Second Order Cone Program with Quadratic Objective Function

171 Views Asked by At

The standard form for a Second Order Cone Program (SOCP) is

\begin{equation} \begin{array}{c} \min _{x} f^{T} x \\ \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m \end{array} \end{equation}

where $ A_{i} \in \mathbb{R}^{k_{i} \times n}, b_{i} \in \mathbb{R}^{k_{i}}, c_{i} \in \mathbb{R}^{n} \text { and } d_{i} \in \mathbb{R}$.

If the objective is quadratic instead we have

\begin{equation} \begin{array}{c} \min _{x} x^{T}\Sigma x + f^Tx \\ \left\|A_{i} x+b_{i}\right\|_{2} \leq c_{i}^{T} x+d_{i}, i=1, \ldots, m \end{array} \end{equation}

Can someone help me how can I reformulation this to SCOP. I found this link https://docs.mosek.com/modeling-cookbook/cqo.html#sec-cqo-modeling-qset where they state that

Assume $Q \in \mathbb{R}^{n \times n}$ is a symmetric positive semidefinite matrix. The convex inequality $$ (1 / 2) x^{T} Q x+c^{T} x+r \leq 0 $$ may be rewritten as $$ \begin{aligned} t+c^{T} x+r &=0 \\ x^{T} Q x & \leq 2 t. \end{aligned} $$ Can someone help me with what exactly t is?

e.g. I have $Q = \begin{bmatrix} 2 & 0 \\ 0& 2 \\ \end{bmatrix}$, $c =\begin{bmatrix} 2 \\ 2 \\ \end{bmatrix}$ and $r = 0$, how can I rewrite this?

1

There are 1 best solutions below

0
On BEST ANSWER

Define $t=-c^Tx-r.$ Then clearly $t+c^Tx+r=0$ and $$\frac{1}{2}x^TQx-t=\frac{1}{2}x^TQx+c^Tx+r\leq 0$$ implies $$ x^TQx\leq 2t. $$ We are adding an extra variable ("$t$") together with an extra equation to constrain that variable. Rewriting your equation we get the two equations $$ t+\begin{bmatrix}2 & 2 \end{bmatrix}x=0 $$ and $$ x^T \begin{bmatrix}2 & 0 \\ 0 & 2\end{bmatrix}x\leq 2t. $$ If $x=(x_1,x_2)$ then these equations are $$ t+2x_1+2x_2=0 $$ and $$ 2x_1^2+2x_2^2\leq 2t. $$