Ideal formulations for constrained convex optimization problems with indicator variables

Abstract

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.

A The special case when \({{\,\mathrm{conv}\,}}(Q)\) is compact

In this section, we give an extended formulation of ${{\,\mathrm{cl \ conv}\,}}(Z_Q)$ based on an extended formulation of ${{\,\mathrm{conv}\,}}(Q_0)$. In particular, this alternative formulation is more favorable in cases when the number of facets of ${{\,\mathrm{conv}\,}}(Q)$ is polynomially bounded while ${{\,\mathrm{conv}\,}}(Q_0)$ has an exponential number of facets. We denote the facets of ${{\,\mathrm{conv}\,}}(Q)$ which do not contain zero by $\{F_\ell \}_{1 \le \ell \le k}$, and we write each $F_\ell$ as $F_\ell := \{z \; | \; A_\ell z \le b_\ell \}$. Angulo et al. [2] prove that ${{\,\mathrm{conv}\,}}(Q_0) = {{\,\mathrm{conv}\,}}\left( \bigcup _{1 \le \ell \le k} F_\ell \right)$, and a natural extended formulation of ${{\,\mathrm{conv}\,}}(Q_0)$ is as follows:

$$\begin{aligned}&z = \sum _{\ell \in [k]} {{\hat{z}}}_\ell \end{aligned}$$

(32a)

$$\begin{aligned}&A_\ell {{\hat{z}}}_\ell \le \lambda _\ell b_\ell&\ell \in [k] \end{aligned}$$

(32b)

$$\begin{aligned}&\sum _{\ell \in [k]} \lambda _\ell = 1, \; \lambda \ge \mathbf{0 }. \end{aligned}$$

(32c)

Theorem 4

$$\begin{aligned}&{{\,\mathrm{cl \ conv}\,}}(Z_Q)\\&\quad = {{\,\mathrm{proj}\,}}_{(z,\beta ,t)} \Big \{(z,{{\hat{z}}}, \lambda , \beta ,t) \in {\mathbb {R}}_+^{(k+1)p + k} \times {\mathbb {R}}^{p}\times {\mathbb {R}}\; | \; (32a)-(32b),\; \sum _{\ell \in [k]} \lambda _\ell \le 1, \\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad t \ge f(\mathbf{1 }^\top \beta ),\;t \ge (\mathbf{1 }^\top \lambda )f\left( \frac{\mathbf{1 }^\top \beta }{\mathbf{1 }^\top \lambda }\right) \Big \}. \end{aligned}$$

Proof Let

$$\begin{aligned} Z \!=\!\Big \{(z,{{\hat{z}}}, \lambda , \beta ,t) \!\in \! {\mathbb {R}}_+^{(k+1)p + k} \times {\mathbb {R}}^{p}\!\times \! {\mathbb {R}}\; | \;&(32a)-(32b),\; \sum _{\ell \in [k]} \lambda _\ell \!\le \! 1, t \!\ge \! f(\mathbf{1 }^\top \beta ), \\&t \ge (\mathbf{1 }^\top \lambda )f\left( \frac{\mathbf{1 }^\top \beta }{\mathbf{1 }^\top \lambda }\right) \Big \}. \end{aligned}$$

First we show that ${{\,\mathrm{proj}\,}}_{(z,\beta ,t)}(Z) \subseteq {{\,\mathrm{cl \ conv}\,}}(Z_Q)$. Given any $(z,{{\hat{z}}}, \lambda , \beta ,t)\in Z$, note that constraints $z\in {{\,\mathrm{conv}\,}}(Q)$ and $t \ge f(\mathbf{1 }^\top \beta )$ defining ${{\,\mathrm{cl \ conv}\,}}(Z_Q)$ are trivially satisfied. It remains to show that $t \ge (\pi ^\top z)f\left( \frac{\mathbf{1 }^\top \beta }{\pi ^\top z}\right) ,\; \; \forall \pi \in {\mathcal {F}}$. For each $\pi \in {\mathcal {F}}$, we have

$$\begin{aligned} \pi ^\top z = \sum _{\ell \in [k]} \pi ^\top {{\hat{z}}}_\ell = \sum _{\ell \in [k]} \lambda _\ell \pi ^\top \left( \frac{{{\hat{z}}}_\ell }{\lambda _\ell }\right) \ge \sum _{\ell \in [k]} \lambda _\ell , \end{aligned}$$

