论文标题
有关指标变量的二次约束的注释：凸船体描述和透视放松
A note on quadratic constraints with indicator variables: Convex hull description and perspective relaxation
论文作者
论文摘要
在本文中，我们研究了由连续变量的可分离二次约束给出的混合企业非线性集，其中每个连续变量都由其他指标控制。该集合在不确定性和机器学习的优化问题上普遍存在。我们表明，对此集合的优化是NP-HARD。尽管结果为负面，但我们表征了凸壳的结构，并表明可以使用多面体理论对其进行正式研究。此外，我们表明，尽管该集合的文献中的透视放松无法与其凸船体的结构相匹配，但保证它是一个紧密的近似值。
In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we characterize the structure of the convex hull, and show that it can be formally studied using polyhedral theory. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation.
