quadprog output: this problem is non-convex

I am trying to solve a quadratic optimization problem but quadprog keeps telling me that my problem is non-convex.

After several experiments, I found that the problem comes from the equation constraints matrix A, which is a 57250*57441 matrix.

For the following code,

[m, n] = size(A);
assert(m < n);
options = optimoptions('quadprog','Display','off');
[Pwp,fval,exitflag,output] = quadprog(speye(n), zeros(n,1), [], [], A, zeros(m, 1), [], [], [], options);

obviously the solution should be the all-zero vector. But the output still said that this is a nonconvex problem.

=============

Update: I am using matlab 2022b. Here is the link for the mat file of my matrix A:

https://www.dropbox.com/t/eeqMCurgyrgy8brB

I am sorry that it's larger than 5MB so I can only put the link here instead of directly attaching it to this post.

[Matt J]

You haven't indicated what release you're using, but I don't get that message in R2023b.

[Changhe]

2022b

[Matt J]

Is A in sparse form?

[Changhe]

Yes. I just added the link for A.

[Walter Roberson]

It works in R2024b. I am going back to test in R2022b.

[Walter Roberson]

It works for me in R2022b. The resulting Pwp is all ones.

[Matt J]

It works for me in R2022b. The resulting Pwp is all ones.

Clearly the wrong result. Are you sure there isn't a premultiplying constant scaling it down close to zero?

[Matt J]

but quadprog keeps telling me that my problem is non-convex.

I have reproduced this with the given A matrix in R2023b. Hmmm...

[Torsten]

@Walter Roberson

It works for me in R2022b. The resulting Pwp is all ones.

Not zeros ?

[Walter Roberson]

All, I was counting on the fact that there was no error message, and was not checking exitflag . exitflag is showing up as -6, non-convex problem detected.

[Walter Roberson]

Unfortunately the invoked routine, ipqpsparse, is a .p file, so we cannot examine what is going on internally.

Answer 1

[Matt J]

I think you probably should report it as a bug, but a possible workaround would be to approximate the original problem with inequality constraints,

b=repelem(1e-10,m);

[Pwp,fval,exitflag,output] = ...
    quadprog(speye(n), zeros(n,1), [A;-A], [b;b], [], [], [], [], [], options);

Answer 2

[Torsten]

Maybe there are Inf or NaN coefficients in your A ? The following small example works.

A = rand(53,66);
[m,n] = size(A);
options = optimoptions('quadprog','Display','off');
[Pwp,fval,exitflag,output] = quadprog(speye(n), zeros(n,1), [], [], A, zeros(m, 1), [], [], [], options)

Pwp = 66x1

1.0e-13 * -0.0955 -0.1044 -0.0355 0.0400 0.0122 0.1021 -0.0133 0.0133 -0.0910 0.1088

<mw-icon class=""></mw-icon>

<mw-icon class=""></mw-icon>

fval = 3.2638e-27

exitflag = 1

output = struct with fields:
            message: 'Minimum found that satisfies the constraints....'
          algorithm: 'interior-point-convex'
      firstorderopt: 2.0437e-16
    constrviolation: 3.1306e-14
         iterations: 1
       linearsolver: 'sparse'
       cgiterations: []

[Changhe]

No, I am very sure there aren't any NAN or inf.

[Torsten]

Ok, then we are not able to give a helpful answer because quadprog in MATLAB R2024a seems to work as expected.

[Changhe]

Is it possible for me to upload my matrix A? Then anyone who is interested in this problem could try.

[Walter Roberson]

Store A in a .mat file and attach the .mat file. If that would be too large, try zipping the .mat file and attaching the zip

[Changhe]

Thanks a lot. I will do it in a minute.

[Changhe]

I have added the link for A.