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