Global Optimization

Unlike local optimization algorithms which start from one point and typically a local minimum, global optimization algorithms seek to find the best minimum in a defined region. This means that they typically have a much higher chance to find the global optimum for functions with several local minima but require many more evaluations of the objective. As an example, consider the Styblinski-Tang function:

\[f(x, y)= 0.5\cdot (x^4-16x^2+5x + y^4-16y^2+5y)\]

This function has four local minima, one of which is a global minimum.

For such low-dimensional problems with a small number of local minima, the deterministic DIviding RECTangles algorithm (DIRECT) is often a good candidate. We will compare the performance of DIRECT and the default derivate free local optimizer in simplenlopt, BOBYQA, initiated at (0, 0). Note that global optimizers do not require an initial guess x0 but bounds in the form [(min, max), (min, max), ...].

import simplenlopt
import plotly.graph_objects as go
import numpy as np

def styblinski_tang(pos):

    x, y = pos
    return 0.5 * (x**4 -16*x**2 + 5*x + y**4 - 16 * y**2 + 5 * y)

bounds = [(-4, 4), (-4, 4)]

x0 = np.array([0, 0])
res_bobyqa = simplenlopt.minimize(styblinski_tang, x0, bounds = bounds)
print("BOBYQA Optimum position: ", res_bobyqa.x)
print("BOBYQA Optimum value: ", res_bobyqa.fun)
print("BOBYQA Function evaluations: ", res_bobyqa.nfev)

res_direct = simplenlopt.direct(styblinski_tang, bounds)
print("DIRECT Optimum position: ", res_direct.x)
print("DIRECT Optimum value: ", res_direct.fun)
print("DIRECT Function evaluations: ", res_direct.nfev)

#Plot the function and the found minima
X = np.linspace(-4, 4, num = 100)
Y = np.linspace(-4, 4, num = 100)

BOBYQA Optimum position:  [-2.90353718  2.74681255]
BOBYQA Optimum value:  -64.19561235748431
BOBYQA Function evaluations:  28
DIRECT Optimum position:  [-2.90348693 -2.90362242]
DIRECT Optimum value:  -78.33233123410332
DIRECT Function evaluations:  255

#Plotly code to produce the above image. Unfortunately not rendering correctly on readthedocs.

XX, YY = np.meshgrid(X, Y)
F = 0.5 * (XX**4 -16*XX**2 + 5*XX + YY**4 - 16 * YY**2 + 5 * YY)

fig = go.Figure(data=[go.Surface(z=F, x=XX, y=YY, showscale = False)])
#fig.update_layout(
#    scene = dict(zaxis = dict(nticks=4, range=[0,10])))
fig.add_scatter3d(x=[res_bobyqa.x[0]], y=[res_bobyqa.x[1]], z=[res_bobyqa.fun], mode = 'markers', marker=dict(size=10, color='green'), name='BOBYQA')
fig.add_scatter3d(x=[res_direct.x[0]], y=[res_direct.x[1]], z=[res_direct.fun], mode = 'markers', marker=dict(size=10, color='black'), name='DIRECT')
camera = dict(
    eye=dict(x=-1.5, y=-1.5, z=0)
)

fig.update_layout(scene_camera=camera)
fig.show()