Can some please help me on this SDP problem? Thanks


I got an optimization problem, as shown like this

The variable is x, and the matrix X=xx^T. I am really confused on how to programme the constraint (C2).

For example, I assume that the variable x is a three-elements vector and specify it as
variable x(3)
and then specify the matrix X=xx^T. The objective is quite linear, and the constraint (C1) is also easy to build. But I got no idea on the second constraint (C2), how to program it? Can someone help me on this? Thanks very much for your kind help.

(Mark L. Stone) #2

This is addressed in the CVX Users’ Guide .

[X x;x' 1] == semidefinite(4)

or if using SDP mode

[X x;x' 1] >= 0

Note that you have not modeled X = x*x’ . Constraint C2 is a semidefinite relaxation of that.

Note that I have removed the TFOCS designation from the thread. If you really want to solve this problem using TFOCS rather than CVX, please say so.


Hi Mark, really thanks for your kind help! I tried to program it in Matlab like this

cvx_begin sdp
variable x(3)
X=xx’; % matrix X
minimize 1+q
subject to
[X x;x’ 1] == semidefinite(4); % constraint (C2)

Unfortunately, a waring " Only scalar quadratic forms can be specified in CVX" always returned. Is there any mistake when I define matrix X? Thanks for your kind reply.

(Mark L. Stone) #4

You are not “supposed to” use X= x*x’. Constraint C2 is a semidefinite relaxation of it, and that is what you should enter. You will have to determine whether this is the model you want. Alternatively, if X is input data rather than an optimization (CVX) variable, you need to remove the declaration of X(3,3) as being a variable.

    P1 = randn(3,3); P1 = P1*P1'; % I made up some data
    r1 = 0; % I made up some data
    q = [1,2,3];
    variables X(3,3) x(3,1)
    minimize 1+ q*x
    subject to
    trace(X*P1) + q*x + r1 <= 0
    [X x;x' 1] == semidefinite(4); % constraint (C2)

which produced

Calling SDPT3 4.0: 11 variables, 2 equality constraints

 num. of constraints =  2
 dim. of sdp    var  =  4,   num. of sdp  blk  =  1
 dim. of linear var  =  1
   SDPT3: Infeasible path-following algorithms
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
 0|0.000|0.000|1.3e+02|1.3e+01|1.0e+03| 0.000000e+00  0.000000e+00| 0:0:00| chol  1  1 
 1|0.864|0.996|1.7e+01|1.1e-01|9.1e+01|-3.949596e+00 -1.895868e+01| 0:0:00| chol  1  1 
 2|1.000|1.000|9.2e-08|6.1e-03|6.1e+00|-3.872070e+00 -9.961497e+00| 0:0:00| chol  1  1 
 3|0.910|1.000|2.2e-08|6.1e-04|1.4e+00|-5.739227e+00 -7.176243e+00| 0:0:00| chol  1  1 
 4|1.000|1.000|6.1e-09|6.1e-05|3.0e-01|-6.293679e+00 -6.591130e+00| 0:0:00| chol  1  1 
 5|0.975|0.983|2.5e-10|7.1e-06|6.6e-03|-6.458643e+00 -6.465075e+00| 0:0:00| chol  1  1 
 6|0.964|0.984|1.2e-11|7.2e-07|2.9e-04|-6.462935e+00 -6.463211e+00| 0:0:00| chol  1  1 
 7|1.000|1.000|1.0e-10|2.4e-12|2.4e-05|-6.463152e+00 -6.463177e+00| 0:0:00| chol  1  1 
 8|0.964|0.984|1.5e-10|3.7e-12|8.1e-07|-6.463171e+00 -6.463172e+00| 0:0:00| chol  1  1 
 9|1.000|1.000|6.8e-10|5.5e-12|1.6e-07|-6.463172e+00 -6.463172e+00| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
 number of iterations   =  9
 primal objective value = -6.46317150e+00
 dual   objective value = -6.46317166e+00
 gap := trace(XZ)       = 1.61e-07
 relative gap           = 1.16e-08
 actual relative gap    = 1.15e-08
 rel. primal infeas (scaled problem)   = 6.84e-10
 rel. dual     "        "       "      = 5.49e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 1.2e+01, 6.5e+00, 2.3e+01
 norm(A), norm(b), norm(C) = 2.3e+01, 2.0e+00, 3.6e+00
 Total CPU time (secs)  = 0.45  
 CPU time per iteration = 0.05  
 termination code       =  0
 DIMACS: 6.8e-10  0.0e+00  8.0e-12  0.0e+00  1.1e-08  1.2e-08
Status: Solved
Optimal value (cvx_optval): -5.46317

Of course, the solution obtained depends on the random value of P which was generated.


cvx_begin sdp
variables X(3,3) x(3,1)
minimize 1 + q*x
subject to
trace(X*P1) + q*x + r1 <= 0
[X x;x' 1] >= 0; % constraint (C2)

which produces the same result.


Amazing! It works now.
Really thanks for your kind help!:smile_cat: