Hello,
I want to access my dual variable for an SDP problem that I’ve solved. I understand this is possible, but I am a little confused about how to do it.
My primal problem is \min c^Tx \text{ s.t. } F(x)\succeq 0, so the corresponding dual problem is \max -\text{tr}(F_0Z) \text{ s.t. } \text{tr}(F_iZ)=c_i, Z \succeq 0 (Ref).
So how do I extract the dual variable Z?
CVX executes this without error message. Does it do “the right thing”?
cvx_begin sdp
variable X(3,3) symmetric
dual variable y
minimize(trace(X))
X - eye(3) >= 0 : y
cvx_end
disp(y)
(1,1) 1
(2,2) 1
(3,3) 1
CVX does not appear to accept
X - eye(3) == semidefinite3) : y
So it appears that sdp mode is needed in order to get dual variables for SDP constraints, but I don’t believe is documented
Thanks @Mark_L_Stone
In this case, what does the following mean? Could you explain it in words?
X - eye(3) >= 0 : y
Also, maybe I am not understanding completely, but this is in a different form than what I am trying. My primal problem is what I put in CVX (see below). I can solve this, which CVX does by solving the primal and the dual. Since, both the primal and the dual problem are solved, how can I extract the corresponding dual variable?
% create the matrices
F0 = [0.2034 -0.2976 -0.1091 0 0 0;
-0.2976 0.2455 -0.1935 0 0 0;
-0.1091 -0.1935 0.0137 0 0 0;
0 0 0 1.0000 0 0;
0 0 0 0 1.0000 0;
0 0 0 0 0 0];
F1 =[2 1 1 0 0 0;
1 0 0 0 0 0;
1 0 0 0 0 0;
0 0 0 0 0 1;
0 0 0 0 0 0;
0 0 0 1 0 0];
F2 =[0 1 0 0 0 0;
1 2 1 0 0 0;
0 1 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 1;
0 0 0 0 1 0];
F3 =[0 0 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 0;
0 0 0 0 0 1];
% solve
cvx_begin sdp
variables x(3)
% objective
minimize x(3)
subject to:
F0 + x(1)*F1 + x(2)*F2 + x(3)*F3 >= 1e-6*eye(6)
cvx_end
My example specifies a semidefinite constraint, X - eye(3) >= 0, and assigns the dual variable,y, to it, which is a matrix of the same dimension as the semidefinite constraint.
I am not the expert on what this means, or whether it makes sense. But it gets CVX to do something. However dual variables for semidefinite constraints are not explicitly addressed in the CVX Users’ Guide or help.
Well your intuition is good! I tried this approach as follows
% solve
cvx_begin sdp
variables x(3)
dual variable Z
% objective
minimize x(3)
subject to:
F0 + x(1)*F1 + x(2)*F2 + x(3)*F3 >= 1e-6*eye(6) : Z
cvx_end
And was able to confirm the result
\min c^Tx = \max - \text{tr}(F_0Z),
\text{tr}(F_iZ)=c_i, Z \succeq 0
Do you know is there a way I can recommend this as a change to the documentation or do it myself with some “pull request” type approach?
The most recent build of CVX and it documentation is from Jan 2020. CVX is not under active development, nor is its documentation (except for what gets posted on this forum, which is not official documentation). Perhaps at some point, other people will be allowed to develop CVX, but this has not yet happened, and might not ever happen, with the limited exception of a CVX for Apple Silicon build.
There is some about semidefinite duals here:
http://cvxr.com/cvx/doc/sdp.html
Quote: “A dual variable, if supplied, will be applied to the converted equality constraint. It will be given a positive semidefinite value if an optimal point is found.”
It sort of follows from general abstract nonsense that the dual of a PSD constraint must be what you’d expect, so maybe that’s why it is only mentioned in passing.
See 8 Duality in conic optimization — MOSEK Modeling Cookbook 3.3.0 if in doubt.
Mea culpa…
On the other hand, the example in the CVX User’s Guide with the form
Z == hermitian_semidefinite( n ) : Q;
produces an error for me, but does work using >= in sdp mode. So ti does appear that either documentation is wrong, or there is a bug in CVX, depending on how you look at it.