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)

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)

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)

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)

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

• Python for finance 2nd edition - Chapter 11. Mathematical Tools


• Which Optimization method to use?


• Optimization and Root Finding (scipy.optimize)