How can I solve infinite quadratic programs using the Optimization Toolbox?

The problem occurs if I have a quadratic:

.5*x'*H*x + f'*x

where H is indefinite (i.e. has both negative and positive eigenvalues) or negative definite and f has all zero elements. If this is the case, then the algorithm fails.

This problem does not happen when "f" has any nonzero elements.

Answer 1

[MathWorks Support Team]

Please follow this link to our website to review the limitation of QUADPROG:

https://www.mathworks.com/help/optim/ug/quadprog.html

The solution to indefinite or negative definite problems is often unbounded. In this case, "exitflag" is returned with a negative value to show a minimum was not found. Note that when a finite solution does exist, QUADPROG may only give local minima since the problem may still be nonconvex.

Try using the FMINCON function instead. Your objective function should be structured as:

myobjfun = @(x, H, c) (.5*x'*H*x + c'*x);

If you are using a version prior to MATLAB 7.0 (R14), you will need to create an inline function:

myobjfun = inline('(.5*x'*H*x + c'*x)', 'x', 'H', 'c');

The following function file computes the gradient of the quadratic and the first derivative matrix for the constraints, which in this case is just A':

function [g, gcon] = myg(x, H, c, A)
g = H*x + c;
gcon=A';

Then, FMINCON can be called using:

 [x,optout] = fmincon(myobjfun, x0, A, b, [], [], lb, ub, @myg)

In general, QUADPROG should be preferred over FMINCON when possible, but for some particular problems, QUADPROG will not work.