DUAL_ANNEALING

Overview

The DUAL_ANNEALING function finds the global minimum of a multivariate objective function using the Dual Annealing optimization algorithm. This stochastic approach is particularly effective for complex, high-dimensional optimization problems with many local minima where gradient-based methods would become trapped.

Dual Annealing combines Generalized Simulated Annealing (GSA) with a local search strategy to efficiently explore the solution space. The algorithm is based on the work of Tsallis and Stariolo, generalizing Classical Simulated Annealing (CSA) and Fast Simulated Annealing (FSA). For implementation details, see the SciPy dual_annealing documentation and the source code on GitHub.

The algorithm uses a distorted Cauchy-Lorentz visiting distribution controlled by the visit parameter (q_v) to generate trial jump distances:

g_{q_v}(\Delta x) \propto \frac{[T_{q_v}(t)]^{-\frac{D}{3-q_v}}}{\left[1 + (q_v - 1)\frac{(\Delta x)^2}{[T_{q_v}(t)]^{\frac{2}{3-q_v}}}\right]^{\frac{1}{q_v-1} + \frac{D-1}{2}}}

where T_{q_v}(t) is the artificial temperature at time t and D is the problem dimensionality. The temperature decreases according to:

T_{q_v}(t) = T_{q_v}(1) \frac{2^{q_v - 1} - 1}{(1 + t)^{q_v - 1} - 1}

Higher initial_temp values allow broader exploration of the energy landscape, helping the algorithm escape local minima. The accept parameter controls acceptance probability of new states, while restart_temp_ratio triggers reannealing when the temperature drops to initial_temp * restart_temp_ratio. Setting no_local_search to TRUE performs traditional Generalized Simulated Annealing without local refinement.

The theoretical foundations are described in Tsallis (1988) on generalized Boltzmann-Gibbs statistics and Xiang et al. (1997, 2000) on generalized simulated annealing. For additional context on global optimization methods, see the Simulated Annealing Wikipedia article.

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

Excel Usage

=DUAL_ANNEALING(func_expr, bounds, maxiter, initial_temp, restart_temp_ratio, visit, accept, seed, no_local_search, x_zero)

func_expr (str, required): Objective expression in terms of x using x[i] notation for components.
bounds (list[list], required): 2D list of [min, max] pairs defining the search domain for each variable.
maxiter (int, optional, default: 1000): Maximum number of global search iterations.
initial_temp (float, optional, default: 5230): Initial temperature controlling the search scope.
restart_temp_ratio (float, optional, default: 0.00002): Temperature ratio in (0, 1] triggering restarts.
visit (float, optional, default: 2.62): Parameter governing the visiting distribution (must be > 0).
accept (float, optional, default: -5): Parameter controlling acceptance probability of new states.
seed (int, optional, default: null): Random seed for reproducible results.
no_local_search (bool, optional, default: false): If true, skip the local minimization polish stage.
x_zero (list[list], optional, default: null): Optional initial point as a single-row 2D list with one value per variable.

Returns (list[list]): 2D list [[x1, x2, …, objective]], or error message string.

Examples

Example 1: Demo case 1

Inputs:

func_expr	bounds		maxiter	initial_temp	restart_temp_ratio	visit	accept	seed	no_local_search	x_zero
(x[0]-1)^2 + (x[1]+2)^2	-5	5	1500	6000	0.000015	2.5	-4.5	101	false	0	0
	-5	5

Excel formula:

=DUAL_ANNEALING("(x[0]-1)^2 + (x[1]+2)^2", {-5,5;-5,5}, 1500, 6000, 0.000015, 2.5, -4.5, 101, FALSE, {0,0})

Expected output:

Result
1	-2	0

Example 2: Demo case 2

Inputs:

func_expr	bounds		seed	no_local_search	maxiter
(x[0])^2 + (x[1]-3)^2	-4	4	202	true	200
	0	6

Excel formula:

=DUAL_ANNEALING("(x[0])^2 + (x[1]-3)^2", {-4,4;0,6}, 202, TRUE, 200)

Expected output:

Result
0.03728196940073758	3.023874340233789	0.0019599293639962433

Example 3: Demo case 3

Inputs:

func_expr	bounds		initial_temp	restart_temp_ratio	visit	accept	seed
(x[0]-2)^2 + (x[1]-1)^2	-6	6	7000	0.00001	2.7	-3	404
	-6	6

Excel formula:

=DUAL_ANNEALING("(x[0]-2)^2 + (x[1]-1)^2", {-6,6;-6,6}, 7000, 0.00001, 2.7, -3, 404)

Expected output:

Result
2	1	0

Example 4: Demo case 4

Inputs:

func_expr	bounds		x_zero			seed	maxiter
(x[0]+1)^2 + (x[1]-2)^2 + (x[2]-0.5)^2	-5	5	-0.5	1.5	0	909	300
	-5	5
	-5	5

Excel formula:

=DUAL_ANNEALING("(x[0]+1)^2 + (x[1]-2)^2 + (x[2]-0.5)^2", {-5,5;-5,5;-5,5}, {-0.5,1.5,0}, 909, 300)

Expected output:

Result
-1	2	0.5	0

Python Code

import math
import re

import numpy as np
from scipy.optimize import dual_annealing as scipy_dual_annealing

