Can I write this ( xy + xz +yz <1 ) as a SOCP?


(Manijeh Bashar) #1

I need to write the following equation as a SOCP:

xy + xz +yz <1

I assume to do this, I need to prove that xy + xz +yz can be written as || v ||, where v is a vector and a function of x,y,z.

Is there any way to do this? Thanks a lot in advance!

Best


(Mark L. Stone) #2

You haven’t said anything about nonnagitivity constraints, so I’ll assume there are none. The eigenvalues of the Hessian xy + xz + yz are -1, -1, 2. Therefore it is not convex (nor concave). Therefore xy + xz + yz < 1 is not a second order cone constraint, nor representable as such. It can not be entered into CVX.

Why do you “need” to write this as a second order cone constraint? BTW, professors have assigned many homework, take-home test, and thesis problems under false claims of convexity.


(Manijeh Bashar) #3

Thanks very much sir.

Actually, this is my optimization problem:

\min_{x_k,y_k} \sum_{k=1}^K x_k+y_k
s.t.
\sum_{k=1}^ K a_k x_k y_k \le (\sum_{k=1}^k b_k x_k)^2
x_k \ge 0,
y_k \ge 0,
where x_k and y_k are decision variables. Moreover, K is a positive integer number and a_k and b_k are positive values.

I can solve it by SDP. However, I want to solve it using SOCP. Is it possible to write \sum_{k=1}^ K a_k x_k y_k = || v_k||^2, where v_k is a vector? Many thanks in advance for your great help.
Really appreciate the time you put on this!

Best


(Mark L. Stone) #4

Show us your SDP formulation.


(Manijeh Bashar) #5

Dear Mark,

Thanks very much for your response. Let me consider the following optimization problem (for a given K):
and M
P_1: \min_{\{x_{mk}\}} ~~~~\sum\limits_{m=1}^{M}\sum\limits_{k=1}^K x_{mk}

s.t.

\dfrac{\left(\sum_{m=1}^M\sqrt{x_{mk}b_{mk}}\right)^2}{\sum_{k^\prime\ne k}^K\sum_{m=1}^M\sum_{n\ne m}^M \sqrt{a_{mk^\prime k}}\sqrt{a_{nk^\prime k}}\sqrt{x_{mk^\prime}}\sqrt{x_{nk^\prime}}+1} \ge 1

\sum_{m=1}^M\sum_{k=1}^K x_{mk} \le 1

x_{mk}\ge 0,

where a and b are positive numbers. This is equivalent to

P_2: \min_{\{x_{mk}\}} ~~~~\sum\limits_{m=1}^{M}\sum\limits_{k=1}^K x_{mk}

s.t.

\dfrac{\left(\sum_{m=1}^M\sqrt{x_{mk}b_{mk}}\right)^2}{\sum_{k^\prime\ne k}^K\left(\sum_{m=1}^M \sqrt{x_{mk^\prime}}\sqrt{a_{mkk^\prime}}\right)^2-\sum_{k^\prime\ne k}^K \sum_{m=1}^M x_{mk^\prime}a_{mkk^\prime}+1} \ge 1

\sum_{m=1}^M\sum_{k=1}^K x_{mk} \ge 1

x_{mk}\le 0.

Now I introduce new slack variables w_{mlk}=\sqrt{x_{mlk}}. This results in the following optimization problem:

P_3: \min_{\{w_{mk}\}} ~~~~\sum\limits_{m=1}^{M}\sum\limits_{k=1}^K \mathbf{w}_{k}

s.t.

\dfrac{\mathbf{w}_k^T \mathbf{F}_k \mathbf{w}_k}{\sum_{k^\prime\ne k}^K \mathbf{w}_{k^\prime}^T \mathbf{G}_{k} \mathbf{w}_{k^\prime}-\sum_{k^\prime\ne k}^K \mathbf{w}_{k^\prime}^T \mathbf{H}_{k} \mathbf{w}_{k^\prime}+1} \ge 1

\sum_{m=1}^M\sum_{k=1}^K w_{mk}^2 \ge 1

w_{mk}\le 0,

