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.

## 30 Comments

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

How to make money online – earnings with investment https://sites.google.com/view/site-for-investing-in-bitcoin/how-to-make-money-online-earnings-with-investment

Delta Airlines Phone Number | Delta airlines customer service phone number https://www.pinterest.com/pin/1071153092593253744/

Delta Airlines Phone Number | Delta airlines customer service phone number https://telegra.ph/Delta-Airlines-Manage-Booking–18556702491-10-01

Delta Air lines Colorado Springs. Arizona booking customer service customer service phone number https://delta-airlines-2022.blogspot.com

control of pest Fort Worth service https://sdachurch.com/?s=control+of+pest+%E2%98%8E+1%28844%299484793+Fort Worth+service+phone+number

control of pest New Hampshire service https://111.wales.nhs.uk/localservices/viewlocalservice.aspx?s=control+of+pest+%E2%98%8E+1%28844%299484793+New Hampshire+service+phone+number

control of pest Fort Worth service https://www.craftstorming.com/?s=control+of+pest+%E2%98%8E+1%28844%299484793+Fort Worth+service+phone+number

control of pest San Jose service https://www.goodcarbadcar.net/?s=control+of+pest+%E2%98%8E+1%28844%299484793+San Jose+service+phone+number

control of pest AK service https://www.densetsugames.com.br/?s=control+of+pest+%E2%98%8E+1%28844%299484793+AK+service+phone+number

control of pest San Diego service https://www.webdesignerdepot.com/?s=control+of+pest+%E2%98%8E+1%28844%299484793+San Diego+service+phone+number

flight+club+phone+number+ny Washington service https://auntie.tw/?s=%E2%98%8E+1%28888%294972988+flight+club+phone+number+ny

https://www.google.com/travel/flights?tfs=Delta+airlines%F0%9F%93%9E+1+855-670-2491+book+a+flight

Delta Air lines Louisiana booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

Delta Air lines MS booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

Delta Air lines Ohio booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

Delta Air lines Miami booking flight service https://search.yahoo.com/tablet/s?p=Delta+airlines+1+855-670-2491+book+a+flight&ei=UTF-8&age=1m&fr2=time&btf=m

Веном 2 – смотреть онлайн в хорошем качестве https://bit.ly/venom2-2021

Иван Грозный – смотреть онлайн в хорошем качестве https://bit.ly/ivan_groznii

Дракулов 2021 – 2021 смотреть онлайн в хорошем качестве

Thank you this method worked after I followed step 1 to the end. Indira Matthaeus Aloise

Thanks again for the article. Much thanks again. Really Cool. Matti Fransisco Cullin

I got what you mean,saved to fav, very nice website. Cate Kane Fortuna

Transforming a QP Problem to an SOCP Problem | Certified Quantitative Analyst

aqceifdzhjq

[url=http://www.g48837359dp91xtibjjs50at0h4rxt58s.org/]uqceifdzhjq[/url]

qceifdzhjq http://www.g48837359dp91xtibjjs50at0h4rxt58s.org/

Great content! Keep up the good work!

Hi there just wanted to give you a quick heads up.

The text in your content seem to be running off the screen in Internet explorer.

I’m not sure if this is a format issue or something to do with browser compatibility

but I figured I’d post to let you know. The design and style look great though!

Hope you get the issue resolved soon. Many thanks

Below youll discover the link to some internet sites that we consider it is best to visit.

Wonderful story, reckoned we could combine a handful of unrelated data, nevertheless seriously worth taking a look, whoa did a single learn about Mid East has got a lot more problerms as well

that is the finish of this write-up. Right here youll uncover some web-sites that we feel youll value, just click the links over

Every when in a while we choose blogs that we read. Listed beneath would be the most recent web-sites that we decide on