A Quadratic Programming problem (QP) in the form of

\begin{aligned} & \underset{x}{\text{minimize}} & & \frac{1}{2} x^T H x + p^T x \\ & \text{subject to} \\ & & & A_{eq} x = b_{eq} \\ & & & A x \geq b \end{aligned}

where $$H \in \Re^{n \times n}, A \in \Re^{m \times n}, p, x \in \Re^n, b \in \Re^m$$, can be transformed to a Second-Order Cone Programming (SOCP) problem in the form of

\begin{aligned} & \underset{x}{\text{minimize}} & & f^T x \\ & \text{subject to} \\ & & & \left \| A_i x + b_i \right \|_2 \leq c_i^T x + d_i, \; i = 1, \ldots, m \end{aligned}

Consider $$y = \left \| F x – c \right \|$$, and

\begin{aligned} y^2 & = \left \| F x – c \right \|^2 \\ & = (F x – c)^T (F x – c) \\ & = x^T F^T F x – 2 c^T F x + c^T c \end{aligned}

As $$c^T c$$ is non-negative, minimizing $$x^T F^T F x – 2 c^T F x$$ is equivalent to minimizing $$y^2$$, and hence is equivalent to minimizing $$y$$.

If we have $$H = 2 F^T F$$ and $$p = -2 F^T c$$, then the objective function in QP $$\frac{1}{2} x^T H x + p^T x$$ can be written as $$x^T F^T F x – 2 c^T F x$$. We can thus minimize $$y$$.

Thus, the QP problem can now be written as

\begin{aligned} & \underset{y}{\text{minimize}} & & y \\ & \text{subject to} \\ & & & \left \| F x – c \right \| \leq y \\ & & & A_{eq} x = b_{eq} \\ & & & A x \geq b \end{aligned}

As $$H$$, by definition of QP, is symmetric, a symmetric $$F$$ can be found such that $$\frac{H}{2} = F^T F = F^2$$. If the QP is assumed to be a convex QP, $$H$$ is positive semidefinite, applying Cholesky factorization gives $$\frac{H}{2} = U^T U$$ (or $$L L^T$$). In this case, $$F = U$$ (or $$L^T$$).

Next, as $$\left \| \cdot \right \|_2$$ is always non-negative, the equality constraint $$A_{eq} x = b_{eq}$$ can be written as

$$\left \| A_{eq} x – b_{eq} \right \| \leq 0$$

Finally, each row in the inequality constraint $$A x \geq b$$ can be written as

$$a_i x – b_i \geq 0, \; i = 1, \ldots, m$$

where $$a_i$$ is the i-th row of $$A$$, and $$b_i$$ is the i-th element of $$b$$.

Therefore, a QP problem can be transformed to an equivalent SOCP problem in the following way. We need to introduce a few variables first.

• $$y = x_{n+1}$$
• $$c = -\frac{1}{2} F^{-T} p$$

\begin{aligned} & \underset{x}{\text{minimize}} & & f^T x \\ & \text{subject to} \\ & & & \left \| A_1 x + b_1 \right \|_2 \leq c_1^T x + d_1 \\ & & & \left \| A_2 x + b_2 \right \|_2 \leq c_2^T x + d_2 \\ & & & \left \| A_3 x + b_3 \right \|_2 \leq c_3^T x + d_3 \\ & & & \vdots \\ & & & \left \| A_{m+2} x + b_{m+2} \right \|_2 \leq c_{m+2}^T x + d_{m+2} \\ & \text{where} \\ & & f & = (0, \ldots, 0, 1)^T \\ & & x & = (x_1, \ldots, x_n, x_{n+1})^T \\ & & A_1 & = \left [ F, 0 \right ], b_1 = \frac{1}{2} F^{-T} p, c_1 = (0, \ldots, 0, 1)^T, d_1 = 0, \left (\frac{H}{2} \right ) = F^T F \\ & & A_2 & = \left [ A_{eq}, 0 \right ], b_2 = -b_{eq}, c_2 = 0, d_2 = 0 \\ & & A_{i+2} & = 0, b_{i+2} = 0, c_{i+2} = \text{the i-th row of }A, d_{i+2} = -(\text{the i-th element of }b), \; i = 1, \ldots, m \\ & & & f, x, c_1, \ldots, c_{m+2} \in \Re^{n+1} \end{aligned}

The sub-vector with the first $$n$$ elements in the solution of the transformed SOCP problem is the solution of the original QP problem.

SuanShu has implementations to solve both SOCP and QP problems.

## 1 Comment

1. […] Transforming a QP Problem to an SOCP Problem [Numerical Method] […]