bundles / scipy latest / scipy / optimize / _shgo / shgo

function

`scipy.optimize._shgo:shgo`

source: /scipy/optimize/_shgo.py :22

Signature

   def     shgo (    func    ,    bounds    ,    args    =  ()   ,    constraints    =  None   ,    n    =  100   ,    iters    =  1   ,    callback    =  None   ,    minimizer_kwargs    =  None   ,    options    =  None   ,    sampling_method    =  simplicial   ,  * ,     workers    =  1     )

Summary

Finds the global minimum of a function using SHG optimization.

Extended Summary

SHGO stands for "simplicial homology global optimization".

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:

Instance of Bounds class.
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 : {Constraint, dict} or List of {Constraint, dict}, optional

Constraints definition. Only for COBYLA, COBYQA, SLSQP and trust-constr. See the tutorial ^[5] for further details on specifying constraints.

n : int, optional

Number of sampling points used in the construction of the simplicial complex. For the default simplicial sampling method 2**dim + 1 sampling points are generated instead of the default n=100. For all other specified values n sampling points are generated. For sobol, halton and other arbitrary sampling_methods n=100 or another specified number of sampling points are generated.

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:

method: method
args: args
options: options

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:

maxfev: maxfev
f_min: f_min
f_tol: f_tol
maxiter: maxiter
maxev: maxev
maxtime: maxtime
minhgrd: minhgrd

Objective function knowledge:

symmetry: symmetry
jac: jac
hess,hessp: hess, hessp

Algorithm settings:

minimize_every_iter: minimize_every_iter
local_iter: local_iter
infty_constraints: infty_constraints

Feedback:

disp: disp

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.

workers : int or map-like callable, optional

Sample and run the local serial minimizations in parallel. Supply -1 to use all available CPU cores, or an int to use that many Processes (uses multiprocessing.Pool <multiprocessing>).

Alternatively supply a map-like callable, such as multiprocessing.Pool.map for parallel evaluation. This evaluation is carried out as workers(func, iterable). Requires that func be pickleable.

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.

Notes

Global optimization using simplicial homology global optimization ^[1]. 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 ^[1].

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, COBYLA, or COBYQA 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.

Examples

First consider the problem of minimizing the Rosenbrock function, `rosen`:

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)

import numpy as np
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, n=150, constraints=cons)

✓

res

✗

g1(res.x), g2(res.x), h1(res.x)

`scipy.optimize._shgo:shgo`

Signature

Summary

Extended Summary

Parameters

Returns

Notes

Examples

Aliases

Referenced by

This package