论文标题
2x2用于凸变量变量的凸二次优化的凸面
2x2 convexifications for convex quadratic optimization with indicator variables
论文作者
论文摘要
在本文中，我们研究了指标变量的凸二次优化问题。对于双变量情况，我们描述了变量原始空间中墓存的凸面，并给出锥形二次扩展配方。然后，将双变量案例的凸船体描述作为构建块，我们为一般情况提供了扩展的SDP松弛。这种新的配方比有关该问题的文献中提出的其他SDP放松要强，包括Shor的SDP松弛，最佳的视角放松以及最佳的排名一宽松。计算实验表明，所提出的配方在减少优化问题的完整性差距方面非常有效。
In this paper, we study the convex quadratic optimization problem with indicator variables. For the bivariate 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 bivariate 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 Shor's SDP relaxation, the optimal perspective relaxation as well as the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems.
