Welcome to noisyopt’s documentation!¶

noisyopt is concerned with solving an (possibly bound-constrained) optimization problem of the kind

\[\min_{\boldsymbol x} f(\boldsymbol x) = \min_{\boldsymbol x} \mathbb{E}[F(\boldsymbol x, \xi)]\]

where evaluations of the function f are not directly possible, but only evaluation of the function F. The expectation value of F is f, but F also depends on some random noise. Such optimization problems are known under various names, such as stochastic approximation, stochastic optimization/programming, or noisy optimization. They arise in various contexts from Simulation-based optimization, to machine learning.

To solve such optimization problems the package currently implements two (derivative-free) algorithms:

a robust pattern search algorithm with an adaptive number of function evaluations [Mayer2016]
a stochastic approximation algorithm, namely simultaneous perturbation stochastic approximation [Spall1998]

Further algorithms might be added in the future – you are invited to contribute! The package also contains a function to find the root of a noisy function by a bisection algorithm with an adaptive number of function evaluations.

Noisyopt is concerned with local optimization, if you are interested in global optimization you might want to have a look at Bayesian optimization techniques (see e.g. scikit-optimize). For optimizing functions that are not noisy take a look at scipy.optimize.

Documentation¶

You can install noisyopt using pip:

pip install noisyopt

Minimal usage example:

import numpy as np
from noisyopt import minimizeCompass

def obj(x):
    return (x**2).sum() + 0.1*np.random.randn()

res = minimizeCompass(obj, x0=[1.0, 2.0], deltatol=0.1, paired=False)

For further documentation see below or the usage examples.

Tutorial - Minimize a noisy function¶

The following tutorial shows how to find a local minimum of a simple function using the noisyopt library.

The problem is to solve the following optimization problem

\[ \begin{align}\begin{aligned}\min_{\boldsymbol x \in \Omega} f\\f(x_1, x_2) = x_1^2 + x_2^2\\\Omega = [-3.0, 3.0] \times [0.5, 5.0],\end{aligned}\end{align} \]

where we do not have access to the function f directly, but only to some noisy approximation.

\[\tilde f = f + \xi, \quad \xi \sim \mathcal{N}(0, 0.1^2).\]

This is obviously a toy example (the solution (0.0, 0.5) is obvious from inspection of the problem), but similar problems arise in practice.

First we need to import the minimizeCompass function from the noisyopt package:

>>> import numpy as np
>>> from noisyopt import minimizeCompass

Then we need to define the objective of the function:

>>> def obj(x):
  ...     return (x**2).sum() + 0.1*np.random.randn()

We now define the domain of the problem using bound constraints:

>>> bounds = [[-3.0, 3.0], [0.5, 5.0]]

And we define the initial guess:

>>> x0 = np.array([-2.0, 2.0])

The pattern search based optimization algorithm is called using the minimizeCompass function. The minimizeCompass functions accepts the problem objective obj and bound constraints:

>>> res = minimizeCompass(obj, bounds=bounds, x0=x0, deltatol=0.1, paired=False)

It is possible to further customize the algorithm using the parameters of the minimizeCompass function (see noisyopt.minimizeCompass()). Alternatively we can also try a different algorithm implementing a simultaneous perturbation stochastic approximation algorithm (see noisyopt.minimizeSPSA()).

The minimizeCompass function returns a result object res making accessible among other the optimal point, res.x, and the value of the objective at the optimum, res.fun:

>>> print(res)
    free: array([False, False], dtype=bool)
     fun: 0.25068227287617101
   funse: 0.0022450327079771111
 message: 'convergence within deltatol'
    nfev: 9510
     nit: 9
 success: True
       x: array([ 0. ,  0.5])

As instructed, the algorithm finds the correct solution respecting the bounds (the unconstrained optimum would be at [0, 0]).

Further examples¶

A usage example on a real-world problem can be found at http://github.com/andim/evolimmune/ including using the noisyopt.bysect() routine.

API Reference¶

minimizeCompass¶

noisyopt.minimizeCompass(func, x0, args=(), bounds=None, scaling=None, redfactor=2.0, deltainit=1.0, deltatol=0.001, feps=1e-15, errorcontrol=True, funcNinit=30, funcmultfactor=2.0, paired=True, alpha=0.05, disp=False, callback=None, **kwargs)¶

Minimization of an objective function by a pattern search.

The search algorithm is a simple compass search along coordinate directions. If the function evaluation contains a stochastic element, then the function is called repeatedly to average over the stochasticity in the function evaluation. The number of evaluations is adapted dynamically to ensure convergence.

Parameters:

func: callable :

objective function to be minimized: called as func(x, *args, **kwargs), if paired=True, then called with keyword argument seed additionally

x0: array-like :

starting point

args: tuple :

extra arguments to be supplied to func

bounds: array-like :

bounds on the variables

scaling: array-like :

scaling by which to multiply step size and tolerances along different dimensions

redfactor: float :

reduction factor by which to reduce delta if no reduction direction found

deltainit: float :

inital pattern size

deltatol: float :

smallest pattern size

feps: float :

smallest difference in function value to resolve

errorcontrol: boolean :

whether to control error of simulation by repeated sampling

funcNinit: int, only for errorcontrol=True :

initial number of iterations to use for the function, do not set much lower than 30 as otherwise there is no sufficient statistics for function comparisons

funcmultfactor: float, only for errorcontrol=True :

multiplication factor by which to increase number of iterations of function

paired: boolean, only for errorcontrol=True :

compare for same random seeds

alpha: float, only for errorcontrol=True :

significance level of tests, the higher this value the more statistics is acquired, which decreases the risk of taking a step in a non-descent direction at the expense of higher computational cost per iteration

