Quadratically constrained quadratic program
In mathematical optimization, a quadratically constrained quadratic program is an optimization problem in which both the objective function and the constraints are quadratic functions. It has the form
where P0, …, Pm are n-by-n matrices and x ∈ Rn is the optimization variable.
If P0, …, Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If P1, …,Pm are all zero, then the constraints are in fact linear and the problem is a quadratic program.
Hardness
Solving the general case is an NP-hard problem. To see this, note that the two constraints x1 ≤ 0 and x1 ≥ 0 are equivalent to the constraint x1 = 0, which is in turn equivalent to the constraint x1 ∈. Hence, any 0–1 integer program can be formulated as a quadratically constrained quadratic program. Since 0–1 integer programming is NP-hard in general, QCQP is also NP-hard.Relaxation
There are two main relaxations of QCQP: using semidefinite programming, and using the reformulation-linearization technique. For some classes of QCQP problems, second-order cone programming and linear programming relaxations providing the same objective value as the SDP relaxation are available.Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations, and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact. Moreover, it was shown that a class of random general QCQPs has exact semidefinite relaxations with high probability as long as the number of constraints grows no faster than a fixed polynomial in the number of variables.
Semidefinite programming
When P0, …, Pm are all positive-definite matrices, the problem is convex and can be readily solved using interior point methods, as done with semidefinite programming.Example
is a problem in graph theory, which is NP-hard. Given a graph, the problem is to divide the vertices in two sets, so that as many edges as possible go from one set to the other. Max Cut can be formulated as a QCQP, and SDP relaxation of the dual provides good lower bounds.Solvers and scripting (programming) languages
| Name | Brief info |
| Artelys Knitro | Knitro is a solver specialized in nonlinear optimization, but also solves linear programming problems, quadratic programming problems, second-order cone programming, systems of nonlinear equations, and problems with equilibrium constraints. |
| FICO Xpress | A commercial optimization solver for linear programming, non-linear programming, mixed integer linear programming, convex quadratic programming, convex quadratically constrained quadratic programming, second-order cone programming and their mixed integer counterparts. |
| AMPL | |
| CPLEX | Popular solver with an API for several programming languages. Free for academics. |
| Gurobi | Solver with parallel algorithms for large-scale linear programs, quadratic programs and mixed-integer programs. Free for academic use. |
| MOSEK | A solver for large scale optimization with API for several languages |
| TOMLAB | Supports global optimization, integer programming, all types of least squares, linear, quadratic and unconstrained programming for MATLAB. TOMLAB supports solvers like Gurobi, CPLEX, SNOPT and KNITRO. |