论文标题
带有指示变量的双变量二次集合的显式凸面船体描述
Explicit convex hull description of bivariate quadratic sets with indicator variables
论文作者
论文摘要
我们考虑nonconvex set $ \ mathcal s_n = \ {（x，x，z）：x = x x x^t，\; x（1-z）= 0，\; x \ geq 0，\; z \ in \ {0,1 \}^n \} $，它与几个困难的非convex优化问题的可行区域密切相关，例如最佳子集选择和约束投资组合优化。利用凸分析和析取编程中的想法，我们获得了一个明确的描述，以关闭原始变量空间中$ \ Mathcal S_2 $的凸壳。为了产生与$ \ Mathcal S_2 $的支持凸壳的超平面相对应的有效不平等，我们提出了一种简单的分离算法，可以将其纳入基于分支和切割的求解器中，以增强现有放松的质量。
We consider the nonconvex set $\mathcal S_n = \{(x,X,z): X = x x^T, \; x (1-z) =0,\; x \geq 0,\; z \in \{0,1\}^n\}$, which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, we obtain an explicit description for the closure of the convex hull of $\mathcal S_2$ in the space of original variables. In order to generate valid inequalities corresponding to supporting hyperplanes of the convex hull of $\mathcal S_2$, we present a simple separation algorithm that can be incorporated in branch-and-cut based solvers to enhance the quality of existing relaxations.
