Loading [MathJax]/extensions/tex2jax.js
scipy 1.10.1 Pypi GitHub Homepage
Other Docs

NotesParametersReturns
shgo(func, bounds, args=(), constraints=None, n=None, iters=1, callback=None, minimizer_kwargs=None, options=None, sampling_method='simplicial')

SHGO stands for "simplicial homology global optimization".

Notes

Global optimization using simplicial homology global optimization . Appropriate for solving general purpose NLP and blackbox optimization problems to global optimality (low-dimensional problems).

In general, the optimization problems are of the form

minimize f(x) subject to

g_i(x) >= 0,  i = 1,...,m
h_j(x)  = 0,  j = 1,...,p

where x is a vector of one or more variables. f(x) is the objective function R^n -> R, g_i(x) are the inequality constraints, and h_j(x) are the equality constraints.

Optionally, the lower and upper bounds for each element in x can also be specified using the bounds argument.

While most of the theoretical advantages of SHGO are only proven for when f(x) is a Lipschitz smooth function, the algorithm is also proven to converge to the global optimum for the more general case where f(x) is non-continuous, non-convex and non-smooth, if the default sampling method is used .

The local search method may be specified using the minimizer_kwargs parameter which is passed on to scipy.optimize.minimize. By default, the SLSQP method is used. In general, it is recommended to use the SLSQP or COBYLA local minimization if inequality constraints are defined for the problem since the other methods do not use constraints.

The halton and sobol method points are generated using scipy.stats.qmc. Any other QMC method could be used.

Parameters

func : callable

The objective function to be minimized. Must be in the form f(x, *args), where x is the argument in the form of a 1-D array and args is a tuple of any additional fixed parameters needed to completely specify the function.

bounds : sequence or `Bounds`

Bounds for variables. There are two ways to specify the bounds:

  1. Instance of Bounds class.
  2. Sequence of (min, max) pairs for each element in x.
args : tuple, optional

Any additional fixed parameters needed to completely specify the objective function.

constraints : dict or sequence of dict, optional

Constraints definition. Function(s) R**n in the form

g(x) >= 0 applied as g : R^n -> R^m
h(x) == 0 applied as h : R^n -> R^p

Each constraint is defined in a dictionary with fields:

Equality constraint means that the constraint function result is to be zero whereas inequality means that it is to be non-negative. Note that COBYLA only supports inequality constraints.

n : int, optional

Number of sampling points used in the construction of the simplicial complex. Note that this argument is only used for sobol and other arbitrary sampling_methods. In case of sobol, it must be a power of 2: n=2**m, and the argument will automatically be converted to the next higher power of 2. Default is 100 for sampling_method='simplicial' and 128 for sampling_method='sobol'.

iters : int, optional

Number of iterations used in the construction of the simplicial complex. Default is 1.

callback : callable, optional

Called after each iteration, as callback(xk), where xk is the current parameter vector.

minimizer_kwargs : dict, optional

Extra keyword arguments to be passed to the minimizer scipy.optimize.minimize Some important options could be:

options : dict, optional

A dictionary of solver options. Many of the options specified for the global routine are also passed to the scipy.optimize.minimize routine. The options that are also passed to the local routine are marked with "(L)".

Stopping criteria, the algorithm will terminate if any of the specified criteria are met. However, the default algorithm does not require any to be specified:

Objective function knowledge:

Algorithm settings:

Feedback:

sampling_method : str or function, optional

Current built in sampling method options are halton, sobol and simplicial. The default simplicial provides the theoretical guarantee of convergence to the global minimum in finite time. halton and sobol method are faster in terms of sampling point generation at the cost of the loss of guaranteed convergence. It is more appropriate for most "easier" problems where the convergence is relatively fast. User defined sampling functions must accept two arguments of n sampling points of dimension dim per call and output an array of sampling points with shape n x dim.

Returns

res : OptimizeResult

The optimization result represented as a OptimizeResult object. Important attributes are: x the solution array corresponding to the global minimum, fun the function output at the global solution, xl an ordered list of local minima solutions, funl the function output at the corresponding local solutions, success a Boolean flag indicating if the optimizer exited successfully, message which describes the cause of the termination, nfev the total number of objective function evaluations including the sampling calls, nlfev the total number of objective function evaluations culminating from all local search optimizations, nit number of iterations performed by the global routine.

