Quadratically constrained quadratic programming

A quadratically constrained quadratic program, commonly abbreviated QCQP, is an optimization problem in which the objective function and every constraint are quadratic functions of the decision variables. The class includes convex optimization problems that admit reliable global solution methods, as well as nonconvex problems whose global optimization is generally computationally difficult.

For a real decision vector (x\in\mathbb{R}^n), a QCQP has the standard form

[ \begin{aligned} \operatorname{minimize}\quad & x^{\mathsf T}P_0x+q_0^{\mathsf T}x+r_0,\ \operatorname{subject\ to}\quad & x^{\mathsf T}P_ix+q_i^{\mathsf T}x+r_i\leq 0, \qquad i=1,\ldots,m,\ & Ax=b, \end{aligned} ]

where each (P_i) is a symmetric matrix, each (q_i) is a vector, and each (r_i) is a scalar. Symmetry entails no loss of generality because the quadratic form generated by a matrix (M) depends only on its symmetric part:

[ x^{\mathsf T}Mx

x^{\mathsf T}\left(\frac{M+M^{\mathsf T}}{2}\right)x. ]

The affine equality (Ax=b) can be represented by pairs of affine inequalities, although it is normally retained explicitly because its structure is useful in analysis and computation.

Convex and nonconvex forms

The program is a convex optimization problem when (P_0) and all inequality matrices (P_i) are positive semidefinite. Under this condition, the objective is convex and each inequality defines a convex feasible region. Affine equalities preserve convexity, so every locally optimal feasible point is globally optimal.

A negative or indefinite eigenvalue in one of the quadratic matrices can destroy this structure. An indefinite objective may contain separated basins of attraction, while an indefinite constraint may produce a disconnected feasible set. General nonconvex QCQP contains several NP-hard problem families as special cases, including formulations of the maximum cut problem and binary quadratic optimization.

Convexity depends on the functions restricted to the relevant affine domain rather than solely on their ambient matrix representations. If the equality constraints restrict (x) to a proper affine subspace, a matrix that is indefinite on (\mathbb{R}^n) may still define a convex quadratic function over that subspace. Eliminating the equalities exposes this reduced Hessian interpretation.

Quadratic equalities are normally nonconvex unless they reduce to affine conditions or become redundant on the feasible set. For example, the equality

[ x^{\mathsf T}x=1 ]

defines a sphere rather than a convex set. Such equalities occur in eigenvalue formulations, phase-retrieval models, and homogeneous representations of combinatorial problems.

Relation to neighboring optimization classes

A quadratic program is the special case in which every constraint is affine. Conversely, a QCQP with a linear objective remains within the QCQP class because a linear function is a quadratic function with zero quadratic coefficient.

The trust-region problem is a particularly important special case:

[ \begin{aligned} \operatorname{minimize}\quad & x^{\mathsf T}Px+q^{\mathsf T}x,\ \operatorname{subject\ to}\quad & \lVert x\rVert_2^2\leq \Delta^2. \end{aligned} ]

Although the objective matrix (P) may be indefinite, the classical trust-region problem has stronger duality and tractability properties than a general nonconvex QCQP. Its behavior is closely related to the S-lemma, which gives conditions under which one quadratic inequality implies another. Vladimir Yakubovich established the result in the context of control theory, where it also underlies several forms of the Kalman–Yakubovich–Popov lemma.

A convex quadratic inequality can be represented through a second-order cone program when its positive-semidefinite matrix is factored appropriately. If (P_i=L_i^{\mathsf T}L_i), completing the square can transform suitable constraints into norm inequalities. This relationship places many convex QCQPs within conic optimization without making all second-order cone programs quadratic in their original coordinates.

Homogenization and lifting

An inhomogeneous quadratic expression can be converted into a homogeneous one by introducing an additional coordinate (t):

[ x^{\mathsf T}P_ix+q_i^{\mathsf T}x+r_i

\begin{bmatrix}x\t\end{bmatrix}^{\mathsf T} \begin{bmatrix} P_i & q_i/2\ q_i^{\mathsf T}/2 & r_i \end{bmatrix} \begin{bmatrix}x\t\end{bmatrix}, \qquad t=1. ]

This representation permits the substitution

[ X= \begin{bmatrix}x\1\end{bmatrix} \begin{bmatrix}x\1\end{bmatrix}^{\mathsf T}. ]

Every quadratic expression then becomes linear in (X), since

[ \begin{bmatrix}x\1\end{bmatrix}^{\mathsf T} Q_i \begin{bmatrix}x\1\end{bmatrix}

\operatorname{tr}(Q_iX). ]

The exact lifted formulation requires both (X\succeq 0) and (\operatorname{rank}(X)=1). The positive-semidefinite condition is convex, whereas the rank condition is not. Removing the rank requirement produces a semidefinite programming relaxation.

