Sqlp stop: dual problem is suspected of being infeasible

(Man Ho Minh) #1

I have a problem here . How can I solve it

input : https://drive.google.com/file/d/0BzytuMhrgIMOWHByaV9tVGhYNWs/view?usp=sharing
X ( d: 1575 , N: 49 ) contains in its columns the vectorized training images with d being the dimensionality of each images and N the number of training observations.

queryimage (d: 1575) is a vectorized image.

n = size(X,2);
variable a(n)
minimize norm(a,1)
subject to
X*a == queryimage;

Calling SDPT3 4.0: 1673 variables, 98 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.

num. of constraints = 98
dim. of socp var = 98, num. of socp blk = 49
dim. of free var = 1575 *** convert ublk to lblk

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|3.6e-01|5.6e+01|2.5e+09| 2.768130e-05 0.000000e+00| 0:0:00| chol 1 1
1|0.014|0.890|3.6e-01|6.2e+00|8.9e+07|-6.607117e+03 -2.342315e+07| 0:0:00| chol 1 1
2|1.000|0.882|1.1e-05|7.3e-01|6.1e+06|-2.580880e+04 -4.559388e+06| 0:0:00| chol 1 1
3|1.000|0.368|3.2e-06|4.6e-01|3.9e+06|-1.521688e+05 -2.907350e+06| 0:0:00| chol 1 1
4|0.218|0.248|3.1e-06|3.5e-01|2.8e+06|-3.013709e+05 -2.200364e+06| 0:0:00| chol 1 1
5|0.694|0.154|2.0e-06|3.0e-01|3.1e+06|-2.269359e+06 -1.868173e+06| 0:0:00| chol 1 1
6|0.067|0.047|2.3e-06|2.9e-01|3.5e+06|-8.434676e+06 -1.783595e+06| 0:0:00| chol 1 1
7|0.023|0.024|2.5e-06|2.8e-01|5.0e+06|-2.692048e+07 -1.741752e+06| 0:0:01| chol 1 1
8|0.058|0.033|3.0e-06|2.7e-01|1.8e+07|-2.501300e+08 -1.687105e+06| 0:0:01| chol 1 1
9|0.017|0.032|3.2e-06|2.7e-01|5.8e+07|-1.572757e+09 -1.642588e+06| 0:0:01| chol 1 1
10|0.013|0.009|3.2e-06|2.7e-01|6.8e+08|-1.991626e+10 -1.633585e+06| 0:0:01| chol 1 2
11|0.021|0.011|2.3e-06|2.7e-01|1.3e+10|-4.132350e+11 -1.683176e+06| 0:0:01| chol 2 2
12|0.036|0.012|2.2e-05|2.7e-01|4.7e+11|-1.758230e+13 -2.788725e+06| 0:0:01| chol 2 2
13|0.001|0.016|4.9e-05|2.6e-01|1.1e+12|-5.443418e+13 -6.520184e+07| 0:0:01| chol 2 2
14|0.008|0.009|1.3e-03|2.6e-01|2.4e+13|-1.237089e+15 -2.039176e+08| 0:0:01| chol 2 2
15|0.002|0.001|8.3e-03|2.7e-01|2.5e+14|-8.987602e+15 -4.396276e+08| 0:0:01| chol 2 2
16|0.001|0.001|1.4e-02|2.7e-01|5.4e+14|-1.557068e+16 -2.914295e+09| 0:0:01| chol 2 2
17|0.001|0.002|2.6e-02|2.7e-01|1.4e+15|-3.411376e+16 -1.361923e+10| 0:0:01| chol 2 2
18|0.002|0.004|4.1e-02|2.7e-01|3.5e+15|-7.479164e+16 -7.331256e+10| 0:0:01| chol 2 2
19|0.003|0.007|1.1e-01|2.7e-01|9.7e+15|-2.029225e+17 -3.875892e+11| 0:0:01| chol 2 2
20|0.005|0.016|5.5e-01|2.7e-01|2.9e+16|-7.195577e+17 -2.651445e+12| 0:0:01| chol 2 2
21|0.012|0.033|4.1e+00|2.6e-01|9.9e+16|-6.406001e+18 -1.708287e+13| 0:0:01|
sqlp stop: dual problem is suspected of being infeasible

number of iterations = 21
residual of dual infeasibility
certificate X = 5.18e-18
reldist to infeas. <= 5.18e-17
Total CPU time (secs) = 1.47
CPU time per iteration = 0.07
termination code = 2
DIMACS: 1.6e+01 0.0e+00 7.5e+00 0.0e+00 -1.0e+00 1.5e-02

Status: Infeasible
Optimal value (cvx_optval): +Inf

(Mark L. Stone) #2
Status: Infeasible
Optimal value (cvx_optval): +Inf

reports that the problem is primal infeasible, as CVX always reports relative to the problem as entered.

Indeed, X*a == queryimage is overdetermined, and can not be solved exactly, but can for instance be solved by least squares, in which case the inf norm of the residual is 75.5. Or fit it in another norm, as below.

I don’t know what you are trying to do, but obviously your problem formulation is not “correct”.

Is this what you want?

n = size(X,2);
variable a(n)

This reports

Status: Inaccurate/Solved
Optimal value (cvx_optval): +11125.7

Using SeDuMi,

Status: Solved
Optimal value (cvx_optval): +11125.6

The least squares solution has a 1 norm of residual of 11909.5, which is a little bigger than the 1 norm of the residual of the 1 norm residual minimizer.

(Man Ho Minh) #3

Thank you for quick answer .
I want to reproduce Sparse Representation Classification by using CVX and step 3 is my problem :frowning:

I’ll try again . Thank you for your help :smiley:

(Mark L. Stone) #4

The 2 norm of the 2 norm minimizing (i.e., least squares) solution a to X*a = queryimage is 4.189843135262012e+02 . Therefore, if you wish

variable a(n)
norm(X*a-queryimage,2) <= epsilon

to be feasible, epsilon must be >= 4.189843135262012e+02. I really doubt the algorithm authors had that in mind as a value of epsilon. Using that minimum such value of epsilon, results in optimal a having norm(a,1) = 21169.

Perhaps you should reexamine whether your X and queryimage constitute a reasonable data set for use of this algorithm. You’re not having difficulty with CVX. You’re having difficulty with your data and/or algorithm. If you can get that figured out, entering the problem and solving in CVX should be easy.

(Mark L. Stone) #5

I’m guessing the algorithm you show is intended for the underdetermined case, m < n, which allows degrees of freedom for optimizing x; specofically attempting to maximize sparsity through the proxy operation of minimizing the L^1 norm, subject to Ax == y (your Xa == queryimage) within some tolerance.

Of course your m (1575) is much greater than n (49).

(Man Ho Minh) #6

Sorry I just woke up. It’s very helpful .
I haven’t tried to use the alternative step 3 with l2 norm and epsilon yet . I’ll try later . But as you said m < n . That’s right.
Thank you so much. I really appriciate your help.
Problem solved >w<