A Logical Benders Decomposition Algorithm for Binary-Constrained Quadratic Programs with Complementarity Constraints

An algorithm is presented for solving nonlinear optimization problems with chance constraints, i.e., those in which a constraint involving an uncertain parameter must be satisfied with at least a minimum probability. In particular, the algorithm is designed to solve cardinality-constrained nonlinear optimization problems that arise in sample average approximations of chance-constrained problems. No convexity assumptions are made. The algorithm employs a novel exact penalty function, which is minimized sequentially by solving quadratic optimization subproblems with linear cardinality constraints. Properties of minimizers of the penalty function in relation to minimizers of the corresponding nonlinear optimization problem are presented. The proposed algorithm converges to a stationary point of the penalty function. The effectiveness of the algorithm is demonstrated through numerical experiments. This is work in collaboration with Frank Curtis and Victor Zavala.