disp: boolean :

whether to output status updates during the optimization

callback: callable :

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

Returns:

scipy.optimize.OptimizeResult object :

special entry: free Boolean array indicating parameters that are unconstrained at the optimum (within feps)

minimizeSPSA¶

noisyopt.minimizeSPSA(func, x0, args=(), bounds=None, niter=100, paired=True, a=1.0, c=1.0, disp=False, callback=None)¶

Minimization of an objective function by a simultaneous perturbation stochastic approximation algorithm.

Parameters:

func: callable :

objective function to be minimized

x0: array-like :

starting point

args: tuple :

extra arguments to be supplied to func

bounds: array-like :

bounds on the variables

scaling: array-like :

scaling by which to multiply step size and tolerances along different dimensions

niter: int :

maximum number of iterations of the algorithm

paired: boolean :

calculate gradient for same random seeds

a: float :

algorithm scaling parameter for step size

c: float :

algorithm scaling parameter for evaluation step size

disp: boolean :

whether to output status updates during the optimization

callback: callable :

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

Returns:

scipy.optimize.OptimizeResult object :

minimize¶

noisyopt.minimize(*args, **kwargs)¶: deprecated: use minimizeCompass instead

bisect¶

noisyopt.bisect(func, a, b, xtol=1e-06, errorcontrol=True, testkwargs={}, outside='extrapolate', ascending=None, disp=False)¶

Find root by bysection search.

If the function evaluation is noisy then use errorcontrol=True for adaptive sampling of the function during the bisection search.

Parameters:

func: callable :

Function of which the root should be found. If errorcontrol=True then the function should be derived from AverageBase.

a, b: float :

initial interval

xtol: float :

target tolerance for interval size

errorcontrol: boolean :

if true, assume that function is instance of DifferenceFunction

testkwargs: only for `errorcontrol=True` :

see AverageBase.test0

outside: [‘extrapolate’, ‘raise’] :

How to handle the case where f(a) and f(b) have same sign, i.e. where the root lies outside of the interval. If ‘raise’ throws a BisectException in this case.

ascending: allow passing in directly whether function is ascending or not :

if ascending=True then it is assumed without check that f(a) < 0 and f(b) > 0 if ascending=False then it is assumed without check that f(a) > 0 and f(b) < 0

Returns:

float, root of function :

Average classes¶

These helper classes perform averages over function values. They provide extra logic such as tests whether function values differ signficantly.

class noisyopt.AverageBase(N=30, paired=False)¶

Base class for averaged evaluation of noisy functions.

Attributes

`N`	number of evaluations

Methods

test0(x[, type_, alpha, force, eps, maxN]) Compares the mean at x to zero.

N¶: number of evaluations

test0(x, type_='smaller', alpha=0.05, force=False, eps=1e-05, maxN=10000)¶

Compares the mean at x to zero.

Parameters:

type_: in [‘smaller’, ‘equality’] :

type of comparison to perform

alpha: float :

significance level

force: boolean :

if true increase number of samples until equality rejected or meanse=eps or N > maxN

eps: float :

maxN: int :

class noisyopt.AveragedFunction(func, fargs=None, **kwargs)¶

Average of a function’s return value over a number of runs.

Caches previous results.

Attributes

`N`	number of evaluations

Methods

__call__(x)

diffse(x1, x2) Standard error of the difference between the function values at x1 and x2

test(xtest, x[, type_, alpha])

Parameters:

test0(x[, type_, alpha, force, eps, maxN]) Compares the mean at x to zero.

N¶: number of evaluations

diffse(x1, x2)¶: Standard error of the difference between the function values at x1 and x2

test(xtest, x, type_='smaller', alpha=0.05)¶

Parameters:

type_: in [‘smaller’, ‘equality’] :

type of comparison to perform

alpha: float :

significance level

test0(x, type_='smaller', alpha=0.05, force=False, eps=1e-05, maxN=10000)¶

Compares the mean at x to zero.

Parameters:

type_: in [‘smaller’, ‘equality’] :

type of comparison to perform

alpha: float :

significance level

force: boolean :

if true increase number of samples until equality rejected or meanse=eps or N > maxN

eps: float :

maxN: int :

class noisyopt.DifferenceFunction(func1, func2, fargs1=None, fargs2=None, **kwargs)¶

Averages the difference of two function’s return values over a number of runs

Attributes

`N`	number of evaluations

Methods

`__call__`(x)
`test0`(x[, type_, alpha, force, eps, maxN])	Compares the mean at x to zero.

N¶: number of evaluations

test0(x, type_='smaller', alpha=0.05, force=False, eps=1e-05, maxN=10000)¶

Compares the mean at x to zero.

Parameters:

type_: in [‘smaller’, ‘equality’] :

type of comparison to perform

alpha: float :

significance level

force: boolean :

if true increase number of samples until equality rejected or meanse=eps or N > maxN

eps: float :

maxN: int :

Release history¶

0.2.2¶

added PendingDeprecationWarning for minimize function

0.2.1¶

setup.py installation requirements fixed

0.2¶

renamed minimize to minimizeCompass for clarity
SPSA algorithm now only uses feasible evaluations
improved documentation

0.1.1¶

support for Python 3
defaulting to errorcontrol=True and paired=True
added option to add callback function to optimization function
Bug fixes

0.1¶

Initial release

Welcome to noisyopt’s documentation!¶

Documentation¶

Tutorial - Minimize a noisy function¶

Further examples¶

API Reference¶

minimizeCompass¶

minimizeSPSA¶

minimize¶

bisect¶

Average classes¶

Release history¶

0.2.2¶

0.2.1¶

0.2¶

0.1.1¶

0.1¶

Further reading¶