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.

Recommended Posts

1 Comment


Add a Comment

Your email address will not be published. Required fields are marked *