On convex quadratic programs with linear complementarity constraints

The present thesis mainly addresses three topics: (1) the global resolution method of convex quadratic programs with linear complementarity constraints (QPCCs); (2) the relationships among QPCCs, quadratically constrained quadratic programs (QCQPs) and completely positive programs; (3) the quadratic convex reformulation (QCR) techniques on the general QCQPs, therefore on the QPCCs. In Chapter 2, we show that the global resolution of a general convex quadratic program with complementarity constraints (QPCC), possibly infeasible or unbounded, can be accomplished in finite time. The method constructs a min-max mixed integer formulation by introducing finitely many binary variables, one for each complementarity constraint. Based on the primal-dual relationship of a pair of convex quadratic programs and on a logical Benders scheme, an extreme ray/point generation procedure is developed, which relies on valid satisfiability constraints for the integer program. To improve this scheme, we propose a two-stage approach wherein the first stage solves the mixed integer quadratic program with preset upper bounds on the complementarity variables, and the second stage solves the program outside this bounded region by the Benders scheme. We report computational results with our method. We also investigate the addition of a penalty term y.;TDw to the objective function, where y and w are the complementary variables and D is a nonnegative diagonal matrix. The matrix D can be chosen effectively by solving a semidefinite program, ensuring that the objective function remains convex. The addition of the penalty term can often reduce the overall runtime by at least 50%. In addition, we report preliminary computational testing on a quadratic program (QP) relaxation method, which can be used to obtain better lower bounds from infeasible points; this method could be incorporated into a branching scheme. By combining the penalty method and the QP relaxation method, more than 90% of the gap can be closed for some QPCC problems. In Chapter 3, we address several topics associated with three classes of constrained optimization problems: QPCCs for quadratic programs with (linear) complementarity constraints, QCQPs for quadratically constrained quadratic programs, and completely positive programs. The subclass of QCQPs, ones that are broader than the QPCCs and fail the Slater constraint qualifications (CQ) can be formulated as QPCCs, therefore a Frank-Wolfe type result holds for this class of QCQPs. We establish a fundamental role of this class of QCQPs in a quadratically constrained non-quadratic program failing the Slater CQ. We also show that such a QCQP, if copositive, can be reformulated as an equivalent completely positive program in the sense of feasibility, boundedness, attainability as well as solvability. Quadratic Convex Reformulation (QCR) is a technique that has been proposed for binary and mixed integer quadratic programs. In Chapter 4, we extend the QCR method to convex quadratic programs with linear complementarity constraints (QPCCs). Due to the complementarity relationship between the nonnegative variables y and w, a term y.;TDw can be added to the QPCC objective function, where D is a nonnegative diagonal matrix chosen to maintain the convexity of the objective function and the global resolution of the QPCC. The addition of y.;TDw turns out to be a simplified version of the QCR method. Following the QCR method, the products of linear equality constraints can also be used to perturb the QPCC objective function, with the goal that the new QP relaxation provides a tighter lower bound. By solving a semidefinite program, an equivalent QPCC can be obtained whose QP relaxation bound is as tight as possible. In addition, we extend the QCR to a general quadratically constrained quadratic program (QCQP), of which the QPCC is a special example. Computational tests on QPCCs are presented.