QCQPs

Quadratically constrained quadratic programs QCQPs are optimization problems in which both the objective function and the constraints are quadratic forms in the decision variables. A common standard form is: minimize x^T Q0 x + c0^T x + d0 subject to x^T Qi x + ci^T x + di ≤ 0 for i = 1,...,m, and equality constraints x^T Qe_j x + ce_j^T x + de_j = 0 if present. The decision variable x lies in R^n. In general, QCQPs can be convex or nonconvex depending on the matrices involved.

If the objective and all constraint quadratics are convex — for example, Q0 and all constraint matrices Qi are positive semidefinite — the problem is a convex optimization problem with a unique global optimum. When any of the quadratic forms are indefinite, the problem is nonconvex and may have multiple local minima, making global optimization more challenging.

Solving QCQPs exactly is NP-hard in general. A central approach for many nonconvex or large-scale instances is to use convex relaxations, notably semidefinite programming (SDP) relaxations. These lift the problem to a matrix variable X ≈ xx^T and replace nonconvex rank constraints with convex criteria, providing lower bounds and sometimes exact solutions under favorable conditions. Other methods include interior-point methods for convex QCQPs, sequential quadratic programming, augmented Lagrangian, and ADMM. For nonconvex QCQPs, global algorithms such as branch-and-bound, specialized global optimization techniques, or heuristic iterative methods are commonly employed.

Applications of QCQPs appear in engineering and applied sciences, including power systems optimization (for example, optimal power flow), wireless communications (beamforming under quadratic power constraints), control, signal processing, and financial engineering where risk or return constraints are modeled quadratically.