Polyhedral analysis of quadratic optimization problems with Stieltjes matrices and indicators
研究了含指示变量的凸二次优化问题，假设二次项的Hessian矩阵为Stieltjes矩阵，通过分析Stieltjes多面体并利用超模性，给出了显式凸松弛，计算表明该松弛能精确求解，尤其适用于标准方法难以处理的大整数间隙实例。
Abstract In this paper, we consider convex quadratic optimization problems with indicators on the continuous variables. In particular, we assume that the Hessian of the quadratic term is a Stieltjes matrix, which naturally appears in sparse graphical inference problems and others. We describe an explicit convex formulation for the problem by studying the Stieltjes polyhedron arising as part of an extended formulation and exploiting the supermodularity of a set function defined on its extreme points. Our computational results confirm that the proposed convex relaxation provides an exact optimal solution and may be an effective alternative, especially for instances with large integrality gaps that are challenging with the standard approaches.