Quadratically Constrained Quadratic Programs (QCQPs)
A Quadratically Constrained Quadratic Program (QCQP) is a convex optimization problem obtained by extending a quadratic program to allow convex quadratic inequality constraints, while keeping an affine feasible structure where possible.
A QCQP has the general form
\min_{x \in \mathbb{R}^n} \quad & x^\top P_0 x + q_0^\top x + r_0 \\ \text{s.t.} \quad & x^\top P_j x + q_j^\top x + r_j \le 0, \quad j = 1,\dots,k, \\ & a_i^\top x = b_i, \quad i = 1,\dots,m, \end{aligned}$$ where each $P_j \in \mathbb{S}^n$ is **positive semidefinite** to guarantee convexity, $q_j \in \mathbb{R}^n$, and $r_j \in \mathbb{R}$. Just as a QP generalizes an LP by allowing a **quadratic objective**, a QCQP generalizes a QP by allowing **quadratic inequality constraints**. If all constraint matrices satisfy $P_j = 0$, the QCQP reduces to a QP. Thus, $$\text{LP} \subset \text{QP} \subset \text{QCQP} \subset \text{Convex Optimization}.$$ Different from LPs and QPs, he **feasible set** of a QCQP is the intersection of **ellipsoids** (from quadratic inequalities) and **hyperplanes** (from affine equalities): $$\mathcal{S}_{\text{QCQP}} = \left(\underbrace{\bigcap_{j=1}^{k}\{x\in\mathbb{R}^n \mid x^\top P_j x + q_j^\top x + r_j \le 0\}}_{\text{quadratic constraint (ellipsoid)}}\right) \cap \left(\underbrace{\bigcap_{i=1}^{m}\{x\in\mathbb{R}^n \mid a_i^\top x = b_i\}}_{\text{hyperplane}}\right).$$ In QCQPs, the boundary generally contains **curved faces**, reflecting the quadratic nature of the constraints. Geometrically, a constraint of the form $$x^\top P x + q^\top x + r \le 0$$ defines a convex ellipsoid (or a degenerate version such as a half-space or cylinder). Intersecting multiple such sets yields a convex but typically **non-polyhedral, curved** region. From a computational standpoint, QCQPs are **harder to solve than QPs**, which are themselves harder than LPs. The loss of polyhedral structure prevents simplex-style vertex traversal, and interior-point or conic methods are typically used instead.