Wrong results in CVX with different solvers, correct in Yalmip. Bug?


(A ) #1

Hi everyone.
I am trying to implement a rather simple SDP coming from quantum information.
In the code below the matrices R and linconst come from other computations and will in general change. As a matter of fact for many instances of the problem CVX gives correct results (I can provide examples if needed).
Note that the matrix R is complex valued.

Unfortunately, in many other instances CVX gives a completely wrong result, for example with the data in this file.
A minimal version of the code to reproduce the problem is the following, I provide the YALMIP version as well, which gives me the correct result.
I know that the YALMIP result is correct also from other external considerations.
I have tried with other solvers: both sedumi and spdt3 give the same result.

% CVX
cvx_solver mosek
cvx_begin sdp
    variable V(2,2) symmetric
    variable X(8,2)
    minimize trace(V)
    subject to
        [ V , X'*R' ; R*X , eye(6)] >= 0
        linconst*X==eye(2)
cvx_end
cvxRes=cvx_optval;

% Yalmip
V=sdpvar(2,2);
X=sdpvar(8,2,'full'); 
Constraints = [[ V , X'*R' ; R*X , eye(6)] >= 0,linconst*X==eye(2)];
Objective = trace(V);
options = sdpsettings('verbose',1,'solver','mosek');
s    ol = optimize(Constraints,Objective,options);
YalmipRes=value(Objective);

cvxRes-YalmipRes %this should be close to zero instead it about 91!

Output of cvx_version:

---------------------------------------------------------------------------
CVX: Software for Disciplined Convex Programming       (c)2014 CVX Research
Version 2.1, Build 1123 (cff5298)                  Sun Dec 17 18:58:10 2017
---------------------------------------------------------------------------
Installation info:
    Path: /home/francesco/Downloads/cvx-a64/cvx
    MATLAB version: 9.5 (R2018b)
    OS: Linux amd64 version 4.18.0-16-generic
    Java version: 1.8.0_152
Verfying CVX directory contents:
    No missing files.
Preferences: 
    Path: /home/francesco/.matlab/cvx_prefs.mat
License host:
    Username: francesco
    Host ID: 989096e19379 (eno1)
Installed license:
    Also in file: /home/francesco/Documents/MATLAB/cvx_license.dat
    Organization: The University of Warwick
    Contact: ----
    License type: academic
    Named user: francesco
    Host ID: 989096e19379
    Expiration: 2019-10-31 (226 days remaining)
    Status: verified
---------------------------------------------------------------------------

Is it safe to say this is a bug? Should I file a report?
Thanks.


(Mark L. Stone) #2

Three solvers under CVX basically produce the same feasible solution while claiming optimality. YALMIP produces an optimal, feasible soution having much smaller objective value.

This looks like a bug in CVX,. Go ahead and file a bug report with reproducible examples demonstrating erroneous solution.


(A ) #3

Thanks for the answer, I will do that.


(Mark L. Stone) #4

Perhaps this has something to do with complex input data.

This matches YALMIP

cvx_begin 
variable V(2,2) symmetric
variable X(8,2) complex
minimize trace(V)
subject to
[V , X'*R' ; R*X , eye(6)] == semidefinite(8)
linconst*X==eye(2)
cvx_end

but this does not

    cvx_begin sdp
    variable V(2,2) symmetric
    variable X(8,2) complex
    minimize trace(V)
    subject to
    [ V , X'*R' ; R*X , eye(6)] >= 0
    linconst*X==eye(2)
    cvx_end

No variables are declared complex in your YALMIP code, and indeed YALMIP produces real X and V.


(A ) #5

Interesting observation.
In my problem X has to be real, nonetheless the matrix inequality is meant in the hermitian positive semidefinite sense, the only imaginary components enter through R.

Without specifying a complex X this code produces the same wrong answer:

cvx_begin 
    variable V(2,2) symmetric
    variable X(8,2)
    minimize trace(V)
    subject to
        [ V , X'*R' ; R*X , eye(6)] == hermitian_semidefinite(8)
        linconst*X==eye(2)
cvx_end

If I use

[ V , X'*R' ; R*X , eye(6)] == semidefinite(8)

I get a different wrong result, but I guess that it should be a mistake to constrain an Hermitian matrix to be real positive semidefinite instead of hermitian positive semidefinite (I couldn’t understand this clearly from the documentation to be honest).


(Mark L. Stone) #6

I will have to defer to @mcg for any further investigation.


(A ) #7

Thanks again, I’m also filing a bug anyway.


(Mark L. Stone) #8

Bug reports go to @mcg . We’ll have to let him rule whether it is a bug or a feature.


(Lucas) #9

Mark,

By that you mean the same model gives better (more accurate) results if passed to YALMIP as opposed to CVX?


(Mark L. Stone) #10

By that I mean that I will defer to the CVX develper, @mcg, as to what is a bug, documentation error, inadequately clear documentation, feature, or whatever.

Whatever is going on in this case seems to have something to do with there being some complex numbers in the input data. It is not a generally true statement that YALMIP gives better or more accurate results than CVX for problems which both tools can address.


(A ) #11

In case I was not clear enough: the input data I gave is only a particular example for which CVX gives a wrong result, but in most cases results from YALMIP and CVX coincide perfectly.
That’s why I think it’s very likely a bug.