# Ideal formulations for constrained convex optimization problems with indicator variables

arXiv: https://arxiv.org/abs/2007.00107 · HTML: https://mlsanity.com/paper/2007.00107/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jun 2020.

## Built on by (most cited first, 9 of 9)

- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Slowly Varying Regression under Sparsity](https://mlsanity.com/paper/2102.10773/) (2021)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models](https://mlsanity.com/paper/2404.12592/) (2024)
- [On the Exactness of Dantzig-Wolfe Relaxation for Rank Constrained Optimization Problems](https://mlsanity.com/paper/2210.16191/) (2022)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)
- [Coordinate Optimality Reformulation for Mixed-Integer Convex Programs with Indicators](https://mlsanity.com/paper/2608.01385/) (2026)

## Abstract (arXiv)

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 regression problems under hierarchy constraints on real datasets demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead.