Repository: scipy/scipy
Pull request: DOC: optimize: l-bfgs-b: clarify what is meant by `maxfun`, `maxiter`
This is an attempt to clarify the behaviour of `maxiter` and `maxfun` in `l-bfgs-b` via documentation. x-ref #18346.

Closes #18346.

From the reading of that issue the OP may also wish to see `maxfun`/`maxiter` set to `None` (i.e. wait until convergence).

Problem statement:
DOC: optimize: l_bfgs_b: sets `maxiter` and `maxfun` to the same value (15000)
### Describe your issue.

scipy.optimize.fmin_l_bfgs_b sets both ``maxiter`` and ``maxfun``, and sets them to the same value of 15000.  The exact  meaning of "iteration" is somewhat ambiguous, and the number of function evaluations is not precisely described for an iteration.  Still, it is hard to imagine a case in which the number of iterations is smaller than the number of function evaluations.   

That means that ``maxiter=15000`` has effectively no impact, and that a user setting ``maxiter=25000`` but not also setting ``maxfun`` will have the method give up due to too many function calls.   The error message from this condition ('STOP: TOTAL NO. of f AND g EVALUATIONS EXCEEDS LIMIT') is cryptic, and likely to lead the gentle user to assume that this was generated by Fortran code.

Must both ``maxiter`` and ``maxfun`` be set to the same value? 
Does one ever care how many iterations are taken (again, not knowing for sure how many function evaluations that would be) as opposed to caring about how many function evaluations (easily measured, easy to interpret as "proportional to runtime").

Perhaps ``maxiter`` should have a default value of ``None``.





### Reproducing Code Example

```python
result = minimize(my_func, method='L-BFGS-B', maxiter=25000)
```


### Error message

```shell
STOP: TOTAL NO. of f AND g EVALUATIONS EXCEEDS LIMIT
```


### SciPy/NumPy/Python version and system information

```shell
scipy 1.10.1
```

Hints from issue discussion:
I usually set maxfun much larger than maxiter, when I change defaults, expecting that each iteration will or can take several function evaluations.
I usually check maxiter and never maxfun for the optimization.
@josef-pkt I think the issue is not what knowledgable users do, but that specifying ``maxiter=50000`` will not actually allow more function evaluations -- the method will stop at 15000 function evaluations and give a relatively cryptic message even when the user explicitly told the method that it could take more iterations.    

Setting ``maxiter=50000`` does not do what the documentation says it will do. 


All stopping criteria are `or` connected. If one is satisfied, then it stops. AFAIK.
I think mixing how conditions are combined will be confusing.

This actually also bites me quite often. 
I increase maxiter, then maxfun stops early, then I increase maxfun high enough that I think it won't be binding. But we don't have cases in statsmodels where we would want maxiter=50000.


(
In statsmodels we have a named option for user for `maxiter`, all other optimizer options are in kwargs.
You could change maxfun to a multiple of maxiter, if users just specify a non-default maxiter.
)



@josef-pkt my view is that ``maxiter`` is confusing, liable to be different for different methods, and that sticking with ``maxfun`` would be much clearer, easily explainable: how many times is the function called to find the solution?  Do I care if it is called to find a derivative or "take a step"?  No, I do not.  But, it is something easily counted and easily verified.  "Iteration" will always be poorly defined. 

But: here, setting ``maxiter == maxfun`` and having cryptic messages just make no sense.   
And, again, setting ``maxiter=50000`` does not do what the documentation says it will do.

The number of iterations is a good measure for how fast it converges, which still depends on which gradient, hessian information is used, or not used, by the optimization methods but is a good measure of how difficult the optimization is.

The number of iterations, AFAIU, is a measure for how often the parameters are "successfully" updated.

The number of function evaluation depends in general on implementation details, how much backtracking, numerical derivatives or are analytical derivatives provided. This can be a measure of how expensive the optimization is but not about how **difficult** the optimization is.

For statsmodels, nice problems converge below 10 iterations or below 100 iterations with bfgs or newton methods.
Difficult problems and badly scaled problems take 1000 or 5000 Nelder-Mead iterations to get into the neighborhood of the optimum. After that maybe a few bfgs or newton iterations to get a good local optimum.

If you need too many iterations, then the problem is most likely ill-posed, and the user better check what's wrong with model and/or data.

Disclaimer: I never checked how number of function evaluations is actually computed.

