fmincon Gradients not Matching with Mine

Having an issue with fmincon... The nonlinear constraint gradients that I compute do not match with those created by fmincon according to the dialog that appears when DerivativeCheck is 'on'. The issue is that fmincon is claiming that my derivative and its derivative are not the same within a tolerance of 1e-6. The difference it claims is usually 3e-3 to 1e-5. And the strange part is that sometimes the derivative that fmincon computes varies from run to run. Sometimes the derivatives match within the tolerance, most of the time they don't. Here is the equality constraint I am using:

ceq(1) = x(1) * e(x(2)) - x(2)

where e is a griddedInterpolant that is a function of x(2). For example, the data that generates the griddedInterpolant could be as follows:

E = [0 2.0 1.0]

P = [0 0.5 1.0]

e = griddedInterpolant(P, E, 'linear', 'linear')

So, I estimate the gradient of the equality constraint using a simple "forward" method as follows:

deltaX = 1e-6;  %Small step

eForward = e(x(2) + deltaX);  %Value of e at x(2) plus the small step

gradceq(1,1) = e(x(2))  %Gradient of ceq with respect to x(1)

gradceq(1,2) = x(1)*(eForward-e)/deltaX - 1  %Gradient of ceq with respect to x(2)

I have tried adjusting the step that fmincon uses to compute the gradient with 'TypicalX' to match mine, and no dice. I have tried central differences as well. Here is the dialog that it shows me:

Nonlinear equality constraint derivatives:
Maximum relative difference between user-supplied 
and finite-difference derivatives = 0.00354916.
  User-supplied constraint derivative element (4,1):     -0.996447
  Finite-difference constraint derivative element (4,1): -0.999996

Answer 1

[Matt J]

Linear griddedInterpolants are not differentiable at the knots, so you are quite likely to get arbitrary discrepancies near them depending on the particular finite difference parameters used by each test method.

Since twice continuous differentiability is required for most fmincon algorithms, use a 'spline' griddedInterpolant instead.

[Matt J]

In addition, it looks like gradceq(1,1) should be 1, not e(x(2)) and also

eForward = e(x(2) + deltaX);

[John R.]

Hi Matt, Thank you for the reply. I tried both 'cubic' and 'spline' for the griddedInterpolant and am getting the same result, albeit the difference between my derivative and fmincon's is ~1e-5 now.

There still is the inconsistency however. The difference between mine and fmincon's changes from run to run. Any idea why this is happening?

Do my equations for gradceq look okay?

[John R.]

Yes, eForward = e(x(2) + deltaX), that's what I meant.

Why do you say that gradceq(1,1) = 1?

The difference that DerivativeCheck is finding is associated with gradceq(1,2) in my example. With gradceq(1,1)=1, the difference becomes quite large.

[Matt J]

Why do you say that gradceq(1,1) = 1?

Never mind. In the formula for ceq, I misread the '*' for a '+'. I also didn't understand that gradceq is what your nonlcon handle is returning as the analytical gradient.

However, it should be clear that your finite difference estimate of gradceq(1,2) will not be as accurate as fmincon's native finite differencer, if fmincon uses a smaller finite difference step size. I don't think there is an easy way to reverse engineer fmincon's finite differencing operations and match them to your own tests. TypicalX is not the same as the step size.

As an alternative to DerivativeCheck, you can get fmincon to reveal its own gradient computation by setting the objective function to ceq. Then, get fmincon to return the gradient of this "objective function" at the initial point by calling with 6 output arguments

    [x,fval,exitflag,output,lambda,grad]=fmincon(...)

Do this with MaxIter=1 and GradObj='off'. The output 'grad' will be fmincon's idea of the gradient of ceq and you can compare your own estimate of the gradient to that baseline.

[Matt J]

John Commented:

Thank you for the information Matt. After some experimentation, it appears that using polyfit/polyder/polyval instead of the griddedInterpolant seems to work better. There is now good correlation between what I am computing and what fmincon is computing, using DerivativeCheck.

I just need to be careful about extrapolation as these high order polynomials can do some strange things beyond their training points.