Faster, but weaker, relaxations for quadratically constrained quadratic programs

DOI10.1007/s10589-013-9618-8zbMath1303.90077OpenAlexW2139767903MaRDI QIDQ742292

Samuel Burer, Sunyoung Kim, Kojima, Masakazu

Publication date: 18 September 2014

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-013-9618-8

zbMATH Keywords

semidefinite programmingnonconvex quadratic programmingsecond-order cone programmingdifference of convex

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items

(Global) optimization: historical notes and recent developments, Sustainable two stage supply chain management: a quadratic optimization approach with a quadratic constraint, A simultaneous diagonalization based SOCP relaxation for portfolio optimization with an orthogonality constraint, The Convex Hull of a Quadratic Constraint over a Polytope, A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, A simultaneous diagonalization based SOCP relaxation for convex quadratic programs with linear complementarity constraints, Copositive Relaxation Beats Lagrangian Dual Bounds in Quadratically and Linearly Constrained Quadratic Optimization Problems, New SOCP relaxation and branching rule for bipartite bilinear programs, Completely positive reformulations for polynomial optimization

Uses Software

• SDPLR
• Biq Mac

Cites Work

• Unnamed Item
• Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations
• Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations
• Positive definite completions of partial Hermitian matrices
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• Semidefinite programming relaxation for nonconvex quadratic programs
• First- and second-order methods for semidefinite programming
• Exploiting sparsity in semidefinite programming via matrix completion. II: Implementation and numerical results
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
• Global Optimization with Polynomials and the Problem of Moments
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• A Newton-CG Augmented Lagrangian Method for Semidefinite Programming
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Spectral Bundle Method for Semidefinite Programming
• Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets