On the convex hull of convex quadratic optimization problems with indicators
On the convex hull of convex quadratic optimization problems with indicators
复制标题
DOI：
10.1007/s10107-023-01982-0
复制
发表时间：
2022-01
期刊：
影响因子：
--
通讯作者：
Linchuan Wei;Alper Atamtürk;Andr'es G'omez;Simge Küçükyavuz
中科院分区：
文献类型：
--
作者：
Linchuan Wei;Alper Atamtürk;Andr'es G'omez;Simge Küçükyavuz
本文研究了一类具有指标变量和任意约束条件的凸二次优化问题.我们表明，一个凸船体描述的相关的混合整数集在一个扩展的空间中的二次额外的变量由一个半正定约束（明确规定）和线性约束。特别是，这类问题的凸化减少到描述一个多面体集在一个扩展的配方。虽然这个多面体集的顶点表示是指数和显式的线性不等式描述可能不容易在一般情况下，我们推导出一个紧凑的混合整数线性配方，其解决方案与多面体集的顶点相一致。我们还在原始变量空间中给出了描述：我们提供了一个基于无穷多个圆锥二次不等式的描述，这些不等式是“非线性生成的”。特别地，可以表征给定的不等式对于描述凸船体是否是必要的。本文提出的新理论统一了几个已有的结果，并为利用多面体方法分析混合整数非线性集的凸船体铺平了道路。
We consider the convex quadratic optimization problem inwith indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of anpositive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. While the vertex representation of this polyhedral set is exponential and an explicit linear inequality description may not be readily available in general, we derive a compact mixed-integer linear formulation whose solutions coincide with the vertices of the polyhedral set. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are “finitely generated.” In particular, it is possible to characterize whether a given inequality is necessary to describe the convex hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.