Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
From MaRDI portal
Publication:5038440
DOI10.1080/10556788.2020.1827256zbMATH Open1501.90063arXiv1911.02188OpenAlexW3089683005MaRDI QIDQ5038440FDOQ5038440
Authors:
Publication date: 30 September 2022
Published in: Optimization Methods \& Software (Search for Journal in Brave)
Abstract: Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. (2001) and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP relaxation of QCQPs. Specifically, we prove that exploiting the aggregate sparsity reduces the number of second-order cones in the SOCP relaxation, and that we can simplify the matrix completion procedure by Fukuda et al. in both primal and dual of the SOCP relaxation problem without losing the max-determinant property. For numerical experiments, QCQPs from the lattice graph and pooling problem are tested as their SOCP relaxations provide the same optimal value as the SDP relaxations. We demonstrate that exploiting the aggregate sparsity improves the computational efficiency of the SOCP relaxation for the same objective value as the SDP relaxation, thus much larger problems can be handled by the proposed SOCP relaxation than the SDP relaxation.
Full work available at URL: https://arxiv.org/abs/1911.02188
Recommendations
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Exact SDP relaxations of quadratically constrained quadratic programs with forest structures
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Faster, but weaker, relaxations for quadratically constrained quadratic programs
- A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues
semidefinite programmingsecond-order cone programmingchordal sparsityquadratic constrained quadratic programmingaggregate sparsity
Quadratic programming (90C20) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Semidefinite programming (90C22)
Cites Work
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Second-order cone programming
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Positive definite completions of partial Hermitian matrices
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- SPARSE SECOND ORDER CONE PROGRAMMING FORMULATIONS FOR CONVEX OPTIMIZATION PROBLEMS
- Recent advances in the solution of quadratic assignment problems
- Projection, lifting and extended formulation integer and combinatorial optimization
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
- A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Fast implementation for semidefinite programs with positive matrix completion
- Fractional QCQP With Applications in ML Steering Direction Estimation for Radar Detection
- An efficient second-order cone programming approach for optimal selection in tree breeding
- Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
- Alternative SDP and SOCP approximations for polynomial optimization
- Conic relaxation approaches for equal deployment problems
- Polyhedral-based methods for mixed-integer SOCP in tree breeding
Cited In (3)
Uses Software
This page was built for publication: Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5038440)