In any case, I always check number of iterations, but never number of function evaluations. I have no intuition for the how number of function evaluation differs across methods.

 
@josef-pkt   While I can understand that you, an expert in using these methods, know what they are doing, that is not actually the issue here.  A less experienced user will read the documentation and conclude that it does what it says it will do.  For ``method='L-BFGS-B'``, setting ``maxiter=30000`` does not do what the documentation says it does

The number of function evaluations is easy for any user to check -- they can just add a counter to their objective function.   It is also fair to say that either the function evaluation dominates the fit run time or the run time will be very fast. 
So N_function_evaluations will scale well with run time when run time is noticeable and something the user may want to limit.   Comparing two methods, the number of function evaluations is an important measure of "time for solution".

But "iteration" is poorly defined.  Is that Nvarys function evaluations, 2*Nvarys, 3*Nvarys?   Is it even guaranteed to be consistent for any single method, let alone consistent across methods?  I consider myself somewhat familiar with these algorithms and tools, and I do not know the answer.  Because "iteration" is poorly defined and likely to be different for different methods: do they fully recompute a 2- or 3-point derivative for each variable at each "iteration"?  I do not see any documentation of that for *any* of the solvers. 

As an aside, the dreaded `optimize.least_squares` just flat-out lies about how many function evaluations it does -- the lie is documented, but documented fraud is still fraud.  I refuse to raise any issues having to do with `least_squares` as that would imply a willingness to try to improve it.

I've raised the issue, but I am now done trying to contribute further to `scipy.optimize`.
Hi @newville, thank you for reporting. I am relabelling this as a documentation issue as there is nothing wrong with the implementation.

The documentation currently says:

```
    maxfun : int, optional
        Maximum number of function evaluations. Note that this function
        may violate the limit because of evaluating gradients by numerical
        differentiation.
    maxiter : int, optional
        Maximum number of iterations.
```

Both descriptions are correct but I do agree that there is room for improvement. The logic around `approx_grad` and `fprime` makes it that the number of evaluation cannot really be known (only looking at `fprime`, being a user defined function it could called `func` an arbitrary number of time.)

> The error message from this condition ('STOP: TOTAL NO. of f AND g EVALUATIONS EXCEEDS LIMIT') is cryptic, and likely to lead the gentle user to assume that this was generated by Fortran code.

This is actually not the case. All this code is pure Python and we can easily improve the message.

```python
            if _call_callback_maybe_halt(callback, intermediate_result):
                task[:] = 'STOP: CALLBACK REQUESTED HALT'
            if n_iterations >= maxiter:
                task[:] = 'STOP: TOTAL NO. of ITERATIONS REACHED LIMIT'
            elif sf.nfev > maxfun:
                task[:] = ('STOP: TOTAL NO. of f AND g EVALUATIONS '
                           'EXCEEDS LIMIT')
```

`maxfun` and `maxiter` are both present to try to have some consistency between all the optimizers. And for some folks it's more natural to speak in terms of one or the other. Adjusting one or the other would not be very simple and must be done carefully as backward compatibility is a real concern for such parameters.

All in all, I think there is room for documentation improvement in both the docstrings and the error messages being raised.
@tupui 

It is true that setting ``maxiter=30000`` does not do what the documentation says. That could be viewed solely as a documentation bug.  

It is also true that setting ``maxiter=30000`` does not increase the number of iterations performed - the routine will stop at 15000 function evaluations.  That is not a documentation bug, that is a logic error.

>> The error message from this condition ('STOP: TOTAL NO. of f AND g EVALUATIONS EXCEEDS LIMIT') is cryptic, and likely to lead the gentle user to assume that this was generated by Fortran code.

> This is actually not the case

Yes to "It is actually not the case that the error was generated by Fortran code".  But also, No to "It is actually not the case that the error message *is cryptic, and likely to lead the gentle reader to assume that the error was generated by Fortran code*", which is what I actually said.

> maxfun and maxiter are both present to try to have some consistency between all the optimizers

Which other optimizers set the same value for both `maxfun` and `maxiter` and stop when either is reached?  

How is possible for any optimizer to ever reach N iterations before reaching N function evaluations?

I disagree, both parameters are linked together. The current statements are not false, the missing bit is to say that both are linked together (and also the stopping criteria is also playing a role in the effective iterations/evaluations.)


> Which other optimizers set the same value for both maxfun and maxiter and stop when either is reached?

e.g. Nelder-Mead https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html You can also have some combination of global/local optimiser where you would set some iterations on the global one and some iterations/evaluations on the local one. i.e. it's not trivial as lot of parameters are involved in stopping optimizers.

