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".
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.
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 for variables. There are two ways to specify the bounds:
(min, max)
pairs for each element in x.Any additional fixed parameters needed to completely specify the objective function.
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.
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'
.
Number of iterations used in the construction of the simplicial complex. Default is 1.
Called after each iteration, as callback(xk)
, where xk
is the current parameter vector.
Extra keyword arguments to be passed to the minimizer scipy.optimize.minimize
Some important options could be:
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:
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.
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.
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
bounds = [(None, None), ]*4
result = shgo(rosen, bounds)
result.x
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)]
result = shgo(eggholder, bounds, n=64, sampling_method='sobol')
result.x, result.fun
result.xl
result.funl
result_2 = shgo(eggholder, bounds, n=64, iters=3, sampling_method='sobol')
len(result.xl), len(result_2.xl)
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)
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.
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