Globtim

Globtim is a Julia package for solving global optimization problems via polynomial approximations. It is registered in the Julia General registry (pkg> add Globtim HomotopyContinuation), and the documentation is available here. The underlying algorithm is described in this paper.

For this method to work, we only require access to evaluations of the objective function f.

We call this method global because we seek to compute all local minima of the objective function f, a real continuous function defined over some given rectangular domain in \(\mathbb{R}^n\).

Our method is carried out in 3 main steps:

  1. The input function f is sampled on a tensorized Chebyshev grid
  2. A polynomial approximant is constructed via a discrete least squares
  3. The polynomial system of Partial derivatives is solved by either homotopy continuation (numerical method) or through exact polynomial system solving (symbolic method)

Level Set Examples

Critical points of the Deuflhard function
Six-hump camel polynomial level set
Left: critical points of the Deuflhard function computed with Globtim, with local minima (red diamonds) and the remaining critical points (white circles). Right: a degree-6 Chebyshev approximant of the six-hump camel function, with the critical points of the polynomial and the refined minima.

2D Optimization Examples

Here we consider the Trefethen function from the Problem 4 of the 100 Digit challenge. All of its critical points displayed in orange have been computed using the Globtim package over the \([-.2, .2]^2\) domain.

\[f(x, y) = \exp(\sin(50 x_1)) + \sin(60 \exp(x_2)) + \sin(70 \sin(x_1)) + \sin(\sin(80 x_2)) - \sin(10 (x_1 + x_2)) + (x_1^2 + x_2^2) / 4\]

This function has \(2720\) critical points in \([-1, 1]^2\), which is slightly too much for us, at least for the moment, hence we subdivide the domain.

Camel Function Example

Below is a template of how the Globtim package can be used to compute all local minimizers of the Camel function: