# Error with "sparsify" Function

In an attempt to solve a convex optimization problem, I am running the code below. CVX consistently returns

cvx_optval = 0


However, when I evaluate the objective function manually, at the end of the code,

manual_optval = det_rootn(Hp(1:2,1:2))


I get a nonzero number:

manual_optval =

0.9547


Why is CVX doing this? It’s almost like it’s treating the optimization problem as a feasibility problem… Any thoughts?

The Code

%specify the problem data
m = 3;
mu = zeros(1,m+1);
mu(1) = 6.7307e3; %cm^-3
mu(2) = 227.8969; %cm^-2
mu(3) = 9.1470; %cm^-1
mu(4) = 0.3850;
k = ceil(m/2);

%specify cvx settings
cvx_precision default
cvx_quiet false
cvx_solver mosek

%describe the SDP
cvx_begin sdp
variable p(max(2*k+2,m) + 1,1) %+1 because of matlab indexing
variable z

expression Hp(k+1,k+1)
expression Bp(k-1+1,k-1+1)

maximize det_rootn(Hp(1:2,1:2))
subject to

%define the entries of the Hankel matrices
for i = 1:(k+1)
for j = 1:(k+1)
Hp(i,j) = p(i+j - 2 + 1); %plus one to account for indexing starting at 1
end
end

%define the entries of the Hankel matrices
for i = 1:(k-1+1)
for j = 1:(k-1+1)
Bp(i,j) = p(i+j - 1 + 1); %plus one to account for indexing starting at 1
end
end

%specify the LMIs
Hp >= 0;
Bp >= 0;

%specify the linear constraints
for j = 0:m
J = j + 1; %calculate the matlab index
p(J) <= mu(J)*z;
end

%specify the other constraints on p and z
p(1+1) == 1;
z >= 0;
cvx_end

if not(strcmp(cvx_status,'Solved'))
warning('CVX did not solve the problem to its default tolerance.')
disp(cvx_status)
end

cvx_optval
manual_optval = det_rootn(Hp(1:2,1:2))

I believe you have indeed inadvertently specified a feasibility problem, by virtue of maximizing an undefined expression. So CVX produces a feasible solution, whose objective value is not tied at all to the feasible Hp returned by CVX.

You need to place the defining equations (shown below) for the expression Hp prior to the maximize command in which it is used.
for i = 1:(k+1)
for j = 1:(k+1)
Hp(i,j) = p(i+j - 2 + 1); %plus one to account for indexing starting at 1
end
end;

If you do so, then at least using SeDuMi and SDPT3, the problem appears to be unbounded, with cvx_optval = Inf.

I believe what you did is essentially the same as this minimal example:

cvx_begin
variable x
expression y
maximize(y)
y = x
x <= 5
cvx_end
disp(y)
y =
cvx real affine expression (scalar)

Calling SeDuMi 1.34: 1 variables, 1 equality constraints
------------------------------------------------------------
SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 1 free variables
eqs m = 1, order n = 3, dim = 3, blocks = 1
nnz(A) = 2 + 0, nnz(ADA) = 1, nnz(L) = 1
it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
0 :            5.19E+00 0.000
1 :   1.25E-01 1.56E-01 0.000 0.0300 0.9900 0.9900   0.48  1  1  1.4E-01
2 :  -5.55E-06 7.18E-06 0.000 0.0000 1.0000 1.0000   0.99  1  1
iter seconds digits       c*x               b*y
2      0.0   Inf  0.0000000000e+00  0.0000000000e+00
|Ax-b| =   1.7e-15, [Ay-c]_+ =   0.0E+00, |x|=  1.2e+01, |y|=  0.0e+00

Detailed timing (sec)
Pre          IPM          Post
7.001E-03    1.400E-02    9.958E-04
Max-norms: ||b||=5, ||c|| = 0,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0

5.0000


Compare to:

    cvx_begin
variable x
expression y
y = x
maximize(y)
x  <=  5
cvx_end
disp(y)
y =
cvx real affine expression (scalar)

