Trace minimization


(Ignacio) #1

Hello,

I am interested in solving the following problem:

find x
st ||P*x|^2 -b| <=error

where x is a complex vector, P is a complex matrix and b is a real vector.

This is not convex and that is why I am solving the trace minimzation instead, having:

min trace(X)
st |trace(P*X)-b| <=error

and then I get the x from X using the svd.

My problem is summarized as: when a real solution of x satisfies my problem (although X is convex and x too), then I got good results. But when a complex solution is needed then I do not get good results.

In the script below I solve these two problems (the one with A and B requires just a real solution while the one with C and D requires an imaginary part different from zero). Each of them is solved twice, with CVX and with YALMIP

With Yalmip I get good results in both cases but with CVX just in the first one.

What is the difference between the problem solved in Yalmip and CVX? What am I doing wrong?

Thanks in advance and best regards

n=15;nl=1:n;
u=linspace(-1,1,50); u0=0.2;
P=exp(1i.*(pi*u(:)*nl(:).'));
A=find(abs(u)<=0.15);    B=find(abs(u)>0.2);
C=find(abs(u-u0)<=0.15); D=find(abs(u-u0)>0.2);

PA=P(A,:); PB=P(B,:);
PC=P(C,:); PD=P(D,:);

X0=zeros(n);
for iter=1:5
    cvx_begin quiet
        variable X(n,n) hermitian complex
        minimize(norm(trace((X0+0.1*eye(n,n))\X)));
        subject to
        for ii=1:length(A)
            abs(trace(PA(ii,:)'*PA(ii,:)*X)-1)<=0.1;
        end
        for ii=1:length(B)
            abs(trace(PB(ii,:)'*PB(ii,:)*X)-0)<=0.1;
        end        
    cvx_end
    [uu,ss,vv]=svd(double(X));x=uu*ss(:,1);  X0=double(X);
end
hold on;plot(u,abs(P*x(:))./max(abs(P*x(:))),'--b');

X0=zeros(n);
for iter=1:10
    cvx_begin quiet
        variable X(n,n) hermitian complex
        minimize(norm(trace((X0+0.1*eye(n,n))\X)));
        subject to
        for ii=1:length(C)
            abs(trace(PC(ii,:)'*PC(ii,:)*X)-1)<=0.1;
        end
        for ii=1:length(D)
            abs(trace(PD(ii,:)'*PD(ii,:)*X)-0)<=0.1;
        end        
    cvx_end
    [uu,ss,vv]=svd(double(X));x=uu*ss(:,1);  X0=double(X);
end
hold on;plot(u,abs(P*x(:))./max(abs(P*x(:))),'--r');

X0=zeros(n);F=[];
for iter=1:5
	X=sdpvar(n,n,'hermitian','complex'); F = X >= 0;      	
	for ii=1:length(A)
        F = [F, abs(trace(PA(ii,:)'*PA(ii,:)*X)-1)<=0.1];
    end
	for jj=1:length(B)
        F = [F, abs(trace(PB(jj,:)'*PB(jj,:)*X)-0)<=0.1];
	end
    obj= norm(trace((X0+0.1*eye(n,n))\X));   solvesdp(F , obj);       
    [uu,ss,vv]=svd(double(X));x=uu*ss(:,1);  X0=double(X);
end
hold on;plot(u,abs(P*x(:))./max(abs(P*x(:))),':b');

X0=zeros(n);F=[];
for iter=1:5
	X=sdpvar(n,n,'hermitian','complex'); F = X >= 0;      	
	for ii=1:length(C)
        F = [F, abs(trace(PC(ii,:)'*PC(ii,:)*X)-1)<=0.1];
    end
	for jj=1:length(D)
        F = [F, abs(trace(PD(jj,:)'*PD(jj,:)*X)-0)<=0.1];
	end
    obj= norm(trace((X0+0.1*eye(n,n))\X));
    solvesdp(F , obj);  
    [uu,ss,vv]=svd(double(X));x=uu*ss(:,1); X0=double(X);
end
hold on;plot(u,abs(P*x(:))./max(abs(P*x(:))),':r');

(Mark L. Stone) #2

You did not constrain X to be semidefinite in CVX, but you did in YALMIP.

if the CXV variable declaration is changed to
variable X (n,n) complex semidefinite
or equivalently
variable X(n,n) hermitian semidefinite
or equivalently, the constraint
X == hermitian_semidefinite(n)
is added, then the results match YALMIP’s…


(Ignacio) #3

Thank you Mark!

I guessed that I was missing something but I did not realized what it was.
Best regards,

Ignacio