Unexpected behavior (to me) with quadprog constraintTolerance.

I'm using quadprog (w/ fmincon) to solve a quadratic program w/ inequality constraints.

The returned solution, however, violates one of my constraints by 1e-12.

I would expect the solution to live on the INTERIOR of the constraint set, given that it is using an interior point method...

Changing constraintTolerance to 1e-14 did not help.

Any suggestions or explanations would be much appreciated!

Thanks!

Matt

[Walter Roberson]

What kind of inequality constraints are they ? Linear or nonlinear ?

If I recall correctly, linear inequalities should be respected to within round-off error, but that nonlinear inequalities are not enforced at all times.

[Matthew]

Linear inequality constraints. Thanks for responding!

[Matthew]

In what sense should "linear inequalities be respected within round-off error"? If it can return a value 1e-12 outside of the constraints, it should be able to recognize this and at least throw away the 1e-12 error and return a value on the boundary. This behavior still seems like a choice to me, and, if so, it is a surprising one. It is a sensible choice if one were only interested in values of the objective function...but it does not make sense to me if a user is interested in the solution value.

Answer 1

[John D'Errico]

You say you are using quadprog with fmincon. But in fact, you are apparently not using quadprog then, but fmincon. I suppose you may be solving a quadratic problem using fmincon. Or, possibly what you meant is you tried both solvers and got the same behavior.

What you need to understand is that when you solve mathematical problems in floating point arithmetic, that you can sometimes get tiny errors that are on the order of the least significant bits (LSB) of your process. In fact, you need to accept that you WILL get that crap in the LSBs. Just a fact of life in a floating point universe. That is no different from the classicly misunderstood problem in floating point that

0.1 + 0.2 ~= 0.3
ans =
  logical
   1

Next, you need to appreciate that linear systems of equations (thus things like equality constraints and inequalities) will often amplify any noise in the LSBs. Again, this is simply a fact of life.

So ANY noise in those LSBs can be amplified by a factor that MAY be as large as the condition number of the equations involved. That is simply something unavoidable. So even if fmincon (or quadprog) thinks the result is inside the constraints OR on the boundary thereof, a computed point may fall outside by a tiny amount, because numerically locating that constraint is impossible to any more precision in floating point arithmetic using doubles.

[Matthew]

Thanks for the details John.

1. Yes, I think you're right that I'm effectively using fmincon through calling quadprog.
2. I understand that floating point errors are expected and that they can amplify. However, I don't understand why a solution would be returned that is easily verified to live outside of the constraints within the given precision (even if the difference in objective is just due to amplified LSB noise). In my case, I am interested in the optimal solution, NOT the optimal value of the cost function. Imagine I wished to use the solution as a parameter in a model that is ill-defined outside of the constraint set.