2017

General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming

Park, Jaehyun, Boyd, Stephen

Understand

We introduce the Suggest-and-Improve framework for general nonconvex quadratically constrained quadratic programs (QCQPs).

Using this framework, we generalize a number of known methods and provide heuristics to get approximate solutions to QCQPs for which no specialized methods are available.
We also introduce an open-source Python package QCQP, which implements the heuristics discussed in the paper.

Built on

Nonlinear programming
H. W. Kuhn and A. W. Tucker · 1951
Earlier work this paper cites.
An algorithm for quadratic programming
M. Frank and P. Wolfe · 1956
Earlier work this paper cites.
A quadratic programming procedure
C. Hildreth · 1957
Earlier work this paper cites.
Assignment problems and the location of economic activities
T. C. Koopmans and M. Beckmann · 1957
Earlier work this paper cites.
A method for solving traveling-salesman problems
G. A. Croes · 1958
Earlier work this paper cites.
The cutting-plane method for solving convex programs
J. E. Kelley, Jr · 1960
Earlier work this paper cites.
On the field of values of a matrix
L. Brickman · 1961
Earlier work this paper cites.
Linear systems of real quadratic forms
E. Calabi · 1964
Earlier work this paper cites.
Maximization by quadratic hill-climbing
S. M. Goldfeld, R. E. Quandt, and H. F. Trotter · 1966
Earlier work this paper cites.
Branch-and-bound methods: A survey
E. L. Lawler and D. E. Wood · 1966
Earlier work this paper cites.
Programming with a quadratic constraint
C. Van de Panne · 1966
Earlier work this paper cites.
A note on the branch-and-bound principle
E. Balas · 1968
Earlier work this paper cites.
Pairs of quadratic forms
M. R. Hestenes · 1968
Earlier work this paper cites.
Direct methods for solving symmetric indefinite systems of linear equations
J. R. Bunch and B. N. Parlett · 1971
Earlier work this paper cites.
The complexity of theorem-proving procedures
S. A. Cook · 1971
Earlier work this paper cites.
Quadratic programming with quadratic constraints
D. P. Baron · 1972
Earlier work this paper cites.
Reducibility Among Combinatorial Problems
R. M. Karp · 1972
Earlier work this paper cites.
Computationally related problems
S. Sahni · 1974
Earlier work this paper cites.
A dual method for quadratic programs with quadratic constraints
J. G. Ecker and R. D. Niemi · 1975
Earlier work this paper cites.
Solution of sparse indefinite systems of linear equations
C. C. Paige and M. A. Saunders · 1975
Earlier work this paper cites.
Factorizing symmetric indefinite matrices
R. Fletcher · 1976
Earlier work this paper cites.
An algorithm for nonconvex programming problems
R. Horst · 1976
Earlier work this paper cites.
The Levenberg-Marquardt algorithm: Implementation and theory
J. J. Moré · 1978
Earlier work this paper cites.
On the shannon capacity of a graph
L. Lovász · 1979
Earlier work this paper cites.
A recurring theorem about pairs of quadratic forms and extensions: A survey
F. Uhlig · 1979
Earlier work this paper cites.
Necessary and sufficient conditions for the simultaneous diagonability of two quadratic forms
R. I. Becker · 1980
Earlier work this paper cites.
The polynomial solvability of convex quadratic programming
M. K. Kozlov, S. P. Tarasov, and L. G. Khachiyan · 1980
Earlier work this paper cites.
Computing optimal locally constrained steps
D. M. Gay · 1981
Earlier work this paper cites.
Newton’s method with a model trust region modification
D. C. Sorensen · 1982
Earlier work this paper cites.
Jointly constrained biconvex programming
F. A. Al-Khayyal and J. E. Falk · 1983
Earlier work this paper cites.
Computing a trust region step
J. J. Moré and D. C. Sorensen · 1983
Earlier work this paper cites.
Quadratic optimization problems
N. Z. Shor · 1987
Earlier work this paper cites.
Combinatorial Optimization with Interior-Point Methods and Semi-Definite Matrices
F. Alizadeh · 1991
Earlier work this paper cites.
Branch and bound algorithm for computing the minimum stability degree of parameter-dependent linear systems
V. Balakrishnan, S. Boyd, and S. Balemi · 1991
Earlier work this paper cites.
On the convergence of the proximal point algorithm for convex minimization
O. Güler · 1991
Earlier work this paper cites.
Quadratically constrained least squares and quadratic problems
G. H. Golub and U. Von Matt · 1991
Earlier work this paper cites.
Topics in matrix analysis
R. A. Horn and C. R. Johnson · 1991
Earlier work this paper cites.
Global optimization to prescribed accuracy
R. E. Moore · 1991
Earlier work this paper cites.
A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems
M. Padberg and G. Rinaldi · 1991
Earlier work this paper cites.
Quadratic programming with one negative eigenvalue is NP-hard
P. M. Pardalos and S. A. Vavasis · 1991
Earlier work this paper cites.
A dual algorithm for minimizing a quadratic function with two quadratic constraints
Y.-X. Yuan · 1991
Earlier work this paper cites.
Generalized bilinear programming: Part I. models, applications and linear programming relaxation
F. A. Al-Khayyal · 1992
Earlier work this paper cites.
On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators
J. Eckstein and D. P. Bertsekas · 1992
Earlier work this paper cites.
An o ⁡ ( n l ) o(\sqrt{n}l) -iteration large-step primal-dual affine algorithm for linear programming
C. C. Gonzaga and M. J. Todd · 1992
Earlier work this paper cites.
Augmented lagrangian algorithms for linear programming
O. Güler · 1992
Earlier work this paper cites.
New proximal point algorithms for convex minimization
O. Güler · 1992
Earlier work this paper cites.
Laplacian eigenvalues and the maximum cut problem
C. Delorme and S. Poljak · 1993
Earlier work this paper cites.
The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
C. Delorme and S. Poljak · 1993
Earlier work this paper cites.
Generalizations of the trust region problem
J. J. Moré · 1993
Earlier work this paper cites.
Linear Matrix Inequalities in System and Control Theory
S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan · 1994
Earlier work this paper cites.
Interior-Point Polynomial Methods in Convex Programming
Y. Nesterov and A. Nemirovskii · 1994
Earlier work this paper cites.
A relaxation method for nonconvex quadratically constrained quadratic programs
F. A. Al-Khayyal, C. Larsen, and T. Van Voorhis · 1995
Earlier work this paper cites.
Optimization of positive generalized polynomials under l p l^{p} constraints
L. Baratchart, M. Berthod, and L. Pottier · 1995
Earlier work this paper cites.
Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
M. X. Goemans and D. P. Williamson · 1995
Earlier work this paper cites.
Solving the max-cut problem using eigenvalues
S. Poljak and F. Rendl · 1995
Earlier work this paper cites.
A recipe for semidefinite relaxation for (0, 1)-quadratic programming
S. Poljak, F. Rendl, and H. Wolkowicz · 1995
Earlier work this paper cites.
A reformulation-convexification approach for solving nonconvex quadratic programming problems
H. D. Sherali and C. H. Tuncbilek · 1995
Earlier work this paper cites.
Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations
R. J. Stern and H. Wolkowicz · 1995
Earlier work this paper cites.
Hidden convexity in some nonconvex quadratically constrained quadratic programming
A. Ben-Tal and M. Teboulle · 1996
Earlier work this paper cites.
Numerical Methods for Unconstrained Optimization and Nonlinear Equations
J. E. Dennis Jr. and R. B. Schnabel · 1996
Earlier work this paper cites.
Eigenvalue optimization
A. S. Lewis and M. L. Overton · 1996
Earlier work this paper cites.
Semidefinite programming
L. Vandenberghe and S. Boyd · 1996
Earlier work this paper cites.
Semidefinite programming relaxations of non-convex problems in control and combinatorial optimization
S. Boyd and L. Vandenberghe · 1997
Earlier work this paper cites.
A semidefinite framework for trust region subproblems with applications to large scale minimization
F. Rendl and H. Wolkowicz · 1997
Earlier work this paper cites.
Multiobjective output-feedback control via LMI optimization
C. Scherer, P. Gahinet, and M. Chilali · 1997
Earlier work this paper cites.