Calling SeDuMi 1.34: 1 variables, 1 equality constraints
------------------------------------------------------------
SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Split 1 free variables
eqs m = 1, order n = 3, dim = 3, blocks = 1
nnz(A) = 2 + 0, nnz(ADA) = 1, nnz(L) = 1
it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
0 :            7.72E+00 0.000
1 :  -4.56E+00 2.31E-01 0.000 0.0300 0.9900 0.9900   0.48  1  1  1.8E-01
2 :  -5.00E+00 1.07E-05 0.000 0.0000 1.0000 1.0000   0.99  1  1
iter seconds digits       c*x               b*y
2      0.0  15.8 -5.0000000000e+00 -5.0000000000e+00
|Ax-b| =   5.6e-16, [Ay-c]_+ =   0.0E+00, |x|=  1.2e+01, |y|=  1.0e+00

Detailed timing (sec)
Pre          IPM          Post
6.005E-03    1.399E-02    3.007E-03
Max-norms: ||b||=5, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +5

5.0000
1 Like

Thanks for the help, Mark!

Moving the lines defining Hp before the maximize statement is a step in the right direction, but there’s still something weird going on…

Now when I run the code, I get the following errors:

Undefined function 'vec' for input arguments of type 'double'.

Error in cvx/sparsify>replcols (line 142)

Error in cvx/sparsify (line 105)
[ x, forms, repls ] = replcols( x, tt, 'none', forms, repls, isobj );

Error in cvx_end (line 212)
x = sparsify( x, 'objective' );

Error in cvx/det_rootn (line 32)
cvx_end

Error in maximize (line 14)
x = evalin( 'caller', sprintf( '%s ', varargin{:} ) );

Error in calcCOVU (line 52)
maximize det_rootn(Hp(1:2,1:2))


If I comment out line 212 of cvx_end, so that the sparsify function is bypassed, the code works just fine; it returns that the problem is unbounded, as you said.

Any thoughts as to why I have to comment out the sparsify line while you do not?

Note: the error occurs whether I am using SeDuMi or MOSEK.

Please provide the output of cvx_version. Then when mcg comes along, perhaps he can assess the situation.

Here is mine:

---------------------------------------------------------------------------
CVX: Software for Disciplined Convex Programming       (c)2014 CVX Research
Version 2.1, Build 1110 (66e9a9c)                  Wed Jun 10 21:43:38 2015
---------------------------------------------------------------------------
Installation info:
Path: C:\cvx
MATLAB version: 8.3 (R2014a)
OS: Windows 7 amd64 version 6.1
Java version: 1.7.0_11

Here’s the first several lines of my cvx_version output.:

---------------------------------------------------------------------------
CVX: Software for Disciplined Convex Programming       (c)2014 CVX Research
Version 2.1, Build 1110 (66e9a9c)                  Wed Jun 10 21:43:38 2015
---------------------------------------------------------------------------
Installation info:
Path: C:\Users\Garrett\Dropbox (MIT)\Research\Code\CVX_2.1\cvx-w64\cvx
MATLAB version: 8.3 (R2014a)
OS: Windows 7 amd64 version 6.1
Java version: 1.7.0_11


There are additional lines with the headings Verifying CVX directory contents, Preferences, License host, and Installed license, but I assume that’s not relevant. In any case, I don’t see any messages that look problematic.

Try
which -all vec
There is supposed to be something in your MATLAB path from CVX as a cvx method. If there are any other instances of vec, are they after the cvx vec in your MATLAB path?

1 Like

After reading this post in the CVX forum, I also came to the conclusion that there might be a problem related to the CVX vec function.

I have reordered my search path so that the CVX references are at the top of the list. Thus, when I type the command

which -all vec


the output is

C:\Users\Garrett\Dropbox (MIT)\Research\Code\CVX_2.1\cvx-w64\cvx\functions\@cvx\vec.m     % cvx method
C:\Users\Garrett\Dropbox (MIT)\Research\Code\YALMIP\YALMIP\yalmip\@sdpvar\vec.m           % sdpvar method
C:\Users\Garrett\Dropbox (MIT)\Research\Code\YALMIP\YALMIP\yalmip\extras\@ndsdpvar\vec.m  % ndsdpvar method


I still get the error

Undefined function 'vec' for input arguments of type 'double'.


Update

When I manually added the path to the

cvx/functions/vec_


directory described in this post, the problem went away! Thanks for sticking with me, Mark!

O.k., good. I forgot about that thread, and was too lazy to bother searching on this forum for vec to see whether other problems had been reported.