Finds the global minimum of a function using SHG optimization.

Examples

First consider the problem of minimizing the Rosenbrock function, `rosen`:
import numpy as np
from scipy.optimize import rosen, shgo
bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
result = shgo(rosen, bounds)
result.x, result.fun
Note that bounds determine the dimensionality of the objective function and is therefore a required input, however you can specify empty bounds using ``None`` or objects like ``np.inf`` which will be converted to large float numbers.
bounds = [(None, None), ]*4
result = shgo(rosen, bounds)
result.x
Next, we consider the Eggholder function, a problem with several local minima and one global minimum. We will demonstrate the use of arguments and the capabilities of `shgo`. (https://en.wikipedia.org/wiki/Test_functions_for_optimization)
def eggholder(x):
    return (-(x[1] + 47.0)
            * np.sin(np.sqrt(abs(x[0]/2.0 + (x[1] + 47.0))))
            - x[0] * np.sin(np.sqrt(abs(x[0] - (x[1] + 47.0))))
            )
bounds = [(-512, 512), (-512, 512)]
`shgo` has built-in low discrepancy sampling sequences. First, we will input 64 initial sampling points of the *Sobol'* sequence:
result = shgo(eggholder, bounds, n=64, sampling_method='sobol')
result.x, result.fun
`shgo` also has a return for any other local minima that was found, these can be called using:
result.xl
result.funl
These results are useful in applications where there are many global minima and the values of other global minima are desired or where the local minima can provide insight into the system (for example morphologies in physical chemistry [4]_).
If we want to find a larger number of local minima, we can increase the number of sampling points or the number of iterations. We'll increase the number of sampling points to 64 and the number of iterations from the default of 1 to 3. Using ``simplicial`` this would have given us 64 x 3 = 192 initial sampling points.
result_2 = shgo(eggholder, bounds, n=64, iters=3, sampling_method='sobol')
len(result.xl), len(result_2.xl)
Note the difference between, e.g., ``n=192, iters=1`` and ``n=64, iters=3``. In the first case the promising points contained in the minimiser pool are processed only once. In the latter case it is processed every 64 sampling points for a total of 3 times.
To demonstrate solving problems with non-linear constraints consider the following example from Hock and Schittkowski problem 73 (cattle-feed) [3]_::
minimize: f = 24.55 * x_1 + 26.75 * x_2 + 39 * x_3 + 40.50 * x_4
subject to: 2.3 * x_1 + 5.6 * x_2 + 11.1 * x_3 + 1.3 * x_4 - 5 >= 0,
12 * x_1 + 11.9 * x_2 + 41.8 * x_3 + 52.1 * x_4 - 21 -1.645 * sqrt(0.28 * x_1**2 + 0.19 * x_2**2 + 20.5 * x_3**2 + 0.62 * x_4**2) >= 0,
x_1 + x_2 + x_3 + x_4 - 1 == 0,
1 >= x_i >= 0 for all i
The approximate answer given in [3]_ is::
f([0.6355216, -0.12e-11, 0.3127019, 0.05177655]) = 29.894378
def f(x):  # (cattle-feed)
    return 24.55*x[0] + 26.75*x[1] + 39*x[2] + 40.50*x[3]
def g1(x):
    return 2.3*x[0] + 5.6*x[1] + 11.1*x[2] + 1.3*x[3] - 5  # >=0
def g2(x):
    return (12*x[0] + 11.9*x[1] +41.8*x[2] + 52.1*x[3] - 21
            - 1.645 * np.sqrt(0.28*x[0]**2 + 0.19*x[1]**2
                            + 20.5*x[2]**2 + 0.62*x[3]**2)
            ) # >=0
def h1(x):
    return x[0] + x[1] + x[2] + x[3] - 1  # == 0
cons = ({'type': 'ineq', 'fun': g1},
        {'type': 'ineq', 'fun': g2},
        {'type': 'eq', 'fun': h1})
bounds = [(0, 1.0),]*4
res = shgo(f, bounds, iters=3, constraints=cons)
res
g1(res.x), g2(res.x), h1(res.x)
See :

Local connectivity graph

Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.

Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)

SVG is more flexible but power hungry; and does not scale well to 50 + nodes.

scipy.stats.qmcqmc

All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them


GitHub : /scipy/optimize/_shgo.py#19
type: <class 'function'>
Commit: