On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
On the Convexification of Constrained Quadratic Optimization Problems with Indicator Variables
复制标题
DOI：
10.1007/978-3-030-45771-6_33
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Linchuan Wei;A. Gómez;Simge Küçükyavuz
中科院分区：
文献类型：
--
作者：
Linchuan Wei;A. Gómez;Simge Küçükyavuz
受现代回归应用的启发，本文研究了具有指标变量和指标组合约束的二次优化问题的凸化问题。与以往研究稀疏回归凸化问题的工作不同，我们同时考虑了非线性目标变量、指示变量和组合约束。我们证明了对于一个可分的二次目标函数，透视重构是理想的，不受问题的约束。相反，虽然利用k-稀疏约束的信息不能加强一阶松弛，但对于具有分层结构或多重共线性的推理问题中出现的其他约束，它们可以得到改善。
Motivated by modern regression applications, in this paper, we study the convexification of quadratic 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 objective, indicator variables, and combinatorial constraints. We prove that for a separable quadratic objective function, the perspective reformulation is ideal independent from the constraints of the problem. In contrast, while rank-one relaxations cannot be strengthened by exploiting information fromk-sparsity constraint for, they can be improved for other constraints arising in inference problems with hierarchical structure or multi-collinearity.