3.5. Quadratic Programming

Quadratic Program

A Quadratic Program (QP) is a convex optimization problem with a convex quadratic objective and affine constraints. Its standard matrix form is

\min_{x \in \mathbb{R}^n} \quad & x^\top P_0 x + q_0^\top x + r_0 \\ \text{s.t.} \quad & A x = b, \\ & C x \le d, \end{aligned}$$ where $P_0 \in \mathbb{S}^n$ is a symmetric matrix, $q_0 \in \mathbb{R}^n$, and $r_0 \in \mathbb{R}$. Convexity of the problem requires $P_0 \succeq 0$ (i.e., $P_0$ is PSD), since the Hessian of the objective is $2P_0$. When $P_0 = 0$, the quadratic objective reduces to a linear one, and the problem becomes a [[3.2. Linear Programming|linear program]], showing that $$\text{LP} \subset \text{QP} \subset \text{Convex Optimization}$$ Because all constraints in a QP are affine, the **feasible set is identical in structure to that of an LP**: it is the intersection of hyperplanes and half-spaces, forming a **polyhedron** (or a **polytope** if bounded). Thus, geometrically, QPs optimize over the same feasible regions as LPs, but with a curved objective function instead of a flat one. Unlike LPs, where optimal solutions always occur at vertices of the feasible set, a QP’s optimal solution may lie **strictly inside the feasible region**, since the quadratic objective can have a unique minimizer in the interior. In particular, if $P_0 \succ 0$, the objective is **strictly convex**, guaranteeing a **unique global minimizer**. Although QPs remain convex and tractable, they are generally **harder to solve than LPs**, because evaluating and minimizing a quadratic objective is more computationally expensive than a linear one. Nevertheless, many important problems–such as least-squares regression, regularized optimization, and portfolio optimization–naturally take the form of QPs, highlighting their role as the most immediate and practically important extension of Linear Programming.

Examples

Epigraph Technique for QPs

For each $f_i$, formulate the optimization problem in quadratic form. If such formulation is not possible, explain why.

$f_1(x)=\Vert Ax-y{\Vert }_2^2+\Vert x{\Vert }_1$ (LASSO) This is equivalent to an L1-regularized least squares with $\lambda =1$. We already know from previous notes that for the regularizer term we can introduce a slack variable $u\in {\mathbb{R}}^n$, such that $-u_i\le x_i\le u_i\text{for }i=1,\dots ,n.$ Since $\Vert Ax-y{\Vert }_2^2$ is quadratic, we simply refactor the norm as $(Ax-y{)}^T(Ax-y)=x^T{A}^{T}Ax-2y^{T}Ax+y^{T}y$. As such, our objective becomes $f_1(x)=x^T{A}^{T}Ax-2y^{T}Ax+y^{T}y+1^{T}u,$ subject to the constraint above.

$f_2(x)=\Vert Ax-y{\Vert }_2^2-\Vert x{\Vert }_1$ Since $\Vert x{\Vert }_1$ is convex, it follows that $-\Vert x{\Vert }_1$ is concave. The difference of two convex functions (or equivalently the addition of convex and concave) is generally non-convex. As such, the objective function is not convex, and the problem cannot be formulated as a QP.

$f_3(x)=\Vert Ax-y{\Vert }_2^2+\Vert x{\Vert }_1^2$ We already know that $\Vert Ax-y{\Vert }_2^2=x^T{A}^{T}Ax-2y^{T}Ax+y^{T}y$. Recall that L1 norm is the sum of absolute values. From earlier, we know that it can be expressed using $1^{T}z$, where $z\in {\mathbb{R}}^n$ is a slack variable, such that $-z_i\le x_i\le z_i\text{for }i=1,\dots ,n.$ Therefore, L1 norm squared is simply $(1^{T}z{)}^2$! Our final objective function becomes $f_3(x)=x^T{A}^{T}Ax-2y^{T}Ax+y^{T}y+(1^{T}z{)}^2.$ To go one step further, let $Q\in {\mathbb{R}}^{n\times n}$, such that $Q=11^T$ (i.e., a matrix full of ones). Then, we can express the objective as $f_3(x)=x^T{A}^{T}Ax-2y^{T}Ax+y^{T}y+z^{T}Qz.$