Ideal formulations for constrained convex optimization problems with indicator variables

Linchuan Wei, Andrés Gómez*, Simge Küçükyavuz

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)57-88
Number of pages32
JournalMathematical Programming
Volume192
Issue number1-2
DOIs
StatePublished - Mar 2022
Externally publishedYes

Keywords

  • Combinatorial constraints
  • Convexification
  • Indicator variables
  • Perspective formulation

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Ideal formulations for constrained convex optimization problems with indicator variables'. Together they form a unique fingerprint.

Cite this