How to solve this optimization problem? Thanks!


(Manijeh Bashar) #1

How to solve this optimization problem:

\min_{x_{ij}} x_{11}+x_{12}+x_{13}+x_{21}+x_{22}+x_{23}
s.t.
a_1 x_{12}x_{22}+a_2x_{12}x_{32}+a_3x_{22}x_{32}+\\b_1x_{11}^2+b_2x_{21}^2+b_3x_{31}^2+c_1x_{12}^2+c_2x_{22}^2+c_3x_{32}^2 \le\\\left(d_1x_{11}+d_2x_{21}+d_3x_{31}\right)^2,,
0 \le x_{ij}\le 1, \forall i,j,

where a_{i},b_{i},c_i, and d_i are positive real numbers.
Thanks a lot for your help in advance!


(Mark L. Stone) #2

Take the square root of both sides of the constraint, which you can do because all parameters and variables are nonnegative. Express the left hand side using norm, which makes this a SOCP.

For instance, if a, b, c, d, e, f, x, y, z are all >= 0
a*x^2 + b*y^2 + c*z^2 <= (d*x + e*y + f*z)^2
can be entered in CVX as
norm([sqrt(a)*x; sqrt(b)*y; sqrt(c)*z]) <= d*x + e*y + f*z

Edit: I missed the first line of the constraint, so this doesn’t solve the OP’s problem.


(Manijeh Bashar) #3

Dear Mark, Thanks very much for your response and the kind help.

But what should I do with the term A= a_1 x_{12}x_{22}+a_2x_{12}x_{32}+a_3x_{22}x_{32} in the first constraint? The term A does not let me write the constraint as a norm, and use SOCP. I can do what you said if term A is not there! Is this right? :frowning: Thanks a lot in advance!


(Mark L. Stone) #4

Whoops, I missed the first line of the constraint.

How have you proven this constraint is convex? Why isn't CVX accepting my model? READ THIS FIRST! Can you complete a square? it will be marked non-convex until such time as you (or someone else) proves otherwise.


(Manijeh Bashar) #5

Thanks very much Mark. Let me consider a_1=a_2=a_3=1, Hence, for the first line of the constraint we have:

A=x_{12}x_{22}+x_{12}x_{32}+x_{22}x_{32}=\frac{1}{2}(x_{12}+x_{22}+x_{32})^2-\frac{1}{2}(x_{12}+x_{22}+x_{32}). Now, I completed a square. However, there is a negative term, which does not allow me to use SOCP.

I think I cannot take the term -\frac{1}{2}(x_{12}+x_{22}+x_{32}) to other side of the equation and use SOCP. Is this possible?
So, should I find another way to complete a square for the term A=x_{12}x_{22}+x_{12}x_{32}+x_{22}x_{32}? Thanks very much!


(Mark L. Stone) #6

Your approach does not work. To get the RHS affine, you must take square root of LHS. So you need to complete the square on the entire LHS, which your approach does not do.


(Manijeh Bashar) #7

thanks a lot Mark for the kind help and the useful information.

So, I need to make the term A=x_{12}x_{22}+x_{12}x_{32}+x_{22}x_{32} square somehow without any negative term?!

Thanks a lot!


(Mark L. Stone) #8

The entire LHS needs to be a square.


(Manijeh Bashar) #9

Thanks a lot Mark for the time you spent on this and the kind help.