# Constrained Optimization of Rank-One Functions with Indicator Variables

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 58 references that are in the map.
- First posted on arXiv 31 Mar 2023.

## Builds on (most cited first, 21 of 21)

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms](https://mlsanity.com/paper/1803.01454/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Integer Programming for Learning Directed Acyclic Graphs from Continuous Data](https://mlsanity.com/paper/1904.10574/) (2019)
- [Sparse Classification: a scalable discrete optimization perspective](https://mlsanity.com/paper/1710.01352/) (2017)
- [Rank-one Convexification for Sparse Regression](https://mlsanity.com/paper/1901.10334/) (2019)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [Sparse and Smooth Signal Estimation: Convexification of L0 Formulations](https://mlsanity.com/paper/1811.02655/) (2018)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Consistent Second-Order Conic Integer Programming for Learning Bayesian Networks](https://mlsanity.com/paper/2005.14346/) (2020)
- [Ideal formulations for constrained convex optimization problems with indicator variables](https://mlsanity.com/paper/2007.00107/) (2020)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [Supermodularity and valid inequalities for quadratic optimization with indicators](https://mlsanity.com/paper/2012.14633/) (2020)
- [A Graph-based Decomposition Method for Convex Quadratic Optimization with Indicators](https://mlsanity.com/paper/2110.12547/) (2021)
- [Learning Hierarchical Interactions at Scale: A Convex Optimization Approach](https://mlsanity.com/paper/1902.01542/) (2019)
- [Compact extended formulations for low-rank functions with indicator variables](https://mlsanity.com/paper/2110.14884/) (2021)
- [Computing in Operations Research using Julia](https://mlsanity.com/paper/1312.1431/) (2013)
- [Conic Mixed-Binary Sets: Convex Hull Characterizations and Applications](https://mlsanity.com/paper/2012.14698/) (2020)
- [Robust Conic Satisficing](https://mlsanity.com/paper/2107.06714/) (2021)

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

- [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)

## Abstract (arXiv)

Optimization problems involving minimization of a rank-one convex function over constraints modeling restrictions on the support of the decision variables emerge in various machine learning applications. These problems are often modeled with indicator variables for identifying the support of the continuous variables. In this paper we investigate compact extended formulations for such problems through perspective reformulation techniques. In contrast to the majority of previous work that relies on support function arguments and disjunctive programming techniques to provide convex hull results, we propose a constructive approach that exploits a hidden conic structure induced by perspective functions. To this end, we first establish a convex hull result for a general conic mixed-binary set in which each conic constraint involves a linear function of independent continuous variables and a set of binary variables. We then demonstrate that extended representations of sets associated with epigraphs of rank-one convex functions over constraints modeling indicator relations naturally admit such a conic representation. This enables us to systematically give perspective formulations for the convex hull descriptions of these sets with nonlinear separable or non-separable objective functions, sign constraints on continuous variables, and combinatorial constraints on indicator variables. We illustrate the efficacy of our results on sparse nonnegative logistic regression problems.