Using quadratic convex reformulation to tighten the convex relaxation of a quadratic program with complementarity constraints

作者：Bai Lijie; Mitchell John E^*; Pang Jong Shi

来源：Optimization Letters, 2014, 8(3): 811-822.

DOI：10.1007/s11590-013-0647-0

• Convex quadratic program with linear complementarity constraints (QPCC)
• Semidefinite program (SDP)
• Quadratic convex reformulation (QCR)
• Quadratically constrained quadratic program (QCQP)

Quadratic Convex Reformulation (QCR) is a technique that has been proposed for binary and mixed integer quadratic programs. In this paper, we extend the QCR method to convex quadratic programs with linear complementarity constraints (QPCCs). Due to the complementarity relationship between the nonnegative variables and , a term can be added to the QPCC objective function, where is a nonnegative diagonal matrix chosen to maintain the convexity of the objective function and the global resolution of the QPCC. 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 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.

• 出版日期2014-3