Dealing with a square root of a quadratic constraint. (RMosek)

[kimm...@gmail.com]

Hi I'm having trouble solving this optimization problem.

The only problem  is that I don't know how to transform the constraint with the square root into a conic optimization problem. ((x^T Σ x)^(1/2) is a convex function.)

 By using this form

and from here to

and from here to

Thanks ! 

[Erling D. Andersen]

Your problem is

max  .... -x^T Q x

st .... >= sqrt(x^TQx)

I skipped all the linear stuff you can add as you want. Q=\Sigma.

Assume you know L such that

Q=LL^T

then

min ... - u

st.  ...  >= t

      L^T x - y = 0

      t >= ||y||        (This is a quadratic cone)

      t-w=0

      2*u*v >= t^2   (3 dimensional rotated cone)

      v=0.5       

Given Q is positive semidefinite then a L exists. See

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

for details. Plenty of relevant info. can be located in our modelling cookbook at

   https://mosek.com/resources/doc

[kimm...@gmail.com]

Thank you for the quick answer ! 

Yes my Q matrix is positive definite. I've tried all day getting this to work but I don't know what I'm doing wrong. 

Here's the code I'm using 


prob <- list() #(x1,...,xN, u, t,y1,..,yN,v, w) variables

L <- t(chol(Q)) 
n <- nrow(L)

c <- c(rep(0,n), -1,0, rep(0,n), 0, 0)                                                                     # -u

prob$c <- c

A1 <- Matrix(c(rep(0,n),0,-1,rep(0,n),0,0), nrow = 1 , sparse = TRUE)                    # -t

A2 <-  Matrix(cBind(L,   rep(0 , n ),rep(0 , n ) , −diag ( n ), rep(0 , n ) ,rep(0 , n ) ))  # L^T x - y

A3 <- Matrix(c(rep(0,n),0,1,rep(0,n),0,-1), nrow = 1, sparse = TRUE)                     # t-w 

A <- rBind(A1,A2,A3)

prob$A <- A

prob$sense <- "min"

bl <- c(rep(0,n+2))                      

bu <- c(Inf, rep(0,n+1))

bc <- rBind(bl,bu)    -t >= 0,  L^T x - y  = 0,  t-w = 0

prob$bc <- bc

bx1 <-  matrix ( c(−Inf ,  Inf ) , nrow=2, ncol=n)

bx2 <- matrix ( c(-Inf, 0 ), nrow =2 )

bx3 <- matrix ( c(-Inf, Inf ), nrow =2 )

bx4 <-  matrix ( c(−Inf ,  Inf ) , nrow=2, ncol=n)

bx5 <- matrix ( c(0.5 ,  0.5 ), nrow =2 ) 

bx6 <- matrix ( c(-Inf ,  Inf ), nrow =2 ) 

bx <- cBind(bx1, bx2 ,bx3, bx4, bx5, bx6) #  Inf > x1,...,xN, t, y1,...,yN  , w  > -Inf ,  v = 0.5 , 0 >= u  > -Inf

prob$bx <- bx 

cones <- cBind(

  list('QUAD',(n+2):(n+2+n)),                     # t >= ||y||        

  list ("RQUAD", c(n + 1 , 2*n + 1, n + 2)   #  2u*v >= t^2

))

prob$cones <- cones

mosek(prob)

It gives me an error 1302...

Thanks.

[Erling D. Andersen]

Now if you search for that response at

    http://docs.mosek.com/7.1/capi/Response_codes.html

you see it says

    A new cone which variables overlap with an existing cone has been specified.

Assume you have added the cone

    (x,y,z)

then you can add another cone

   (z,f,g)

I.e. a  variable can ONLY be member of one cone. But you can do

     h=z

    (x,y,z)

   (h,f,g)

so  you had an additional linear constraint h=z. ANd then use h instead of z in the second cone.

[kimm...@gmail.com]

Okay hopefully I have understood it correctly now, this formulation with these variables (x = (x1,...,xN), y = (y1,...,yN), u,t,v,w)

