Hi,
I am completely new to CVX. I have an optimization problem which I solved through semidefinite relaxation method (SDR) and comes up with the solution given in figure![SDR_problem|667x500]!
I have to solve this problem using CVX.
The code is below
n=100;
K=6;
sigma=-114;
cvx_begin
variables V(n,n) z
minimize z
subject to
for k=1:K
trace(A(:,:,k)*X) >= z*sigma^2 ;
end
diag(V) == ones(n,1);
X == semidefinite(n);
cvx_end
Now the issue is in order to make the initial problem relaxed i introduced “z” as a slacked variable. I am not understanding how this z will be tackled in code.
I suppose you mean to have V instead of X in two places in your code (you never even declare X or set it as an expression).
I don’t really understand your problem, but in the SDR, generally you would be replacing V == v*v', which is non-convex, with [V v;v' 1] == semidefinite(n+1) and rank(V) == 1, which is also non-convex, which gets relaxed to just [V v;v' 1] == semidefinite(n+1), which is convex (because it eliminates (relaxes) the non-convex rank(V) == 1 constraint). I’ll leave it to someone else to determine whether v need not be defined here, and the constraint V == semidefinite(n) is sufficient, as shown in the pink box. rather than [V v;v' 1] == semidefinite(n+1)
If the relaxed (not slacked) problem solution is not rank 1, then you will not have a solution to the original problem, but only a lower bound on its optimal objective value.
Yes sorry it is V not X.
And yes the obtained solution will be only a lower bound because in this particular scenario it is not possible to get rank (V)=1. I am confused about z variable.
yes v needs to be define here because V == v*v’ where v is a [n,1] vector.
The formulation is maximizing the minimum of trace(V*A_k), subject to the other constraints . For some reason, sigma^2 is thrown in there as a scaling factor on z. But t is “your” problem, not mine, so I have no idea what the real world application or interpretation of any of this is supposed to be. But presumably, you should.
In my parlance, I wouldn’t call z a slack variable. Perhaps call it an epigraph variable. It is introduced to be the objective function in an epigraph formulation. My previous post stated what that epigraph formulation is doing.
You declare z as a CVX variable, just as you would any other optimization (decision) variable; and as your code shows you already have.