where the inequality follows from the fact that we must have either $\lambda _\ell = 0$ and ${{\hat{z}}}_\ell = \mathbf{0 }$ or $\lambda _\ell > 0$ and $\frac{{{\hat{z}}}_\ell }{\lambda _\ell } \in F_\ell$ since each $F_\ell$ is a polytope contained in the half-space defined by inequality $\mathbf{1 }^\top z\ge 1$. Thus, from Lemma 1, we have $t \ge (\mathbf{1 }^\top \lambda )f\left( \frac{\mathbf{1 }^\top \beta }{\mathbf{1 }^\top \lambda }\right) \ge (\pi ^\top z)f\left( \frac{\mathbf{1 }^\top \beta }{\pi ^\top z}\right) ,\; \; \forall \pi \in {\mathcal {F}}$, hence ${{\,\mathrm{proj}\,}}_{(z,\beta ,t)}(Z) \subseteq {{\,\mathrm{cl \ conv}\,}}(Z_Q)$.

Now, it remains to prove that ${{\,\mathrm{cl \ conv}\,}}(Z_Q) \subseteq {{\,\mathrm{proj}\,}}_{(z,\beta ,t)}(Z)$. For any $(z , \beta , t) \in {{\,\mathrm{cl \ conv}\,}}(Z_Q)$ if $z \in {{\,\mathrm{conv}\,}}(Q_0)$, then there exist ${{\hat{z}}}_\ell$ and $\lambda _\ell$ that satisfy (32) and $\mathbf{1} ^\top \lambda = 1$. Since $t \ge f(\mathbf{1 }^\top \beta )$ for all $(z , \beta , t) \in {{\,\mathrm{cl \ conv}\,}}(Z_Q)$, $(z, \beta , t) \in {{\,\mathrm{proj}\,}}_{(z,\beta ,t)}(Z)$. If $z \in {{\,\mathrm{conv}\,}}(Q)\backslash {{\,\mathrm{conv}\,}}(Q_0)$, then, from Lemma 2, we can write z as $z = \lambda _0 z_0$, $0 \le \lambda _0 < 1$, and we may assume $z_0$ is on one of the facets of ${{\,\mathrm{conv}\,}}(Q_0)$ defined by ${{\hat{\pi }}}^\top z_0 = 1$ for some ${{\hat{\pi }}} \in {\mathcal {F}}$. By definition, $\forall \pi \in {\mathcal {F}} \; \;$ $\pi ^\top z_0 \ge {{\hat{\pi }}}^\top z_0 = 1$ which implies $\lambda _0 = {{\hat{\pi }}}^\top z = \min _{\pi \in {\mathcal {F}}} \pi ^\top z$. Since $z_0 \in {{\,\mathrm{conv}\,}}(Q_0)$, there exists ${{\hat{z}}}_\ell , \lambda _\ell$ such that $z_0 = \sum _{\ell \in [k]} {{\hat{z}}}_\ell$ and (32b)–(32c) hold. Then

$$\begin{aligned} z =&\sum _{\ell \in [k]} (\lambda _0 {{\hat{z}}}_\ell ) \\&A_\ell (\lambda _0 {{\hat{z}}}_\ell ) \le \lambda _0\lambda _\ell b_\ell ,&\ell \in [k] \\&\sum _{\ell \in [k]} \lambda _0 \lambda _\ell \le 1, \lambda \ge \mathbf{0 }, \end{aligned}$$

and we have $\sum _{\ell \in [k]} \lambda _0 \lambda _\ell = \lambda _0 = \min _{\pi \in {\mathcal {F}}} \pi ^\top z$. Using Lemma 1, we find that $t \ge (\pi ^\top z)f\left( \frac{\mathbf{1 }^\top \beta }{\pi ^\top z}\right) ,\; \; \forall \pi \in {\mathcal {F}}$ implies that $t \ge (\sum _{\ell \in [k]} \lambda _0 \lambda _\ell ) f\left( \frac{\mathbf{1 }^\top \beta }{\sum _{\ell \in [k]} \lambda _0 \lambda _\ell }\right) \ge (\sum _{\ell \in [k]} \lambda _\ell ) f\left( \frac{\mathbf{1 }^\top \beta }{\sum _{\ell \in [k]} \lambda _\ell }\right)$. Hence, $(z, \beta , t) \in {{\,\mathrm{proj}\,}}_{(z,\beta ,t)}(Z)$. $\square$