2
$\begingroup$

Question

Try to find the global optimal point of the function (reading Python for finance 2nd edition - Chapter 11. Mathematical Tools).

def fm(p):
    x, y = p
    return (np.sin(x) + 0.05 * x ** 2
          + np.sin(y) + 0.05 * y ** 2)

enter image description here

scipy.optimize.basinhopping says it finds the global minimum.

Find the global minimum of a function using the basin-hopping algorithm

However, it looks it does not find the global optimal point. Why is this and how can make it find the global optimal?

import numpy as np
import scipy.optimize as sco 
from pylab import plt, mpl
from mpl_toolkits.mplot3d import Axes3D

plt.style.use('seaborn')
mpl.rcParams['font.family'] = 'serif'
%matplotlib notebook

x = np.linspace(-10, 10, 50)
y = np.linspace(-10, 10, 50)
X, Y = np.meshgrid(x, y)
Z = fm((X, Y))

optima = sco.basinhopping(
    fo,
    (-10, 10),
    stepsize=0.1
)
# Optimal 
optima['x'] = np.append(optima['x'], fm((optima['x'][0], optima['x'][1])))
optima

Result

                        fun: 3.5447966927667616
 lowest_optimization_result:       fun: 3.5447966927667616
 hess_inv: array([[9.01401735e-01, 1.68119491e-03],
       [1.68119491e-03, 2.84089686e+00]])
      jac: array([2.98023224e-08, 2.98023224e-08])
  message: 'Optimization terminated successfully.'
     nfev: 24
      nit: 5
     njev: 6
   status: 0
  success: True
        x: array([-1.42755175,  9.67888407])
                    message: ['requested number of basinhopping iterations completed successfully']
      minimization_failures: 0
                       nfev: 2516
                        nit: 100
                       njev: 629
                          x: array([-1.42755175,  9.67888407,  3.54479669])

Plot:

fig = plt.figure(figsize=(10, 6))
ax = fig.gca(projection='3d')

# Function
surf = ax.plot_surface(
    X, Y, Z, 
    rstride=2, 
    cstride=2,
    cmap='coolwarm', 
    linewidth=0.5,
    antialiased=True
)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('f(x, y)')

# Optima
ax.plot(
    [optima['x'][0]], [optima['x'][1]], [optima['x'][2]], 
    color='r', marker='X', markersize=15
)
fig.colorbar(surf, shrink=0.5, aspect=5)

enter image description here

Brute

If used [scipy.optimize.brute][5], it may be able to find near point.

OX = []
OY = []
output = True
def fo(p):
    x, y = p
    z = np.sin(x) + 0.05 * x ** 2 + np.sin(y) + 0.05 * y ** 2
    if output == True:
        #print('%8.4f | %8.4f | %8.4f' % (x, y, z))
        OX.append(x)
        OY.append(y)
    return z

optima = sco.brute(
    fo, 
    (
        (-10, 10.1, 2), # Step X from -10 to 10.1 by interval 2
        (-10, 10.1, 2)  # Step Y from -10 to 10.1 by interval 2
    ), 
    finish=None
)  
OZ = fm((np.array(OX), np.array(OY)))

# Optimal 
optima = np.append(optima, fm((optima[0], optima[1])))

fig = plt.figure(figsize=(10, 6))
ax = fig.gca(projection='3d')

# Function
surf = ax.plot_surface(
    X, Y, Z, 
    rstride=2, 
    cstride=2,
    cmap='coolwarm', 
    linewidth=0.5,
    antialiased=True
)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('f(x, y)')

# Brute computation tack
ax.plot(np.array(OX), np.array(OY), np.array(OZ), ls="--", color='k', linewidth=0.5)

# Optima
ax.plot(
    [optima[0]], [optima[1]], [optima[2]], 
    color='r', marker='X', markersize=15
)
fig.colorbar(surf, shrink=0.5, aspect=5)

enter image description here

SHGO

scipy.optimize.shgo seems to work, too.

Finds the global minimum of a function using SHG optimization.

optima = sco.shgo(
    fo,
    [(-10, 10), (-10, 10)]
)
# Optimal 
optima['x'] = np.append(optima['x'], fm((optima['x'][0], optima['x'][1])))

fig = plt.figure(figsize=(10, 6))
ax = fig.gca(projection='3d')

# Function
surf = ax.plot_surface(
    X, Y, Z, 
    rstride=2, 
    cstride=2,
    cmap='coolwarm', 
    linewidth=0.5,
    antialiased=True
)
ax.set_xlabel('x')
ax.set_ylabel('y')
ax.set_zlabel('f(x, y)')

# Optima
ax.plot(
    [optima['x'][0]], [optima['x'][1]], [optima['x'][2]], 
    color='r', marker='X', markersize=15
)
fig.colorbar(surf, shrink=0.5, aspect=5)

enter image description here

Clarification

Even though it is "global Optimization", are there conditions or limitations to consider to make sure they find the global optimal?

Global Optimization
basinhopping(func, x0[, niter, T, stepsize, …])
Find the global minimum of a function using the basin-hopping algorithm
brute(func, ranges[, args, Ns, full_output, …])
Minimize a function over a given range by brute force.
differential_evolution(func, bounds[, args, …])
Finds the global minimum of a multivariate function.
shgo(func, bounds[, args, constraints, n, …])
Finds the global minimum of a function using SHG optimization.
dual_annealing(func, bounds[, args, …])
Find the global minimum of a function using Dual Annealing.

References

$\endgroup$
2

1 Answer 1

1
$\begingroup$

You can not make the basin-hopping algorithm find the global optimal point. Basin-hopping algorithm offers no guarantees of optimality.

There are common techniques for increasing the chances of finding global optimal point:

  • Run the algorithm for longer.
  • Progressively reduce the “temperature” parameter.
  • Progressively reduce the stepsize parameter.
  • Increase niter_success which increases the number of iterations without a change in global minimum candidate.
  • Try different random seeds.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.