Wrong optimal value [model error]

1

With A = [1;-1], b = [1;2] as input the Matlab program

*****************************
[m,n] = size(A)
cvx_begin quiet
  variables   x(n) tau
  minimize( tau )
subject to
 { A * x - b , tau } <In> lorentz(n)
  x >= 0;
cvx_end
x
tau
****************************

gives as output x = 1/2, tau = 1.5. The correct value for tau is 2.12132034 (which equals the 2-norm ||A * x - b||). I tried both SDPT3 4.0 and Mosek 7 as solvers. They gave the same result. Is this a bug in CVX?

2

Are you sure you’ve entered the problem correctly? It is clear to me that x=1/2 is not the optimal solution. Instead, the optimal solution is x=0, \tau=\|b\|=2.2361. The only way to get the value of tau you’ve listed above is if x=-1/2, which violates the inequality x>=0.

3

Actually, there is an error in your model: you should be using lorentz(m), not lorentz(n). Your call to lorentz(n) is actually creating a cone that constrains a scalar instead of a 2-vector, like you intended. And it’s a quirk of MATLAB, that you can compare scalars to vectors elementwise, that allows CVX to accept this silently. What is effectively happening is this:

cvx_begin
    variables x(n) y(n) tau
    minimize( tau )
    A * x - b == y
    { y, tau } == lorentz(n)
cvx_end

If I run this model, I get x = -1/2, tau = 1.5. Notice that I have omitted x >= 0; if I didn’t omit that, the model is infeasible.

Of course, the right way to write your model is as follows:

cvx_begin
    variables x(n)
    minimize( norm(A*x-b) )
    x >= 0
cvx_end

which gives an optimal value of x to be 0. If you insist on using lorentz, then this is the correct model:

cvx_begin
    variables x(n) tau
    minimize( tau )
    { A * x - b, tau } == lorentz( m )
    x >= 0
cvx_end

So CVX is correct here. But why use lorentz anyway, when you can just use the norm function? Using lorentz is unclear, and as you have demonstrated, it is also prone to error.

4

You are right. The matrix A that I used was not [1;-1] but [-1;1]. Sorry for this typo.

5

Thanks a lot for you reply. Your last model now works fine. And you are right when you say that the second model is the more natural choice. However, it does not work. With A=[-1;1], b=[1;1], it produce the following error message:

Error using z (line 3)
Not enough input arguments.
Error in cvx/norm (line 74)
                        { x, z } == lorentz( n, [], ~isreal( x ) );
                        %#ok
Error in CVX_0_dual (line 12)
minimize( norm(A * x - b) )

Any explanation for this?

6

I have no trouble running this. You might want to file a bug report @ http://support.cvxr.com with details of your exact installation.

7

Ah, as I just realized, I think the problem may be the existence of a function named ‘z.m’ in your MATLAB path somewhere. Is that possible?

8

OK, I have confirmed this. If I create such a function, I get exactly the behavior you’re seeing. It would seem that CVX is confusing MATLAB’s parser! For now, please rename or remove that function, but I have already come up with a fix that will go out with the next release of CVX. Thank you!