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.
This is addressed in the CVX Users’ Guide http://cvxr.com/cvx/doc/sdp.html .
[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
q=[1,2,3];
cvx_begin sdp
variable x(3)
X=xx’; % matrix X
minimize 1+qx
subject to
[X x;x’ 1] == semidefinite(4); % constraint (C2)
cvx_end
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.
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];
cvx_begin
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)
cvx_end
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.
Alternatively,
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)
cvx_end
which produces the same result.
Amazing! It works now.
Really thanks for your kind help!