Similar

A modified Cholesky algorithm based on a symmetric indefinite factorization
S. H. Cheng and N. J. Higham · 1998
Cited alongside, same era.
An algorithm for quadratic optimization with one quadratic constraint and bounds on the variables
G. C. Fehmers, L. P. J. Kamp, and F. W. Sluijter · 1998
Cited alongside, same era.
On the quality of spectral separators
S. Guattery and G. L. Miller · 1998
Cited alongside, same era.
Applications of second-order cone programming
M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret · 1998
Cited alongside, same era.
Global quadratic optimization via conic relaxation
Y. Nesterov · 1998
Cited alongside, same era.
Semidefinite relaxation and nonconvex quadratic optimization
Y. Nesterov · 1998
Cited alongside, same era.
A simplicial branch-and-bound method for solving nonconvex all-quadratic programs
U. Raber · 1998
Cited alongside, same era.
Strong duality for a trust-region type relaxation of the quadratic assignment problem
K. Anstreicher, X. Chen, H. Wolkowicz, and Y.-X. Yuan · 1999
Cited alongside, same era.
Nonlinear Programming
D. P. Bertsekas · 1999
Cited alongside, same era.
Semidefinite relaxations, multivariate normal distributions, and order statistics
D. Bertsimas and Y. Ye · 1999
Cited alongside, same era.
Solving the trust-region subproblem using the lanczos method
N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint · 1999
Cited alongside, same era.
Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization
C. Lemaréchal, F. Oustry, et al · 1999
Cited alongside, same era.

Then

Rank-constrained separable semidefinite programming with applications to optimal beamforming
Y. Huang and D. P. Palomar · 2010
Later among the works it cites.
Semidefinite relaxation of quadratic optimization problems
Z.-Q. Luo, W.-K. Ma, A. M.-C. So, Y. Ye, and S. Zhang · 2010
Later among the works it cites.
New results on Hermitian matrix rank-one decomposition
W. Ai, Y. Huang, and S. Zhang · 2011
Later among the works it cites.
Distributed optimization and statistical learning via the alternating direction method of multipliers
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein · 2011
Later among the works it cites.
Proximal splitting methods in signal processing
P. L. Combettes and J.-C. Pesquet · 2011
Later among the works it cites.
APOGEE: Global optimization of standard, generalized, and extended pooling problems via linear and logarithmic partitioning schemes
R. Misener, J. P. Thompson, and C. A. Floudas · 2011
Later among the works it cites.
The NumPy array: a structure for efficient numerical computation
S. van der Walt, S. C. Colbert, and G. Varoquaux · 2011
Later among the works it cites.
Multiuser MIMO downlink beamforming design based on group maximum SINR filtering
Y.-H. Yang, S.-C. Lin, and H.-J. Su · 2011
Later among the works it cites.
Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation
Original
X. J. Zheng, X. L. Sun, and D. Li · 2011
Later among the works it cites.
Globally solving nonconvex quadratic programming problems via completely positive programming
J. Chen and S. Burer · 2012
Later among the works it cites.
Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint
J.-M. Feng, G.-X. Lin, R.-L. Sheu, and Y. Xia · 2012
Later among the works it cites.
Global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations
R. Misener and C. A. Floudas · 2012
Later among the works it cites.
Linear programming relaxations of quadratically constrained quadratic programs
A. Qualizza, P. Belotti, and F. Margot · 2012
Later among the works it cites.
An alternating direction algorithm for matrix completion with nonnegative factors
Y. Xu, W. Yin, Z. Wen, and Y. Zhang · 2012
Later among the works it cites.
Sphere Packings, Lattices and Groups
J. H. Conway and N. J. A. Sloane · 2013
Later among the works it cites.
An improved three-weight message-passing algorithm
N. Derbinsky, J. Bento, V. Elser, and J. S. Yedidia · 2013
Later among the works it cites.
Algebraic Graph Theory
C. Godsil and G. F. Royle · 2013
Later among the works it cites.
A revisit to quadratic programming with one inequality quadratic constraint via matrix pencil
Y. Hsia, G.-X. Lin, and R.-L. Sheu · 2013
Later among the works it cites.
CPLEX User’s Manual Version 12 Release 6
IBM ILOG CPLEX Optimization Studio · 2013
Later among the works it cites.
Low-rank matrix completion using alternating minimization
P. Jain, P. Netrapalli, and S. Sanghavi · 2013
Later among the works it cites.
GloMIQO: Global mixed-integer quadratic optimizer
R. Misener and C. A. Floudas · 2013
Later among the works it cites.
Phase retrieval using alternating minimization
P. Netrapalli, P. Jain, and S. Sanghavi · 2013
Later among the works it cites.
A fast semidefinite approach to solving binary quadratic problems
P. Wang, C. Shen, and A. Van Den Hengel · 2013
Later among the works it cites.
Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report
C. Bliek, P. Bonami, and A. Lodi · 2014
Later among the works it cites.
Constrained Optimization and Lagrange Multiplier Methods
D. P. Bertsekas · 2014
Later among the works it cites.
CVX: Matlab software for disciplined convex programming, version 2.1
M. Grant and S. Boyd · 2014
Later among the works it cites.
Alternating direction method of multipliers for real and complex polynomial optimization models
B. Jiang, S. Ma, and S. Zhang · 2014
Later among the works it cites.
The NLopt nonlinear-optimization package
S. G. Johnson · 2014
Later among the works it cites.
ANTIGONE: Algorithms for continuous/integer global optimization of nonlinear equations
R. Misener and C. A. Floudas · 2014
Later among the works it cites.
A framework for globally optimizing mixed-integer signomial programs
R. Misener and C. A. Floudas · 2014
Later among the works it cites.
BARON 14.3.1: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual
N. V. Sahinidis · 2014
Later among the works it cites.
A conic quadratic programming approach to physical layer multicasting for large-scale antenna arrays
L.-N. Tran, M. F. Hanif, and M. Juntti · 2014
Later among the works it cites.
Quadratically constrained quadratic programs on acyclic graphs with application to power flow
S. Bose, D. F. Gayme, K. M. Chandy, and S. H. Low · 2015
Later among the works it cites.
Phase retrieval via matrix completion
E. J. Candes, Y. C. Eldar, T. Strohmer, and V. Voroninski · 2015
Later among the works it cites.
Phase retrieval via Wirtinger flow: Theory and algorithms
E. J. Candes, X. Li, and M. Soltanolkotabi · 2015
Later among the works it cites.
Gurobi optimizer reference manual, 2015
Inc. Gurobi Optimization · 2015
Later among the works it cites.
High performance adaptive algorithms for single-group multicast beamforming
B. Gopalakrishnan and N. D. Sidiropoulos · 2015
Later among the works it cites.
Methods for convex and general quadratic programming
P. E. Gill and E. Wong · 2015
Later among the works it cites.
Hidden convexity in QCQP with Toeplitz-Hermitian quadratics
A. Konar and N. D. Sidiropoulos · 2015
Later among the works it cites.
Parallel algorithms for constrained tensor factorization via alternating direction method of multipliers
A. P. Liavas and N. D. Sidiropoulos · 2015
Later among the works it cites.
Feasible point pursuit and successive approximation of non-convex QCQPs
O. Mehanna, K. Huang, B. Gopalakrishnan, A. Konar, and N. D. Sidiropoulos · 2015
Later among the works it cites.
Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
R. Misener, J. B. Smadbeck, and C. A. Floudas · 2015
Later among the works it cites.
Phase retrieval with application to optical imaging: a contemporary overview
Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev · 2015
Later among the works it cites.
Convex methods for rank-constrained optimization problems
D. M. Van Sy Mai, B. Ramasubramanian, and M. C. Rotkowitz · 2015
Later among the works it cites.
Phase recovery, MaxCut and complex semidefinite programming
I. Waldspurger, A. d’Aspremont, and S. Mallat · 2015
Later among the works it cites.
Coordinate descent algorithms
S. J. Wright · 2015
Later among the works it cites.
Global convergence of ADMM in nonconvex nonsmooth optimization
Y. Wang, W. Yin, and J. Zeng · 2015
Later among the works it cites.
An efficient algorithm for linear semi-infinite programming over positive polynomials
M. Xu and Z. Luo · 2015
Later among the works it cites.
CVXPY: A Python-embedded modeling language for convex optimization
S. Diamond and S. Boyd · 2016
Later among the works it cites.
The SCIP optimization suite 3.2
G. Gamrath, T. Fischer, T. Gally, A. M. Gleixner, G. Hendel, T. Koch, S. J. Maher, M. Miltenberger, B. Müller, M. E. Pfetsch, C. Puchert, D. Rehfeldt, S. Schenker, R. Schwarz, F. Serrano, Y. Shinano, S. Vigerske, D. Weninger, M. Winkler, J. T. Witt, and J. Witzig · 2016
Later among the works it cites.
On convexity and identifiability in 1-D Fourier phase retrieval
K. Huang, Y. C. Eldar, and N. D. Sidiropoulos · 2016
Later among the works it cites.
Phase retrieval from 1D Fourier measurements: Convexity, uniqueness, and algorithms
K. Huang, Y. C. Eldar, and N. D. Sidiropoulos · 2016
Later among the works it cites.
Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems
M. Hong, Z.-Q. Luo, and M. Razaviyayn · 2016
Later among the works it cites.
Consensus-ADMM for general quadratically constrained quadratic programming
K. Huang and N. D. Sidiropoulos · 2016
Later among the works it cites.
SciPy: open source scientific tools for Python
E. Jones, T. Oliphant, and P. Peterson · 2016
Later among the works it cites.
Binary quadratic optimization problems that are difficult to solve by conic relaxations
S. Kim and M. Kojima · 2016
Later among the works it cites.
Variations and extension of the convex-concave procedure
T. Lipp and S. Boyd · 2016
Later among the works it cites.
Low-rank semidefinite programming: Theory and applications
A. Lemon, A. M.-C. So, and Y. Ye · 2016
Later among the works it cites.
Phase retrieval using feasible point pursuit: Algorithms and Cramér-Rao bound
C. Qian, N. D. Sidiropoulos, K. Huang, L. Huang, and H. C. So · 2016
Later among the works it cites.
Disciplined convex-concave programming
X. Shen, S. Diamond, Y. Gu, and S. Boyd · 2016
Later among the works it cites.
Power system state estimation via feasible point pursuit
G. Wang, A. S. Zamzam, G. B. Giannakis, and N. D. Sidiropoulos · 2016
Later among the works it cites.
Beyond relaxation and Newton-Raphson: Solving AC OPF for multi-phase systems with renewables
A. S. Zamzam, N. D. Sidiropoulos, and E. Dall’Anese · 2016
Later among the works it cites.
The MOSEK optimization toolbox for MATLAB manual. Version 8.0
MOSEK ApS · 2017
Closest in time.
A semidefinite programming method for integer convex quadratic minimization
J. Park and S. Boyd · 2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…