min ... - u                                                               

st.  ...  >= t

      L^T x - y = 0

      t >= ||y||        (This is a quadratic cone)

      t-w=0

      2*u*v >= w^2   (3 dimensional rotated cone)

      v=0.5  

is correct and equal to this. (x = (x1,...,xN))

max  .... -x^T Q x

st .... >= sqrt(x^TQx)

Really appreciate your help ! Thanks again.

[Erling D. Andersen]

That looks fine.

[kimm...@gmail.com]

I don't know what I'm doing wrong, the problem is in fact solvable. I'm using the same expected return and covariance from the portfolio optimization example. But this is what the solver says

Problem status  : DUAL_INFEASIBLE

Solution status : DUAL_INFEASIBLE_CER

and here is the odf file

[hints]

  [hint NUMVAR] 10 [/hint]

  [hint NUMCON] 6 [/hint]

  [hint NUMANZ] 18 [/hint]

  [hint NUMQNZ] 0 [/hint]

  [hint NUMCONE] 2 [/hint]

[/hints]

[variables disallow_new_variables]

  x0000 x0001 x0002 x0003 x0004 

  x0005 x0006 x0007 x0008 x0009 

[/variables]

[objective minimize]

   - 1.073e-001 x0000 - 7.37e-002 x0001 - 6.270000000000001e-002 x0002 - x0006

[/objective]

[constraints]

  [con c0000]  x0000 + x0001 + x0002 = 1e+000 [/con]

  [con c0001] 0e+000 <= - 1.073e-001 x0000 - 7.37e-002 x0001 - 6.270000000000001e-002 x0002 - x0007 [/con]

  [con c0002]  1.666733332000053e-001 x0000 - x0003 = 0e+000 [/con]

  [con c0003]  2.321907125572429e-002 x0000 + 1.028633789549109e-001 x0001 - x0004 = 0e+000 [/con]

  [con c0004]  1.259949603023798e-003 x0000 - 2.228731565504209e-003 x0001 + 3.381486777449774e-002 x0002 - x0005 = 0e+000 [/con]

  [con c0005]  x0007 - x0009 = 0e+000 [/con]

[/constraints]

[bounds]

  [b]          0 <= * [/b]

  [b]               x0000,x0001,x0002,x0003,x0004,x0005 free [/b]

  [b]               x0007 free [/b]

  [b]               x0008 =  5e-001 [/b]

  [b]               x0009 free [/b]

  [cone quad k0000] x0007, x0003, x0004, x0005 [/cone]

  [cone rquad k0001] x0006, x0008, x0009 [/cone]

[/bounds]

[Erling D. Andersen]

You are minimizing. Is that the intention?  

Well, your problem is unbounded given the problem has feasible solution.

[kimm...@gmail.com]

Hi again. To clarify the problem I want to maximize the objective function and get the optimal weights for x

               

   '

(x^T \Sigma x)^(1/2) is a convex function, proven here:

So therefore we are still in the region of convex optimization.

There is a global optimum, proven here

Then I used the model that you presented:

min ... - u

st.  ...  >= t

      L^T x - y = 0

      t >= ||y||        (This is a quadratic cone)

      t-w=0

      2*u*v >= t^2   (3 dimensional rotated cone)

      v=0.5       

And added the linear constraints

min  - \lamda*(\mu + \gamma)^T x  - u

st.  1/2*\mu^T x - \zeta * t  >= c      (c is a constant that can be negative and positive) (\zeta is always positive)

      e^T x = 1

      L^T x - y = 0

      t >= ||y||        (This is a quadratic cone)

      t-w=0

      2*u*v >= t^2   (3 dimensional rotated cone)

      v=0.5       

Thanks !

[Erling D. Andersen]

A minus in front of u looks strange.

--
You received this message because you are subscribed to a topic in the Google Groups "mosek" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/mosek/wNwNFU-iWEA/unsubscribe.
To unsubscribe from this group and all its topics, 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.

[kimm...@gmail.com]

Aaah of course you are totally right. I got it finally working, thanks again