论文标题
具有指标的二次优化的超模型和有效的不平等现象
Supermodularity and valid inequalities for quadratic optimization with indicators
论文作者
论文摘要
我们研究了一个指标的最小化次数的最小化，并表明通过预测连续变量获得的基本集合函数是超模块化的。尽管超模型最小化通常是困难的，但在线性时间内可以最大程度地减少等级二次的特定集合函数。我们表明，可以通过将它们提升为变量原始空间中的非线性不平等，从而从二次二次构图的凸壳中获得。在变量的原始空间和通过圆锥二次陈述的不平等的扩展配方中，都给出了凸形船体描述的明确形式，以及多项式分离算法。计算实验表明，圆锥二次形式的提起的超模块不平等在减少用指标的二次优化的完整性差距方面非常有效。
We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in general, difficult, the specific set function for the rank-one quadratic can be minimized in linear time. We show that the convex hull of the epigraph of the quadratic can be obtaining from inequalities for the underlying supermodular set function by lifting them into nonlinear inequalities in the original space of variables. Explicit forms of the convex-hull description are given, both in the original space of variables and in an extended formulation via conic quadratic-representable inequalities, along with a polynomial separation algorithm. Computational experiments indicate that the lifted supermodular inequalities in conic quadratic form are quite effective in reducing the integrality gap for quadratic optimization with indicators.
