How can I solve this SOCP problem using MOSEK

[amir.sal...@gmail.com]

I would like to solve the following optimization problem using MOSEK. It is known as the Second Order Cone Programming. Without the first constraint, solving this problem by MOSEK is easy, but by adding the first constraint, which includes 2 multiplied variables (αi × αj), I can’t solve it because I did not find a section in the MOSEK help about solving problems with nonlinear constraints including multiplied variables. Please guide me about how I can formulate the first constraint in MOSEK.

[Erling D. Andersen]

Is the funktion under the square root a quadratic function? If yes it is then convex I.e. is  the Hessian positive semidefinite?

Den 26. maj 2016 7.52 PM skrev <amir.sal...@gmail.com>:

I would like to solve the following optimization problem using MOSEK. It is known as the Second Order Cone Programming. Without the first constraint, solving this problem by MOSEK is easy, but by adding the first constraint, which includes 2 multiplied variables (αi × αj), I can’t solve it because I did not find a section in the MOSEK help about solving problems with nonlinear constraints including multiplied variables. Please guide me about how I can formulate the first constraint in MOSEK.

--
You received this message because you are subscribed to the Google Groups "mosek" group.
To unsubscribe from this group and stop receiving emails from it, send an email to mosek+un...@googlegroups.com.
To post to this group, send email to mo...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Henrik Alsing Friberg]

If the dot in (x_i * x_j) is just a standard product then the double summation under the squareroot just equals

( \sum_{i=1}^l { \alpha_i y_i x_i } )^2

and then you get a two-dimensional quadratic cone w_1 \geq \sqrt{ w_2^2 } with

w_1 = \sum_{i=1}^l { r_i \alpha_i } - \gamma
w_2 = \sum_{i=1}^l { \alpha_i y_i x_i }

The two-dimensional quadratic cone is linearly representable since \sqrt{ w_2^2 } is just the absolute value of w_2..

[amir.sal...@gmail.com]

yes, H(i,j) is  the Hessian matrix defined as y(i) * y(j) * x(i) . x(j)
Therefore the function under square root can be displayed as : Sigma( Sigma (alpha (i) * alpha (j) * H(i,j)) that H is a symmetric matrix with L*L dimension. 

[Erling D. Andersen]

Assume you have

   sqrt(x^TQx) + ax+b <= 0 (*)

where Q is positive semidefinite and x is the variables. Therefor there is a matrix L so

  Q=LL^T 

Now (*) is equivalent to

t+ax+b=0

L^T x - y = 0

||y|| <= t

This should help doing the translation.

[amir.sal...@gmail.com]

Mr. Andersen, thanks for your answers, but I am somewhat confused especially by the last parts of your answers. Can I ask you to explain again with more details?
Actually I did not understand how can I account the part of the SQRT that variables alpha(i) and alpha(j) are multiplied together.

[Erling D. Andersen]

Note my x and y is not related to x and y. It is a pain to alpha as variable names when you do not write in LaTex so I use x for variables.

So you have

t+ax+b=0

L^T x - y = 0

||y|| <= t

<=>

t+ax+b=0

||L^T x|| <= t

<=>

||L^T x|| +ax+b <= 0

Now

sqrt(x^TQx) = sqrt(x^T L L^T x)  = ||L^Tx||^2 = ||L^T x|| 

That should explain it.

[Erling D. Andersen]

It should have been

sqrt(x^TQx) = sqrt(x^T L L^T x)  = sqrt(||L^Tx||^2) = ||L^T x|| 

and then you end with

sqrt(x^TQx) + ax + b <= 0

[amir.sal...@gmail.com]

thank you again Mr. Anderson. I apologize for the successive questions.

I think that you assume alpha (or x) under SQRT are the same variables. Am I right?

But we have 2 different variables namely alpha(i) and alpha(j). for example when L=100, we have 100 alpha as alpha(1), alpha(2),..., alpha(100).

Therefore we can,t write sqrt(x^TQx) because 2 variables x are not the same.

[Erling D. Andersen]

I assumed alpha was a vector i.e. a vector in R^L. And hence you had a quadratic function over alpha under the square root. I.e. you had

  sqrt(f(alpha))

where f() is a function that maps R^L into R^1 and f() is a quadratic function. And if f(alpha) is convex then my idea works.

I think the your problem is your think about the scalar terms in the sum. That will not work. You have to think about it in vector terms and then figure out what Q is. Try take L=1 and then  L=2 and figure out Q is for some concrete data of x and y.

[amir.sal...@gmail.com]

Thanks Mr. Anderson. I understand what you mean. It seems that we need matrix L in Q=LL^T that it can be obtained by MATLAB function "cholcov" . Now there is an another question: Can I solve this optimization problem by "mosekopt"? I would be grateful if you guide me about the best way to solve this problem.

[Erling D. Andersen]

May I suggest you read the toolbox manual

   http://docs.mosek.com/7.1/toolbox/index.html

and in particular Section 9.6.

[amir.sal...@gmail.com]

I really thank you for your patience in answering my questions.
I have read this manual several times, but there is still some ambiguities. The examples of manual are quite clear but I can't reformulate my first constraint to MOSEK format.

I have an another question about " sqrt(x^TQx) = ||L^T x|| " . At this quotation, L can be a vector instead a matrix??? Because using function "cholcov" in MATLAB, L is obtained as a matrix. L in the matrix form makes difficult to write the first constraint (of my optimization problem) in mosek format, while if L was a vector, I think it is easier. If it can be possible, what function in MATLAB can do it??

[Erling D. Andersen]

I do not understand what you mean.

I think you can benefit from reading

  http://docs.mosek.com/whitepapers/qmodel.pdf

[rockefe...@gmail.com]

Hi,

Could you please explain if it's a good idea to solve this guy's model via nlp, e.g. ipopt?

I also tried some qcqp examples and it seems ipopt is pretty fast.

Best, M.

On Monday, May 30, 2016 at 6:43:31 AM UTC+1, Erling D. Andersen wrote:

I do not understand what you mean.

I think you can benefit from reading

  http://docs.mosek.com/whitepapers/qmodel.pdf

[edadk]

We can only recommend mosek.