def dual_annealing(func_expr, bounds, maxiter=1000, initial_temp=5230, restart_temp_ratio=2e-05, visit=2.62, accept=-5, seed=None, no_local_search=False, x_zero=None):
    """
    Minimize a multivariate function using dual annealing.

    See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.dual_annealing.html

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

    Args:
        func_expr (str): Objective expression in terms of x using x[i] notation for components.
        bounds (list[list]): 2D list of [min, max] pairs defining the search domain for each variable.
        maxiter (int, optional): Maximum number of global search iterations. Default is 1000.
        initial_temp (float, optional): Initial temperature controlling the search scope. Default is 5230.
        restart_temp_ratio (float, optional): Temperature ratio in (0, 1] triggering restarts. Default is 2e-05.
        visit (float, optional): Parameter governing the visiting distribution (must be > 0). Default is 2.62.
        accept (float, optional): Parameter controlling acceptance probability of new states. Default is -5.
        seed (int, optional): Random seed for reproducible results. Default is None.
        no_local_search (bool, optional): If true, skip the local minimization polish stage. Default is False.
        x_zero (list[list], optional): Optional initial point as a single-row 2D list with one value per variable. Default is None.

    Returns:
        list[list]: 2D list [[x1, x2, ..., objective]], or error message string.
    """
    # Validate func_expr
    if not isinstance(func_expr, str):
        return "Invalid input: func_expr must be a string."
    if func_expr.strip() == "":
        return "Invalid input: func_expr must be a non-empty string."
    if not re.search(r'\bx\b', func_expr):
        return "Invalid input: func_expr must reference variable x (e.g., x[0])."

    # Convert caret notation to Python exponentiation
    func_expr = re.sub(r'\^', '**', func_expr)

    # Validate bounds
    if not isinstance(bounds, list) or len(bounds) == 0:
        return "Invalid input: bounds must be a 2D list of [min, max] pairs."
    processed_bounds = []
    for idx, bound in enumerate(bounds):
        if not isinstance(bound, list) or len(bound) != 2:
            return "Invalid input: each bound must be a [min, max] pair."
        try:
            lower = float(bound[0])
            upper = float(bound[1])
        except (TypeError, ValueError):
            return "Invalid input: bounds must contain numeric values."
        if lower > upper:
            return f"Invalid input: lower bound must not exceed upper bound for variable index {idx}."
        processed_bounds.append((lower, upper))

    dimension = len(processed_bounds)

    # Validate numeric parameters
    try:
        maxiter = int(maxiter)
    except (TypeError, ValueError):
        return "Invalid input: maxiter must be an integer."
    if maxiter <= 0:
        return "Invalid input: maxiter must be positive."

    try:
        initial_temp = float(initial_temp)
        restart_temp_ratio = float(restart_temp_ratio)
        visit = float(visit)
        accept = float(accept)
    except (TypeError, ValueError):
        return "Invalid input: initial_temp, restart_temp_ratio, visit, and accept must be numeric."

    if initial_temp <= 0:
        return "Invalid input: initial_temp must be positive."
    if not (0 < restart_temp_ratio <= 1):
        return "Invalid input: restart_temp_ratio must be in the interval (0, 1]."
    if visit <= 0:
        return "Invalid input: visit must be positive."

    rng_seed = None
    if seed is not None:
        try:
            rng_seed = int(seed)
        except (TypeError, ValueError):
            return "Invalid input: seed must be an integer."

    if not isinstance(no_local_search, bool):
        return "Invalid input: no_local_search must be a boolean."

    x0_vector = None
    if x_zero is not None:
        try:
            arr = np.array(x_zero, dtype=float).flatten()
        except Exception:
            return "Invalid input: x_zero must contain numeric values."
        if arr.size != dimension:
            return "Invalid input: x_zero length must match number of variables."
        x0_vector = arr

    # Build complete safe_globals dictionary for expression evaluation
    safe_globals = {
        "math": math,
        "np": np,
        "numpy": np,
        "__builtins__": {},
    }
    # Add all math module functions
    safe_globals.update({
        name: getattr(math, name)
        for name in dir(math)
        if not name.startswith("_")
    })
    # Add common numpy/math function aliases
    safe_globals.update({
        "sin": np.sin,
        "cos": np.cos,
        "tan": np.tan,
        "asin": np.arcsin,
        "arcsin": np.arcsin,
        "acos": np.arccos,
        "arccos": np.arccos,
        "atan": np.arctan,
        "arctan": np.arctan,
        "sinh": np.sinh,
        "cosh": np.cosh,
        "tanh": np.tanh,
        "exp": np.exp,
        "log": np.log,
        "ln": np.log,
        "log10": np.log10,
        "sqrt": np.sqrt,
        "abs": np.abs,
        "pow": np.power,
        "pi": math.pi,
        "e": math.e,
        "inf": math.inf,
        "nan": math.nan,
    })

    def objective(x_vector):
        try:
            local_x = [float(val) for val in np.atleast_1d(x_vector)]
            value = eval(func_expr, safe_globals, {"x": local_x})
        except Exception as exc:
            raise ValueError(f"Error evaluating func_expr: {exc}")
        try:
            result_value = float(value)
        except (TypeError, ValueError):
            raise ValueError("Objective expression must return a scalar numeric value.")
        if math.isnan(result_value) or math.isinf(result_value):
            raise ValueError("Objective evaluation produced NaN or infinity.")
        return result_value

    try:
        result = scipy_dual_annealing(
            objective,
            bounds=processed_bounds,
            maxiter=maxiter,
            initial_temp=initial_temp,
            restart_temp_ratio=restart_temp_ratio,
            visit=visit,
            accept=accept,
            seed=rng_seed,
            no_local_search=no_local_search,
            x0=x0_vector,
        )
    except ValueError as exc:
        return f"Error during dual annealing: {exc}"
    except Exception as exc:
        return f"Error during dual annealing: {exc}"

    if not result.success:
        return f"Dual annealing failed: {result.message}"

    if result.x is None or result.fun is None:
        return "Dual annealing failed: missing solution data."

    try:
        solution_vector = [float(val) for val in result.x]
    except (TypeError, ValueError):
        return "Error converting solution vector to floats."

    objective_value = float(result.fun)

    return [solution_vector + [objective_value]]

Overview

Excel Usage

Examples

Python Code

Online Calculator