4
$\begingroup$

I am trying to solve numerically a constrained optimisation problem in MATLAB, and I am wondering how the fmincon function calculates gradients when one isn't provided. Does anyone here know, or know how I might be able to find out?

Running the optimisation problem takes more time than I'd like it to, so I was hoping to speed it up by providing the gradient analytically. However, when I do this, I end up with wildly different solutions that seem less plausible than the solution that MATLAB generates when I do not provide the gradient.

As a check, I used the CheckGradients option in fmincon. Predictably, the gradient I provided did not pass this test. The same happens even when I set FiniteDifferenceType to 'central'. One obvious explanation is that the derivatives I provided truly are incorrect. However, I've gone over them several times and I'm fairly certain they are not.

As a sanity check, I tried to calculate the gradient of my objective numerically, using gradient, which the documentation suggests is calculated using finite differences. Unfortunately, the output of gradient is nowhere near the gradient calculated by fmincon.

I'm really not sure what's going on, and I'd appreciate it if anyone can help shed light on this situation.

Edit: I'm more interested in why fmincon and gradient produce different numerical derivatives, despite ostensibly both being calculated using finite differences. Unless I've misunderstood the options, the difference persists even when I give them the same finite difference step size.

Also, in case it's relevant:

I am actually using GlobalSearch (which then calls fmincon) to solve a constrained optimisation problem of the form

\begin{equation*} \begin{aligned} & \underset{\mathbf p, \mathbf q}{\max} & & V(\mathbf p, \mathbf q) - C(\mathbf p, \mathbf q) \\ & \ \ \text{s.t.} & & \sum_{i=1}^n p_i = 1 \\ & & & \sum_{i=1}^n q_i = 1. \end{aligned} \end{equation*}

$V(\mathbf p, \mathbf q)$ is actually the value function of some linear programming problem, and I've written a script that invokes linprog to calculate the value of my objective. $(\mathbf p, \mathbf q)$ also enters linearly into the objective and constraints in that problem. $C$, however, is non-linear.

Improve this question
$\endgroup$
3
  • $\begingroup$ Since you say you were able to calculate gradients analytically, are you able to provide your objective function and it's gradient? $\endgroup$
    – A. B. Marnie
    Aug 8, 2018 at 18:09
  • 1
    $\begingroup$ I suggest you approach this problem a bit more systematically. Simply write a trivial matlab function that calculates the derivative of your objective function by forward difference and compare that to your analytical value for different values of the step size. The fmincon choice of step size may be very inappropriate for your objective function. $\endgroup$
    – Bill Greene
    Aug 8, 2018 at 18:23
  • $\begingroup$ @amarney I could, but looking at the analytical derivatives will probably just be an exercise in chasing typographical errors, which I imagine won't be too productive here. I've verified them using a CAS. Or is there a different reason to have another look at them? $\endgroup$
    – Theoretical Economist
    Aug 10, 2018 at 15:07

1 Answer 1

Reset to default
3
$\begingroup$

The fmincon documentation is fairly clear on HOW it calculates gradients. Specifically, the documentation for the FiniteDifferenceType and FiniteDifferenceStepSize options explain this in some detail. fmincon is using either forward (default) or central difference formulas with the step size selected according to the documentation for FiniteDifferenceStepSize.

So the relevant question is not HOW are they calculated but why do the gradients calculated by finite difference differ so significantly from those calculated from an analytical expression? Usually this is caused by the finite difference step size being either too large or too small for the function being numerically "differentiated." The problem with a too-large step size is obvious. The problem with a too-small step size is that roundoff error makes the calculation unreliable. Some experimentation with different step sizes is often needed to find a value that is appropriate for a particular function.

This is explained in more detail in this paper by Iott and Haftka where they discuss an approach for step size selection.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ I'd argue that it's far more common in practice that the analytical derivative formula supplied by the user is simply wrong. Either way, knowing that you're getting different finite difference and analytical derivatives tells you that you need to debug the derivatives. $\endgroup$
    – Brian Borchers
    Aug 9, 2018 at 13:59
  • $\begingroup$ @BrianBorchers I'm open to the analytical derivatives being wrong. However, what I don't understand is why I am getting different derivatives from gradient and fmincon. Both appear to be calculated using finite differences. If I've understood the options correctly, I've even set the step sizes of both functions to be the same. $\endgroup$
    – Theoretical Economist
    Aug 10, 2018 at 15:04
  • 4
    $\begingroup$ I agree that you should be getting similar numerical derivatives from the two functions if you're using them properly, so either you aren't using them properly or there's a bug in one of them. Can you produce a very simple example which still shows differences between the three derivative calculations? $\endgroup$
    – Brian Borchers
    Aug 10, 2018 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.