# Sqlp stop: dual problem is suspected of being infeasible

## I have a problem here . How can I solve it

Data:
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.

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

## Output: 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

## 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

``````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);
cvx_begin
variable a(n)
minimize(norm(X*a-queryimage,1))
cvx_end
``````

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.

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

Iâ€™ll try again . Thank you for your help

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

cvx_begin
variable a(n)
minimize(norm(a,1))
norm(X*a-queryimage,2) <= epsilon
cvx_end

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.

1 Like

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).

1 Like

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<

Hi Mark,

I am having a similar challenge, i have a code that i used the same formulation for a smaller system , but when i extend it to a larger system i get the results

Status: Infeasible
Optimal value (cvx_optval): +Inf