where \mathbf{F}_k=[b_{1k}...b_{Mk}]^T [b_{1k}...b_{Mk}], \mathbf{G}_{k^\prime}=[\sqrt{a_{1kk\prime}}...\sqrt{a_{Mkk\prime}}]^T[\sqrt{a_{1kk\prime}}...\sqrt{a_{Mkk\prime}}] and \mathbf{H}_k=\text{diag}[a_{1kk^\prime}... a_{Mkk^\prime}]
Next, I introduce the new variable \mathbf{W}_{k}=\mathbf{w}_{k}\mathbf{w}_{k}^T, which enables us to reformulate Problem P_3 into a standard SDP using semidefinite relaxation. By utilising the identity \mathbf{w}^T\mathbf{R}\mathbf{w}=\text{Tr}[\mathbf{R}\mathbf{w}\mathbf{w}^T]=\text{Tr}[\mathbf{R}\mathbf{W}], Problem P_3 can be rewritten as follows:

P_4: \min_{\{\mathbf{W}_k\}} ~~~~\sum\limits_{k=1}^K \text{Tr}(\mathbf{W}_k)

s.t.

\text{Tr} (\mathbf{F}_k\mathbf{W}_k)-\sum_{k^\prime \ne k}^K\text{Tr}(\mathbf{G}_{k^\prime}\mathbf{W}_{k^\prime})-\sum_{k^\prime\ne k}^K\text{Tr}(\mathbf{H}_{k^\prime} \mathbf{W}_{k^\prime})\ge 1

\sum_{m=1}^M\sum_{k=1}^K w_{mk}^2 \ge 1

\mathbf{W}_{k}=\mathbf{W}_{k}^T

\mathbf{W}_{lk}\succeq 0

\text{rank}[\mathbf{W}_{lk}]=1,

where \mathbf{W}_{lk}\succeq 0 means that \mathbf{W}_{lk} is a positive semidefinite matrix. By relaxing all rank-one constraints in Problem P_4, we arrive at a standard SDP.

Now, I am going to use SOCP to solve problem P_1. For this, I need to make the denominator as ||\mathbf{v}_k||^2. This is what I am not able to do!! Looking at Problem P_2 (where I re-wrote the denominator), I am NOT able to write the denominator as ||\mathbf{v}_k||^2 as follows:

\sum_{k^\prime\ne k}^K\left(\sum_{m=1}^M \sqrt{x_{mk^\prime}}\sqrt{a_{mkk^\prime}}\right)^2-\sum_{k^\prime\ne k}^K \sum_{m=1}^M x_{mk^\prime}a_{mkk^\prime}+1 \ne ||\mathbf{v}_k||^2, because there is a negative term here.

My supervisor believes there must be a way to write the denominator as ||\mathbf{v}_k|| and solve this by SOCP. However, I do not know how to do it.

I would be extremely thankful if you could please guide me, and any help would be highly appreciated. Thanks a lot in advance!


(Mark L. Stone) #6

You didn’t say anything before about needing to relax the problem to solve it as an SDP. Tthat’s why I asked to see your SDP formulation, because an SDP formulation of your original problem (but with the nonnegativity constraints) wasn’t obvious to me.

Are you willing to solve a relaxed problem as an SOCP? If you have to relax your problem to get an SDP formulation, then there can not be an SOCP formulation of the unrelaxed problem because any SOCP problem can be formulated as an SDP. You did relax to formulae an SDP, but you did not supply proof that you had to relax to produce an SDP.

I will defer to one of the MOSEK guys who visit this forum to address your SOCP formulation question, because they are much better at this kind of stuff than I am.


(Manijeh Bashar) #7

Dear Mark, Thanks very much for your hints and all the useful information.

Actually, in my code, I always see that the optimal solutions (the matrices \mathbf{W}_k) are rank-1 matrices (without including them in the optimization problem).

What I want now is solving Problem P_1 using SOCP, without any assumption.

Thanks very much for deferring my problem to one of the MOSEK guys.

I know if the denominator is like \sum_{k^\prime= 1}^K\left(\sum_{m=1}^M \sqrt{x_{mk^\prime}}\sqrt{a_{mkk^\prime}}\right)^2+1 this can be written as follows:

\sum_{k^\prime= 1}^K\left(\sum_{m=1}^M \sqrt{x_{mk^\prime}}\sqrt{a_{mkk^\prime}}\right)^2+1 =||\mathbf{v}_k||^2,

where \mathbf{v}_k = \left[\sum_{m=1}^M \sqrt{x_{m1}}\sqrt{a_{mk1}}, \sum_{m=1}^M \sqrt{x_{m2}}\sqrt{a_{mk2}},\cdots, \sum_{m=1}^M \sqrt{x_{mK}}\sqrt{a_{mkK}}, 1\right]. But I do not know how to this with the denominator in problem P_1 in my previous response. Thanks a lot in advance for your help.