Ideal formulations for constrained convex optimization problems with indicator variables
From MaRDI portal
Publication:2118117
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 regression problems under hierarchy constraints on real datasets demonstrate the potential of the proposed approach in improving the relaxation quality without significant computational overhead.
Recommendations
- On the convexification of constrained quadratic optimization problems with indicator variables
- \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
- Strong formulations for conic quadratic optimization with indicator variables
- A graph-based decomposition method for convex quadratic optimization with indicators
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
Cites work
- A branch-and-cut method for 0-1 mixed convex programming
- A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes
- A conic representation of the convex hull of disjunctive sets and conic cuts for integer second order cone optimization
- A lasso for hierarchical interactions
- A selective review of group selection in high-dimensional models
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- A unified approach to mixed-integer optimization problems with logical constraints
- Approximated perspective relaxations: a project and lift approach
- Best subset selection via a modern optimization lens
- Convex programming for disjunctive convex optimization
- Cutting-Planes for Optimization of Convex Functions over Nonconvex Sets
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Feature subset selection for logistic regression via mixed integer optimization
- Forbidden vertices
- How to convexify the intersection of a second order cone and a nonconvex quadratic
- scientific article; zbMATH DE number 1906319 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6438182 (Why is no real title available?)
- Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach
- Intersection cuts for nonlinear integer programming: convexification techniques for structured sets
- Learning sparse classifiers: continuous and mixed integer optimization perspectives
- Least angle regression. (With discussion)
- Lifting inequalities: a framework for generating strong cuts for nonlinear programs
- Mixed-integer nonlinear programs featuring ``on/off constraints
- Nearly unbiased variable selection under minimax concave penalty
- On Convex Hulls of Epigraphs of QCQPs
- On convex relaxations for quadratically constrained quadratic programming
- On integer and MPCC representability of affine sparsity
- On the convexification of constrained quadratic optimization problems with indicator variables
- On the copositive representation of binary and continuous nonconvex quadratic programs
- On valid inequalities for quadratic programming with continuous variables and binary indicators
- OR forum: An algorithmic approach to linear regression
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Projected perspective reformulations with applications in design problems
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- Quadratic convex reformulations for semicontinuous quadratic programming
- Scalable algorithms for the sparse ridge regression
- SDP diagonalizations and perspective cuts for a class of nonseparable MIQP
- Small and strong formulations for unions of convex sets from the Cayley embedding
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- Sparse Approximate Solutions to Linear Systems
- Sparse high-dimensional regression: exact scalable algorithms and phase transitions
- Sparse learning via Boolean relaxations
- Sparse regression: scalable algorithms and empirical performance
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Structural properties of affine sparsity constraints
- Two-term disjunctions on the second-order cone
- Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Cited in
(21)- Valid inequalities for separable concave constraints with indicator variables
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- On the convexification of constrained quadratic optimization problems with indicator variables
- A new perspective on low-rank optimization
- A graph-based decomposition method for convex quadratic optimization with indicators
- On the convex hull of convex quadratic optimization problems with indicators
- Supermodularity and valid inequalities for quadratic optimization with indicators
- Subset Selection and the Cone of Factor-Width-k Matrices
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
- A new dual-based cutting plane algorithm for nonlinear adjustable robust optimization
- Cardinality minimization, constraints, and regularization: a survey
- Constrained optimization of rank-one functions with indicator variables
- Exact continuous relaxations of _0-regularized criteria with non-quadratic data terms
- Integer programming for learning directed acyclic graphs from nonidentifiable Gaussian models
- End-to-end, decision-based, cardinality-constrained portfolio optimization
- Mathematical optimization modelling for group counterfactual explanations
- Rank-one convexification for sparse regression
- 50 years of mixed-integer nonlinear and disjunctive programming
- Explicit convex hull description of bivariate quadratic sets with indicator variables
- A parametric approach for solving convex quadratic optimization with indicators over trees
- Polyhedral analysis of quadratic optimization problems with Stieltjes matrices and indicators
This page was built for publication: Ideal formulations for constrained convex optimization problems with indicator variables
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118117)
