ENH: optimize.minimize: Expose LINCOA, BOBYQA, NEWUOA, and UOBYQA

[nbelakovski]

Is your feature request related to a problem? Please describe.

With the pending closure of #20964, PRIMA will be integrated with SciPy, and while the primary goal of that PR and the issue it closes is to update COBYLA, PRIMA contains 4 other algorithms for derivative free optimization. They are:

• LINCOA - LINearly Constrained Optimization algorithm - for problems with linear constraints and bound constraints (bot no nonlinear constraints)
• BOBYQA - Bound Optimization BY Quadratic Approximation - for problems with bound constraints, but no linear/nonlinear constraints
• UOBYQA - Unconstrained Optimization BY Quadratic Approximation - for unconstrained problems
• NEWUOA - Newer algorithm for unconstrained problems.

More information can be found at @zaikunzhang's website: https://www.zhangzk.net/software.html

Since PRIMA will already be integrated in SciPy with the above PR, exposing these should be rather simple. I could do these myself, and I would propose to add them one by one to smooth out the review process, but these could also be a nice set of "good first issue" for folks interested in contributing to SciPy. I wonder if the maintainers have someone in mind who wants to contribute and can add these, or perhaps we can mark this issue as a good first issue and leave it up for a month or so to see if we have any bites?

Like I said I'd be happy to get this done myself and I'd even be willing to take responsibility for maintaining it in the future, but I thought it might be prudent to pause and ask if there are others who would like to take this opportunity to contribute.

Describe the solution you'd like.

No response

Describe alternatives you've considered.

No response

Additional context (e.g. screenshots, GIFs)

No response

[lucascolley]

x-ref pyodide/pyodide#1477

[dschmitz89]

Thanks for opening this issue :). The important question is which ones of the algorithms we really want. From what I understand, BOBYQA actually supersedes NEWUOA and UOBYQA. LINCOA I do not know much about.. is something between BOBYQA and COBYQA or more similar to COBYLA?

[lucascolley]

cc @gnikit I think you brought this topic up at the summit? (may be thinking of someone else!)

[lucascolley]

cc @janosg also

[janosg]

Hi @lucascolley, thanks for the ping! My understanding is as follows:

NEWUOA (2004) was Powell's first solver to use underdetermined quadratic trustregion models with 2n + 1 interpolation points, resolving the remaining degrees of freedom by penalizing the change in the Hessian terms of the quadratic models. Prof. Powell is very fond of this approach, even though he discovered it almost by accident:

The author’s knowledge of convergence theory had nothing to do with that success, and it
remains unhelpful to the present work (page 3 here).

BOBYQA (2009), LINCOA (2013) and COBYQA (2022) use this same approach and extend NEWUOA to handle bound constraints, linear constraints and nonlinear constraints, respectively. However, I would argue that none of the later solvers supersedes an earlier solver as the earlier solvers might perform better if the extensions are not needed. For example, NEWUOA might perform better than BOBYQA if no bound constraints are present because it can use a spherical trust-region instead of a cube shaped trust-region, which in my experience can help with performance.

NEWUOA (2004) supersedes UOBYQA (2000); Both are designed for unconstrained problems.

COBYQA (2022) supersedes COBYLA (1994); Both are designed for problems with nonlinear constraints.

However, superseding only means that the later solver is expected to be better on average. There is no guarantee that the later solver will be better for every problem. I therefore see value in having access to all solvers.

[janosg]

@nbelakovski I could work on exposing the solvers in scipy. I wanted to start contributing to scipy.optimize for a while and since I am already familiar with the solvers this might be a good starting point.

[dschmitz89]

Thanks for the details @janosg , turns out I know less about Powell's solvers than I thought! I would suggest to start with BOBYQA then after #20964 gets merged as it was requested a long time ago in pyodide/pyodide#1477.

[andyfaff]

(no fortran please)

[lucascolley]

(no fortran please)

could you elaborate? Do you not want to take on the new functions if their (vendored) implementation is in Fortran?

[andyfaff]

I thought the plan was that gradual removal of Fortran was the way forward. Python/c/python is much preferred.

[lucascolley]

Perhaps it makes sense to implement the Python interface to the other PRIMA algorithms in a different package then, if we don't want to commit to new Fortran algorithms in SciPy?

[matthew-brett]

This seems like a more subtle situation than would be covered by "prefer no Fortran". If I understand correctly, we here get a better, maintained, modern Fortran version of something that had an old unmaintained F77 implementation. So surely the answer to the replacements is - clearly yes for now, until we have a C implemention. Then the question is - should we make use of the other optimizers that we get for free. I would have thought the answer would be yes there too ... until we have a C implementation.