How to convert a quadratic constraint into a conic section constraint (SOCP)?

118 Views Asked by At

Given an quadratic optimization program

Minimize $\sqrt{X_{1}^2 + 2X_{2}^2 + X_1X_2 - 2X_2 +1} - X_2$ such that. $X_1^2 - 4X_2\leq 3$

I need to rewrite it into an SOCP. And my thought is to introduce a slack variable, $t$ ,where $$t \geq \sqrt{X_{1}^2 + 2X_{2}^2 + X_1X_2 - 2X_2 +1}$$ And factorize $X_1$ and $X_2$ to a form that can be expressed as norm. $$t \geq \sqrt{(X_1+0.5X_2)^2 + (X_2 - 1)^2 + (\sqrt{3/4}*X_2)^2}$$ which can be expressed as $$\|AX - B\|\leq \|CX+D\|$$ But I am wondering if this way is right? Since the expression is split into 3 dimensions however $X$ only have 2 dimensions(X_1,X_2).

And I cannot rewrite the constraint into a conic section. The best I can do with the factorization is: $$X_1^2 + X_2^2 - (X_2+2)^2 \leq 1$$ Since there is a negative sign, even I can move it to the right and obtain norms on both side. But I do not know whether this is correct or it is a standard form of SOCP.

Thank you for helping me~

1

There are 1 best solutions below

0
On

Since my comment received an upvote, I assume it addressed the question. For completeness, let me organize the comments into an answer.

In short, you've pretty much answered the question yourself. Here are the details:

First, let's agree on the definition of SOCP (second-order cone program). I use the definition given in https://inst.eecs.berkeley.edu/~ee127/sp21/livebook/l_socp_standard.html

$$\begin{align*} \text{minimize}_{x \in \mathbb{R}^n} & \quad f^T x\\ \text{subject to} & \quad \|A_i x + b_i\| \leq c_i^T x + d_i, \quad i = 1, \dots, m \end{align*}$$

Here, $A_i \in \mathbb{R}^{p_i \times n}$, $b_i \in \mathbb{R}^{p_i}$, $c_i \in \mathbb{R}^n$, $d_i \in \mathbb{R}$.

To reformulate your problem as SOCP, proceed exactly as you did: Introduce a new variable $t$ and reformulate the problem as $$\begin{align*} \text{minimize}_{X_1, X_2, t \in \mathbb{R}} & \quad t\\ \text{subject to} & \quad \sqrt{X_1^2 + 2X_2^2 + X_1 X_2 - 2X_2 + 1} - X_2 \leq t\\ & \quad X_1^2 - 4X_2 \leq 3 \end{align*}$$ This optimization problem has three variables $X_1, X_2, t$. For convenience, let's write $Y = \begin{pmatrix} X_1\\ X_2\\ t \end{pmatrix} \in \mathbb{R}^3$. The objective function $t$ is already in the desired form $f^T Y$, where $f = \begin{pmatrix} 0\\ 0\\ 1 \end{pmatrix}$. It remains to write each of the two constraints in the form $\|A Y + b\| \leq c^T Y + d$.

For the first constraint, as you already observed, $\sqrt{X_1^2 + 2X_2^2 + X_1 X_2 - 2X_1 + 1} = \sqrt{ (X_1 + 0.5X_2)^2 + (X_2 - 1)^2 + (\sqrt{3/4} X_2)^2 }$. Going one step further, this expression equals $\Big\| \begin{pmatrix} X_1 + 0.5X_2\\ X_2 - 1\\ \sqrt{3/4} X_2 \end{pmatrix} \Big\|$. So the constraint $\sqrt{X_1^2 + 2X_2^2 + X_1 X_2 - 2X_2 + 1} - X_2 \leq t$ is equivalent to $\Big\| \begin{pmatrix} X_1 + 0.5X_2\\ X_2 - 1\\ \sqrt{3/4} X_2 \end{pmatrix} \Big\| \leq X_2 + t$. It is of the form $\|AY + b\| \leq c^T Y + d$, where $A = \begin{pmatrix} 1 & 0.5 & 0\\ 0 & 1 & 0\\ 0 & \sqrt{3/4} & 0 \end{pmatrix}$, $b = \begin{pmatrix} 0\\ -1\\ 0 \end{pmatrix}$, $c = \begin{pmatrix} 0\\ 1\\ 1 \end{pmatrix}$, $d = 0$.

For the second constraint $X_1^2 - 4X_2 \leq 3$, write it as $X_1^2 \leq 4X_2 + 3$. To turn it into the form $\|AY + b\| \leq c^T Y + d$, we use the following trick (see https://inst.eecs.berkeley.edu/~ee127/sp21/livebook/l_socp_soc.html):

Basically, if $\mathbf{w} \in \mathbb{R}^n$, $u, v \in \mathbb{R}$, then $\mathbf{w}^T \mathbf{w} \leq uv, u \geq 0, v \geq 0$ $\Leftrightarrow \Big\|\begin{pmatrix} 2\mathbf{w}\\ u - v \end{pmatrix}\Big\| \leq u + v$. You can verify the equivalence by directly squaring both sides.

In our case, $\mathbf{w} = X_1$, $u = 4X_2 + 3$, $v = 1$. So constraint $X_1^2 \leq 4X_2 + 3$ is equivalent to $\Big\| \begin{pmatrix} 2X_1\\ 4X_2 + 3 - 1 \end{pmatrix} \Big\| \leq 4X_2 + 3 + 1$. Now this constraint is in the form $\|AY + b\| \leq c^T Y + d$. Here, $A = \begin{pmatrix} 2 & 0 & 0\\ 0 & 4 & 0\\ \end{pmatrix}$, $b = \begin{pmatrix} 0\\ 2 \end{pmatrix}$, $c = \begin{pmatrix} 0\\ 4\\ 0 \end{pmatrix}$, $d = 4$.

Let me know if this fully answers your question.