Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
From MaRDI portal
Publication:5038440
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.
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
Cites work
- scientific article; zbMATH DE number 715155 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic programming
- Alternative SDP and SOCP approximations for polynomial optimization
- An efficient second-order cone programming approach for optimal selection in tree breeding
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Conic relaxation approaches for equal deployment problems
- Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxa\-tions
- Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion
- Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
- Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
- Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems
- Fast implementation for semidefinite programs with positive matrix completion
- Fractional QCQP With Applications in ML Steering Direction Estimation for Radar Detection
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Maxima for Graphs and a New Proof of a Theorem of Turán
- Polyhedral-based methods for mixed-integer SOCP in tree breeding
- Positive definite completions of partial Hermitian matrices
- Projection, lifting and extended formulation integer and combinatorial optimization
- Recent advances in the solution of quadratic assignment problems
- SPARSE SECOND ORDER CONE PROGRAMMING FORMULATIONS FOR CONVEX OPTIMIZATION PROBLEMS
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Second-order cone programming
- Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons
- Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(3)
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)