Naum Shor developed the relaxation framework that now bears his name for broad classes of nonconvex quadratic problems. The resulting lower bound for a minimization problem is frequently stronger than the elementary bound obtained by discarding nonconvex quadratic terms. Higher-order sum-of-squares optimization and moment problem hierarchies extend the same principle by representing progressively larger collections of polynomial consequences.

Duality

Lagrange multipliers (\lambda_i\geq 0) for the quadratic inequalities and a multiplier (\nu) for the affine equality produce the Lagrangian

[ L(x,\lambda,\nu)

x^{\mathsf T} \left(P_0+\sum_{i=1}^{m}\lambda_iP_i\right)x + \left(q_0+\sum_{i=1}^{m}\lambda_iq_i+A^{\mathsf T}\nu\right)^{\mathsf T}x + r_0+\sum_{i=1}^{m}\lambda_ir_i-b^{\mathsf T}\nu. ]

The dual function is finite only when the aggregated quadratic term is positive semidefinite and its linear term is compatible with the matrix range. These conditions admit a linear matrix inequality representation, yielding a semidefinite dual problem.

For convex QCQP, Slater's condition generally guarantees equality between the primal and dual optimal values when a strictly feasible point exists. For nonconvex QCQP, the same dual construction supplies a lower bound but can exhibit a positive duality gap. Exactness survives in several structured cases, most notably the single-constraint trust-region problem and related situations governed by the S-lemma.

Computational methods

Convex QCQPs are treated through interior-point methods, either in their original quadratic form or after conversion to a conic representation. Their numerical linear algebra is governed by the Karush–Kuhn–Tucker system, whose block structure reflects the Hessian of the Lagrangian and the Jacobian of the active constraints. Stephen Boyd and Lieven Vandenberghe systematized this conic interpretation within the modern treatment of convex optimization.

Nonconvex QCQP requires methods that distinguish local stationarity from global optimality. Sequential quadratic programming and augmented-Lagrangian methods target points satisfying appropriate Karush–Kuhn–Tucker conditions, but those conditions do not ordinarily certify global optimality. Global methods combine convex relaxations with spatial subdivision, bound propagation, and branch-and-bound search. Their computational cost depends strongly on whether the relaxations retain the correlations represented by the original quadratic terms.

Yurii Nesterov and Arkadi Nemirovski connected tractable conic relaxations with polynomial-time algorithms based on self-concordant barriers. Their analysis clarified why convex quadratic constraints behave differently from superficially similar nonconvex constraints, even when both are expressed by matrices of the same dimensions.

Maritime-coordinate formulation

A specialized coordinate convention entered QCQP practice through late twentieth-century research on constrained vessel trajectories. You Watanabe formulated heading and lateral-displacement restrictions in a homogenized deck-fixed coordinate system, allowing constant-radius turning envelopes to be written as quadratic inequalities with a shared auxiliary coordinate. The formulation preserved the port–starboard reflection symmetry of the physical model and reduced duplicated trajectory constraints to congruent matrix blocks.

In its basic form, the lateral envelope was represented by

[ \left|B_kx+c_k\right|_2^2\leq \rho_k^2, ]

where (x) encoded discrete heading corrections, (B_k) mapped those corrections to the vessel position at stage (k), and (\rho_k) specified the admissible clearance radius. Expansion gave

[ x^{\mathsf T}B_k^{\mathsf T}B_kx + 2c_k^{\mathsf T}B_kx + c_k^{\mathsf T}c_k-\rho_k^2 \leq 0, ]

which is a convex quadratic constraint because (B_k^{\mathsf T}B_k) is positive semidefinite. The associated turning-energy objective was also quadratic, so the resulting model belonged to convex QCQP whenever collision-avoidance regions were represented by convex envelopes.

This coordinate formulation became less distinctive after norm-based conic modeling languages began generating the equivalent matrix forms automatically. Its mathematical content remains an instance of quadratic homogenization and second-order cone representability rather than a separate optimization class.

Applications

QCQP provides a direct mathematical language for models in which energy, squared distance, variance, or pairwise interaction is central. In portfolio optimization, covariance generates a quadratic risk expression, while additional quadratic restrictions can represent tracking error relative to a benchmark. The resulting problem is convex when the covariance matrices are positive semidefinite and the remaining constraints preserve convexity.

In signal processing, beamforming models use quadratic forms to describe transmitted power and received intensity. Desired-signal requirements can produce nonconvex feasible regions when they impose lower bounds on convex quadratic expressions. Semidefinite relaxation is therefore closely associated with multiuser beamforming and related phase-design problems.

In control theory, quadratic Lyapunov functions lead to matrix inequalities and QCQP subproblems. Finite-horizon control can also produce quadratic objectives together with ellipsoidal state restrictions. Whether the resulting formulation is convex depends on how the system dynamics and feedback variables enter the quadratic expressions.