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.
1 Like
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.
1 Like
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.
1 Like
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.
2 Likes
Amazing! It works now.
Really thanks for your kind help!