> How is possible for any optimizer to ever reach N iterations before reaching N function evaluations?

I did not comment on that part as I don't think this part is relevant for this issue. (And just to fabricate an example, you can provide a function that would skip the evaluation on some parameters. This could also happen in an optimizer (I don't know if we have such things but I would not be surprised if we did in things like trust region optimizers).)
@tupui  Sorry, I do not understand. With what do you disagree?

>> How is possible for any optimizer to ever reach N iterations before reaching N function evaluations?

> I did not comment on that part as I don't think this part is relevant for this issue.

Yes, it is.


>> Which other optimizers set the same value for both maxfun and maxiter and stop when either is reached?
>  e.g. Nelder-Mead https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html 

Well, `Nelder-Mead` sets the same value of ``None``, and in that case sets ``maxfun`` to a number that scales with the number of variables.  It also uselessly sets ``maxiter`` to the same value, but in ``_minimize_neldermead()`` that will never be reached before ``maxfun`` is exceeded.  I do actually mean "never", not merely "in most cases" or "in all but perverse cases".  I have read the code.

But also, setting ``maxiter`` without specifying ``maxfun`` actually does what the user wants, as it sets ``maxfun`` to ``np.inf``.

What the ``lbgfsb`` method does is far, far worse.  

> (And just to fabricate an example, you can provide a function that would skip the evaluation on some parameters. This could also happen in an optimizer (I don't know if we have such things but I would not be surprised if we did in things like trust region optimizers).)

Wouldn't you have to *call the function* to let it "skip"?   Even in concept, "iteration" is poorly defined. But there is not a solver that does not make at least one call to the objective function per iteration.   Setting ``maxiter == maxfun`` is useless.   

What ``lbgfsb`` does is a bug.

Commit message: DOC: l-bfgs-b clarify what is meant by maxfun, maxiter

Patch to review:
diff --git a/scipy/optimize/_lbfgsb_py.py b/scipy/optimize/_lbfgsb_py.py
index 1883b31dbead..c5a476480c8d 100644
--- a/scipy/optimize/_lbfgsb_py.py
+++ b/scipy/optimize/_lbfgsb_py.py
@@ -323,11 +323,11 @@ def _minimize_lbfgsb(fun, x0, args=(), jac=None, bounds=None,
         If `jac is None` the absolute step size used for numerical
         approximation of the jacobian via forward differences.
     maxfun : int
-        Maximum number of function evaluations. Note that this function
-        may violate the limit because of evaluating gradients by numerical
-        differentiation.
+        Maximum number of function evaluations before minimization terminates.
+        Note that this function may violate the limit because if the gradients
+        are evaluated by numerical differentiation.
     maxiter : int
-        Maximum number of iterations.
+        Maximum number of algorithm iterations.
     iprint : int, optional
         Deprecated option that previously controlled the text printed on the
         screen during the problem solution. Now the code does not emit any
@@ -359,6 +359,11 @@ def _minimize_lbfgsb(fun, x0, args=(), jac=None, bounds=None,
     relationship between the two is ``ftol = factr * numpy.finfo(float).eps``.
     I.e., `factr` multiplies the default machine floating-point precision to
     arrive at `ftol`.
+    If the minimization is slow to converge the optimizer may halt if the
+    total number of function evaluations exceeds `maxfun`, or the number of
+    algorithm iterations has reached `maxiter` (whichever comes first). If
+    this is the case then `result.success is False`, and an appropriate
+    error message is contained in `result.message`.
 
     """
     _check_unknown_options(unknown_options)


Code review comments:
diff_hunk: @@ -359,6 +359,11 @@ def _minimize_lbfgsb(fun, x0, args=(), jac=None, bounds=None,
     relationship between the two is ``ftol = factr * numpy.finfo(float).eps``.
     I.e., `factr` multiplies the default machine floating-point precision to
     arrive at `ftol`.
+    If the minimization is slow to converge the optimizer may halt if the
+    total number of function evaluations exceeds `maxfun`, or the number of
+    algorithm iterations has reached `maxiter` (whichever comes first). If
+    this is the case then `result.success is False`, and an appropriate
+    error message is contained in `result.message`.
path: scipy/optimize/_lbfgsb_py.py
text: @user1:
```suggestion
    this is the case then ``result.success=False``, and an appropriate
    error message is contained in ``result.message``.
```