Ideal formulations for constrained convex optimization problems with indicator variables
Ideal formulations for constrained convex optimization problems with indicator variables
复制标题
DOI：
10.1007/s10107-021-01734-y
复制
发表时间：
2020-06
影响因子：
2.7
通讯作者：
Linchuan Wei;A. Gómez;Simge Küçükyavuz
中科院分区：
文献类型：
--
作者：
Linchuan Wei;A. Gómez;Simge Küçükyavuz
受现代回归应用的启发，本文研究了一类具有指示变量和组合约束的凸优化问题的凸化问题。与以往大多数稀疏回归问题凸化的工作，我们同时考虑非线性不可分离的目标，指示变量，和组合约束。具体地说，我们给出了任意组合约束下一维凸函数和仿射函数合成的上图的凸船体描述。作为这一结果的特殊情况下，我们得到理想的凸性问题的层次，多重共线性，稀疏约束。此外，我们还给出了一个简短的证明，对于一个可分离的目标函数，透视重构是理想的独立于问题的约束。我们的稀疏回归问题的计算实验表明，所提出的方法在提高松弛质量没有显着的计算开销的潜力。
Motivated by modern regression applications, in this paper, we study the convexification of a class of convex optimization problems with indicator variables and combinatorial constraints on the indicators. Unlike most of the previous work on convexification of sparse regression problems, we simultaneously consider the nonlinear non-separable objective, indicator variables, and combinatorial constraints. Specifically, we give the convex hull description of the epigraph of the composition of a one-dimensional convex function and an affine function under arbitrary combinatorial constraints. As special cases of this result, we derive ideal convexifications for problems with hierarchy, multi-collinearity, and sparsity constraints. Moreover, we also give a short proof that for a separable objective function, the perspective reformulation is ideal independent from the constraints of the problem. Our computational experiments with sparse regression problems demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead.