Asymptotically Tight MILP Approximations for a Nonconvex QCP.

This article focuses on developing two novel mixed-integer linear programming (MILP) approximations for solving nonconvex quadratically constrained programs (QCPs), which are generally NP-hard optimization problems. The authors reformulate each nonconvex quadratic constraint as a second-order cone (SOC) constraint and its complement, then approximate these using polyhedral methods and linear complementarity constraints to obtain linear programs with complementarity constraints (LPCCs). They prove that the LPCCs' optimal values asymptotically converge to that of the original nonconvex QCP and further reformulate the LPCCs as MILPs by establishing boundedness. Extensive computational experiments demonstrate that these MILP approximations yield tighter lower bounds and shorter solution times compared with state-of-the-art solvers and standard LP, SOCP, and SDP relaxations, with applications shown in the joint decision and estimation problem and the two-trust-region subproblem.