$$\mathbf {2\times 2}$$-Convexifications for convex quadratic optimization with indicator variables
研究了含指示变量的凸二次优化问题，针对2×2情形给出了原空间凸包描述和锥二次扩展，并以此为基础构造了更强的半定规划松弛，有效缩小了整数间隙。
Abstract In this paper, we study the convex quadratic optimization problem with indicator variables. For the $${2\times 2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>×</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the $${2\times 2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2</mml:mn> <mml:mo>×</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including the optimal perspective relaxation and the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.