On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations have been among the most popular convexification techniques for binary polynomial optimization problems. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal recursive sequence amounts to solving a difficult combinatorial optimization problem. In this paper, we prove that any … Read more

Explicit convex hull description of bivariate quadratic sets with indicator variables

\(\) We consider the nonconvex set \(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, … Read more