BASIN_HOPPING

Overview

The BASIN_HOPPING function provides a robust global optimization method for single-variable functions using the basinhopping algorithm from SciPy. Basinhopping is a stochastic global optimization technique that combines random perturbations with local minimization to escape local minima and search for the global minimum of a scalar function. It is especially useful for non-convex optimization problems where the objective function may have multiple local minima or complex landscapes.

The basinhopping algorithm seeks to solve

\min_x f(x)

where $f(x)$ is the objective function. At each iteration, the algorithm performs a random displacement:

x_{\text{trial}} = x_{\text{current}} + \delta

where $\delta$ is a random vector (with user-defined step size). A local minimization is then performed starting from $x_{\text{trial}}$ to find:

x_{\text{min}} = \operatorname{argmin}_x f(x)

The new minimum is accepted with probability

P = \begin{cases} 1 & \text{if } \Delta f \leq 0 \\ \exp(-\Delta f / T) & \text{if } \Delta f > 0 \end{cases}

where $\Delta f = f(x_{\text{min}}) - f(x_{\text{current}})$ and $T$ is the temperature parameter. This approach allows the algorithm to escape local minima by occasionally accepting worse solutions, similar to simulated annealing, and increases the chance of finding the global minimum.

This example function is provided as-is without any representation of accuracy.

Usage

To use the function in Excel:


=BASIN_HOPPING(func_expr, x_zero, [niter], [T], [stepsize], [minimizer_method])

func_expr (string, required): Math expression as a string which accepts a single scalar argument and returns a scalar value. Example: "x**2 + 10*sin(x)"
x_zero (float, required): Initial guess for the variable. Example: 0
niter (int, optional): Number of basinhopping iterations. Example: 200
T (float, optional): Temperature parameter for the acceptance test. Example: 1.0
stepsize (float, optional): Step size for random displacement. Example: 0.5
minimizer_method (string, optional): Local minimization method to use (e.g., "L-BFGS-B", "BFGS", "Powell"). Example: "L-BFGS-B"

The function returns a 2D list: [[minimum, x_min]], where the first value is the minimum found and the second value is the location of the minimum.

Examples

Example 1: Global Minimum of a Sine-Modified Quadratic

In Excel:


=BASIN_HOPPING("x**2 + 10*sin(x)", 0, 200, 1.0, 0.5, "L-BFGS-B")

Expected output:

Minimum Value	x_min
-7.945	-1.306

This means the minimum value is approximately -7.945 at $x \approx -1.306$ .

Example 2: Quartic with Cosine Perturbation

In Excel:


=BASIN_HOPPING("(x**2 - 4)**2 + 5*cos(2*x)", 2, 200, 1.0, 0.5, "L-BFGS-B")

Expected output:

Minimum Value	x_min
0.0	2.0

This means the minimum value is 0.0 at $x = 2.0$ .

Python Code


import numpy as np
from scipy.optimize import basinhopping as scipy_basinhopping
import math
import re
 
def basin_hopping(func_expr, x_zero, niter=100, T=1.0, stepsize=0.5, minimizer_method='L-BFGS-B'):
    """Finds the global minimum of a single-variable function using the basinhopping algorithm.
 
    Args:
        func_expr (str): Math expression as a string (e.g., 'x**2 + 10*sin(x)').
        x_zero (float): Initial guess for the variable.
        niter (int, optional): Number of basinhopping iterations. Default is 100.
        T (float, optional): Temperature parameter for the acceptance test. Default is 1.0.
        stepsize (float, optional): Step size for random displacement. Default is 0.5.
        minimizer_method (str, optional): Local minimization method to use. Default is 'L-BFGS-B'.
 
    Returns:
        2D list [[minimum, x_min]] or [[error_message]]
    """
    if not isinstance(x_zero, (int, float)):
        return [["x_zero must be a scalar (float or int) for single-variable functions."]]
    if not isinstance(func_expr, str):
        return [["func_expr must be a string representing a math expression."]]
    funcs = ['sin', 'cos', 'tan', 'exp', 'sqrt', 'log', 'asin', 'acos', 'atan', 'sinh', 'cosh', 'tanh']
    def repl(m):
        return f"math.{m.group(1)}"
    pattern = r'(?<![\w.])(' + '|'.join(funcs) + r')(?=\s*\()'
    expr = re.sub(pattern, repl, func_expr)
    func_expr_lambda = f"lambda x: {expr}"
    try:
        user_func = eval(func_expr_lambda, {"np": np, "math": math, "sin": math.sin, "cos": math.cos, "exp": math.exp, "sqrt": math.sqrt})
    except Exception as e:
        return [[f"Invalid function expression: {str(e)}"]]
    if not callable(user_func) or user_func.__code__.co_argcount != 1:
        return [["func_expr must be a math expression of a single variable (e.g., 'x**2 + 10*sin(x)')."]]
    def func(x):
        try:
            val = user_func(float(x))
            if isinstance(val, np.ndarray):
                return float(val.item())
            return float(val)
        except Exception:
            return float('inf')
    x0_val = float(x_zero)
    if not isinstance(niter, int) or niter <= 0:
        return [["niter must be a positive integer."]]
    if not isinstance(T, (int, float)) or T <= 0:
        return [["T must be a positive number."]]
    if not isinstance(stepsize, (int, float)) or stepsize <= 0:
        return [["stepsize must be a positive number."]]
    if not isinstance(minimizer_method, str):
        return [["minimizer_method must be a string."]]
    try:
        result = scipy_basinhopping(func, x0_val, niter=niter, T=T, stepsize=stepsize, minimizer_kwargs={"method": minimizer_method})
        x_min = result.x
        min_val = result.fun
        if isinstance(min_val, np.ndarray):
            min_val = float(min_val.item())
        else:
            min_val = float(min_val)
        if isinstance(x_min, np.ndarray):
            x_min_list = x_min.tolist()
        else:
            x_min_list = [float(x_min)]
        return [[min_val] + x_min_list]
    except Exception as e:
        return [[str(e)]]

Live Notebook

Edit this function in a live notebook .