Quadprog new "feature"

It seems that in the later versions of Matlab quadprog checks if the problem is convex. In principle I would be happy with such a feature, except that the check is obviously rather rudimental and classifies as nonconvex problems that in fact are convex. This situation can very easily occur in the presence of equality constraints. I understand that a warning could still be thrown at the user, I even understand that the default behaviour should be to return an error, but I do not understand why I cannot set an option to ignore the warning and solve the problem anyway.

Answer 1

[Bruno Luong]

Can you just switch off by WARNING('off',...) like any other warnings?

[Mario Zanon]

I don't think it's a problem of warnings, it's actually neither a warning nor an error, the solver simply refuses to solve the problem.

Anyway, if I type warning in the command window, I get the message "All warnings have the state 'off'." Then I assume it's not the right fix.

[Bruno Luong]

Can you provide a small example that creates the blocking?

[Mario Zanon]

Actually I checked again on small size problem and it seems to return the correct solution. On a larger scale and more interesting problem, however, it does not return the correct solution.

Answer 2

[Bruno Luong]

It might be possible that with big matrix, degenerated semi-convex problem is detected as non-convex due to the numerical accuracy (e.g, eigs() are notoriously returns off eigen values).

You might try to add a small matrix

H = H + small*eye(size(H))

to make the non-convex detection gives less false warning.

Also if your matrix supposes to be symmetric, force it before calling quadprog by doing

H = 0.5*(H+H');

to make sure it is the case.

[Mario Zanon]

Well, this is not always desirable. In my case the Hessian matrix needs to be indefinite. It's the reduced Hessian which I make sure is positive definite and I do check that it does not have any direction of negative or zero curvature. Anyway, I guess I'll just use other tools, I am just slightly disappointed that quadprog was able to handle such problems before.

[Bruno Luong]

Again I don't get why you have problem, here is my run of non-convex hessian, and it works just fine

>> quadprog([1 0; 0 -1],[1 1],[],[],[],[],-1+[0 0],1+[0 0])

Solver stopped prematurely.

quadprog stopped because it exceeded the iteration limit,
options.MaxIterations = 200 (the default value).

ans =

     -0.9994
      1.0000

>>

[Steve Grikschat]

@Mario What release are you using?

In R2017a, a modified interior-point algorithm was introduced in quadprog for small problems with dense matrices. The convexity check is different from the sparse matrix version due to different factorizations in each.

If it had worked with the previous interior-point solver, then try casting the Hessian to sparse. Alternatively, in R2018b, you can set an option. See the release notes: https://www.mathworks.com/help/optim/release-notes.html

In either case, the solver checks convexity as it goes, which is why you'll see cases like Bruno has shown above. The downside is that it is subject to numerical error (which we try to compensate with some regularization).

The alternative that is prevalent in other IPM code is to simply check for a PSD Hessian and be done with it. In your case, it would never work.

If the sparse solver doesn't work, you can try the following undocumented option using an options structure:

options.ConvexCheck = 'off';

>> opts = optimset('quadprog'); 
>> quadprog([1 0; 0 -1],[1 1], [] ,[],[],[],zeros(2,1),[10; 10],[],opts);

The problem is non-convex.

>> opts.ConvexCheck = 'off';
>> quadprog([1 0; 0 -1],[1 1], [] ,[],[],[],zeros(2,1),[10; 10],[],opts);

Minimum found that satisfies the constraints.
<snip>

[Mario Zanon]

Thanks, I'll try that option. From a first quick attempt

opts.ConvexCheck = 'off';

seems to work.