Implement Shubert-Piyavskii and GSS for deterministic global optimization

[Luis-Varona]

If possible, I'd like to create a PR to add Shubert-Piyavskii and golden-section search to nlopt's algorithm suite:

The Shubert-Piyavskii method optimizes a univariate, Lipschitz continuous function inside a specified interval. Given an accurate Lipschitz constant, it is guaranteed to come within an arbitrary epsilon of the true global extremum. Unlike most other deterministic global optimizations algorithms (e.g., golden-section search), it is not restricted to unimodal functions; moreover, it does not require an initial guess. It deterministically samples points from ever-narrowing subintervals of the search space until the sampled best point is sufficiently close to the lower/upper bound (depending on whether we are minimizing or maximizing) given by the Lipschitz constant.

Golden-section search is a related deterministic global optimization method applicable to any unimodal continuous function. It operates by iteratively narrowing the search interval based on the golden ratio, subdividing into a smaller part and a larger part, eliminating the less promising candidate, and repeating the process. Unlike Shubert-Piyavskii, it does not require a Lipschitz constant (equivalent to a bound on the derivative for differentiable functions), but it does require continuity over the optimization range. The tradeoff is that it only works well for unimodal functions and does not offer the same guarantee of converging to within an arbitrary epsilon of the true global extremum.

[stevengj]

I would be open to this, especially golden-section search (which seems similar in some ways to DIRECT?), with the caveat that NLopt is oriented mainly towards multivariate optimization. Also, the default interface doesn't include a parameter for specifying a Lipshitz constant — you could have this as an algorithm-specific parameter of course, but that interface is mainly intended for optional parameters, not required ones.

[Luis-Varona]

I would be open to this, especially golden-section search (which seems similar in some ways to DIRECT?), with the caveat that NLopt is oriented mainly towards multivariate optimization. Also, the default interface doesn't include a parameter for specifying a Lipshitz constant — you could have this as an algorithm-specific parameter of course, but that interface is mainly intended for optional parameters, not required ones.

Noted, @stevengj. So where do you suggest we go from here?

[stevengj]

Is there a sample implementation of an algorithm you would like to use? Maybe benchmark it (in terms of the number of function evaluations to find the optimum to some tolerance, e.g. using the stop_val termination criterion) against the algorithms in NLopt on a couple of example problems?

[Luis-Varona]

Yup, I have sample implementations. The thing with benchmarking is that the main benefit to using Shubert–Piyavskii is that it can provably get within an arbitrary epsilon of the true global minimum/maximum, even when the function is highly multimodal, non-differentiable, and just generally "not nice." Most of the NLopt solvers are faster but also heuristic/imperfect, I think?

But if you'd like a sample comparison, I wrote some tests a while back for an ongoing PR in Rust's argmin that showcased functions/situations in which SP excels. I can do those in Julia as well @stevengj; just let me know. 🙂

[stevengj]

DIRECT should have the same property for Lipshitz functions (with an unknown Lipshitz constant).

[Luis-Varona]

DIRECT should have the same property for Lipshitz functions (with an unknown Lipshitz constant).

@stevengj Got it. I'm assuming you'd like me to just run the benchmarks in a script and upload the results here rather than actually merge stuff into the codebase as of right now?

[stevengj]

Yes, to start with.

[Luis-Varona]

Will do, @stevengj. 🙂

[Luis-Varona]

Hi, @stevengj! Sorry, this completely slipped my mind for a while. I'll revisit this issue sometime next week and give you the benchmarks. 🙂