A graph-based decomposition method for convex quadratic optimization with indicators
From MaRDI portal
Abstract: In this paper, we consider convex quadratic optimization problems with indicator variables when the matrix defining the quadratic term in the objective is sparse. We use a graphical representation of the support of , and show that if this graph is a path, then we can solve the associated problem in polynomial time. This enables us to construct a compact extended formulation for the closure of the convex hull of the epigraph of the mixed-integer convex problem. Furthermore, we propose a novel decomposition method for general (sparse) , which leverages the efficient algorithm for the path case. Our computational experiments demonstrate the effectiveness of the proposed method compared to state-of-the-art mixed-integer optimization solvers.
Recommendations
- scientific article; zbMATH DE number 4045481
- On the convexification of constrained quadratic optimization problems with indicator variables
- scientific article; zbMATH DE number 1190656
- A decomposition method for quadratic programming
- Decomposition methods for solving nonconvex quadratic programs via branch and bound
- A Decomposition Method and Its Application to Convex Programming
- Convex relaxation and Lagrangian decomposition for indefinite integer quadratic programming
- scientific article; zbMATH DE number 5630592
- \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
- Branch-and-bound decomposition approach for solving quasiconvex-concave programs
Cites work
- A Short Proof of the Factor Theorem for Finite Graphs
- A strong conic quadratic reformulation for machine-job assignment with controllable processing times
- An efficient algorithm for image segmentation, Markov random fields and related problems
- Bayesian image restoration, with two applications in spatial statistics (with discussion)
- Best subset selection via a modern optimization lens
- Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach
- Computational study of a family of mixed-integer quadratic programming problems
- Convex programming for disjunctive convex optimization
- Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs
- Formulations for dynamic lot sizing with service levels
- scientific article; zbMATH DE number 5485514 (Why is no real title available?)
- scientific article; zbMATH DE number 4088961 (Why is no real title available?)
- scientific article; zbMATH DE number 954974 (Why is no real title available?)
- scientific article; zbMATH DE number 3716294 (Why is no real title available?)
- scientific article; zbMATH DE number 3513115 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 795222 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Ideal formulations for constrained convex optimization problems with indicator variables
- Improving the approximated projected perspective reformulation by dual information
- Lifting inequalities: a framework for generating strong cuts for nonlinear programs
- Numerical linear algebra and applications
- On general minimax theorems
- On the consistent path problem
- On the convexification of constrained quadratic optimization problems with indicator variables
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Outer approximation for integer nonlinear programs via decision diagrams
- Outlier detection in time series via mixed-integer conic quadratic optimization
- Perspective cuts for a class of convex 0-1 mixed integer programs
- Perspective reformulations of mixed integer nonlinear programs with indicator variables
- Primal-dual subgradient methods for convex problems
- Quadratic cone cutting surfaces for quadratic programs with on-off constraints
- Quadratic optimization with switching variables: the convex hull for \(n=2\)
- Scalable algorithms for the sparse ridge regression
- Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
- Solving multi-item lot-sizing problems with an MIP solver using classification and reformulation
- Sparse and smooth signal estimation: convexification of \(\ell_0\)-formulations
- Sparse regression at scale: branch-and-bound rooted in first-order optimization
- Spatio-Temporal Signal Recovery Based on Low Rank and Differential Smoothness
- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Subset selection in sparse matrices
Cited in
(11)- Strong formulations for quadratic optimization with M-matrices and indicator variables
- Ideal formulations for constrained convex optimization problems with indicator variables
- On the convexification of constrained quadratic optimization problems with indicator variables
- \(2 \times 2\)-convexifications for convex quadratic optimization with indicator variables
- On the convex hull of convex quadratic optimization problems with indicators
- Some Strongly Polynomially Solvable Convex Quadratic Programs with Bounded Variables
- Mixed-integer nonlinear optimization: a hatchery for modern mathematics. Abstracts from the workshop held August 13--18, 2023
- Exact SDP reformulations for adjustable robust quadratic optimization with affine decision rules
- Rank-one convexification for sparse regression
- 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: A graph-based decomposition method for convex quadratic optimization with indicators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102761)
