proxtoolbox.algorithms.samsara package¶

Provides the class Samsara that is an unconstrained optimiser for real-valued functions.

Running Samsara¶

Samsara is written for Python 3 (but works with Python 2.7) and has the following dependencies:

numpy

matplotlib

You should also add the location of your samsara folder to the PYTHONPATH environment variable.

To use Samsara with your project copy the driver.py file from the samsara folder to any destination you like and edit it with the function you want optimised.

Running the Tests¶

To run the tests you will need to have MATLAB, the matlab module for Python installed (the module can be found with your installed MATLAB program in <path-to-matlab>/extern/engines/python) and pytest installed. To run the test you then execute

>>> py.test <test_file>

Submodules¶

proxtoolbox.algorithms.samsara.hessian module¶

Contains all implementations of hessian products.

proxtoolbox.algorithms.samsara.hessian.delta_MSB2(S_mat, Y_mat, alpha)[source]¶

Scaling for the MSB2 matrix.

Parameters:	S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients. alpha : float A regularisation parameter.
Returns:	float TODO

See also

delta_invBFGS: Alternative function.

samsara.samsara.Normsqresid, samsara.step_finder.Step_generator

proxtoolbox.algorithms.samsara.hessian.delta_invBFGS(mem, S_mat, Y_mat)[source]¶

Scaling for the inverse BFGS matrix

Parameters:	mem : int The step to use. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients.
Returns:	float TODO

See also

BFGS1_product: TODO
delta_MSB2: Alternative function.

proxtoolbox.algorithms.samsara.hessian.scaler_wrapper(Scaler, mem, S_mat, Y_mat, alpha)[source]¶

A wrapper for all scaler functions.

Used to have unified function calls.

Parameters:	Scaler : function The scaler function to use. mem : int The step to use. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients.
Returns:	float TODO

See also

delta_MSB2, delta_invBFGS

proxtoolbox.algorithms.samsara.hessian.BFGS1_product(u_vec, S_mat, Y_mat, scale)[source]¶

An implementation of the BFGS algorithm.

Parameters:	u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling.
Returns:	array_like TODO

See also

delta_invBFGS: TODO

Broyden1_product, Broyden2_product

proxtoolbox.algorithms.samsara.hessian.invBFGS1_product(u_vec, S_mat, Y_mat, scale)[source]¶

Stable inverse-BFGS matrix product.

Parameters:	u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling.
Returns:	array_like TODO

proxtoolbox.algorithms.samsara.hessian.Broyden1_product(mem, u_vec, S_mat, Y_mat, scale)[source]¶

An implementation of Broyden’s method.

Parameters:	mem : int TODO u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling.
Returns:	array_like TODO

See also

Broyden2_product, BFGS1_product

proxtoolbox.algorithms.samsara.hessian.invBroyden1_product(u_vec, S_mat, Y_mat, scale, alpha)[source]¶

An implementation of the inverse Broyden’s method.

Parameters:	u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling. alpha : float A regularization parameter.
Returns:	array_like TODO

proxtoolbox.algorithms.samsara.hessian.Broyden2_product(mem, u_vec, S_mat, Y_mat, scale)[source]¶

An implementation of Broyden’s method.

Parameters:	mem : int How many old steps to consider. u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling.
Returns:	array_like TODO

See also

Broyden1_product, BFGS1_product

proxtoolbox.algorithms.samsara.hessian.invBroyden2_product(u_vec, S_mat, Y_mat, scale, alpha)[source]¶

An implementation of the inverse Broyden’s method.

Parameters:	u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradient differences. scale : float The initial scaling. alpha : float A regularization parameter.
Returns:	array_like TODO

proxtoolbox.algorithms.samsara.hessian.hessian_wrapper(Hessian_product, mem, u_vec, S_mat, Y_mat, scale, alpha)[source]¶

Wrapper for all hessian functions in this module.

Used to have unified parameters across all function calls.

Parameters:	Hessian_product : function The hessian function to use. mem : int The step to use. u_vec : array_like The vector to be multiplied. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients. scale : float The initial scaling. alpha : float A regularisation parameter.
Returns:	array_like TODO

proxtoolbox.algorithms.samsara.hessian.random(size=None)¶

Return random floats in the half-open interval [0.0, 1.0).

Results are from the “continuous uniform” distribution over the stated interval. To sample \(Unif[a, b), b > a\) multiply the output of random_sample by (b-a) and add a:

(b - a) * random_sample() + a

Parameters:	size : int or tuple of ints, optional Output shape. If the given shape is, e.g., `(m, n, k)`, then `m * n * k` samples are drawn. Default is None, in which case a single value is returned.
Returns:	out : float or ndarray of floats Array of random floats of shape size (unless `size=None`, in which case a single float is returned).

Examples

>>> np.random.random_sample()
0.47108547995356098
>>> type(np.random.random_sample())
<type 'float'>
>>> np.random.random_sample((5,))
array([ 0.30220482,  0.86820401,  0.1654503 ,  0.11659149,  0.54323428])

Three-by-two array of random numbers from [-5, 0):

>>> 5 * np.random.random_sample((3, 2)) - 5
array([[-3.99149989, -0.52338984],
       [-2.99091858, -0.79479508],
       [-1.23204345, -1.75224494]])

proxtoolbox.algorithms.samsara.hessian.seed(seed=None)¶

Seed the generator.

This method is called when RandomState is initialized. It can be called again to re-seed the generator. For details, see RandomState.

Parameters:	seed : int or 1-d array_like, optional Seed for RandomState. Must be convertible to 32 bit unsigned integers.

See also

RandomState

proxtoolbox.algorithms.samsara.history module¶

Contains all implementations of history functions.

proxtoolbox.algorithms.samsara.history.fdSY_mat(mem, x_mat, gradf_mat)[source]¶

Finite difference history ordering.

Finite difference history ordering for limited memory matrix secant methods.

Parameters:	mem : int TODO x_mat : array_like The matrix of iterates. gradf_mat : array_like The matrix of gradients.
Returns:	S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients.

See also

cdSY_mat: Alternative function.
history_wrapper: Wrapper to call this function.

proxtoolbox.algorithms.samsara.history.cdSY_mat(mem, x_mat, gradf_mat)[source]¶

Conjugate direction history ordering.

Conjugate direction history ordering for limited memory matrix secant methods.

Parameters:	mem : int TODO x_mat : array_like The matrix of iterates. gradf_mat : array_like The matrix of gradients.
Returns:	S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients.

See also

fdSY_mat: Alternative function.
history_wrapper: Wrapper to call this function.

proxtoolbox.algorithms.samsara.history.history_wrapper(History, mem, x_mat, gradf_mat)[source]¶

Wrapper for all history functions.

Provides a unified function call for all history functions.

Parameters:	mem : int TODO x_mat : array_like The matrix of iterates. gradf_mat : array_like The matrix of gradients.
Returns:	S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients.

See also

fdSY_mat, cdSY_mat

proxtoolbox.algorithms.samsara.memory module¶

Contains the memory update rountine for samsara.samsara.Samsara.

proxtoolbox.algorithms.samsara.memory.Memory_update(x_mat, f_vec, gradf_mat, ngradf_vec, stepsize_vec, mem, psd, it, accept_step)[source]¶

Memory update routine.

Parameters:	x_mat : array_like, modified TODO. Gets modified. f_vec : array_like, modified TODO. Gets modified. gradf_mat : array_like, modified TODO. Gets modified. ngradf_vec : array_like, modified TODO. Gets modified. stepsize_vec : array_like, modified TODO. Gets modified. mem : int TODO psd : int TODO it : int The current iteration. accept_step : int TODO
Returns:	x_mat : array_like TODO f_vec : array_like TODO gradf_mat : array_like TODO ngradf_vec : array_like TODO stepsize_vec : array_like TODO mem : int TODO

proxtoolbox.algorithms.samsara.samsara module¶

Contains the Samsara class and some helper functions.

proxtoolbox.algorithms.samsara.samsara.is_empty(x)[source]¶

Checks if a variable holds any information.

Determines if x is None or an empty array.

This function is used to check whether new function and gradient values have been given to Samsara. This function exists because of the isemtpy function in MATLAB, that is being used in the MATLAB implementation of Samsara.

Parameters:	x The variable to be checked.
Returns:	bool True if x is either None or an empty array. False otherwise.

proxtoolbox.algorithms.samsara.samsara.Normsqresid(Scaler, History, Hessian_product, HessianT_product, mem, spsd, x_mat, gradf_mat, gradfnew_vec, alpha_0)[source]¶

Computes the normsquared residual of the gradient or otherwise vector-values function.

Parameters:	Scaler : function TODO History : function TODO Hessian_product : function TODO HessianT_product : function TODO mem : int TODO spsd : int TODO x_mat : array_like TODO gradf_mat : array_like TODO gradfnew_vec : array_like TODO alpha_0 : float TODO
Returns:	f0 : float TODO gradf0_vec : array_like TODO

See also

delta_invBFGS, delta_MSB2, cdSY_mat, fdSY_mat, BFGS1_product, invBFGS1_product, Broyden1_product, invBroyden1_product, Broyden2_product, invBroyden2_product

class proxtoolbox.algorithms.samsara.samsara.Samsara(verbose=False, alpha_0=5e-09, gamma=0.5, c=0.01, beta=0.99, eta1=0.995, eta2=0.8, eta3=0.05, maxmem=9, tr=1000000000000000.0, ngrad_TOL=1e-06, step_TOL=1e-14, Maxit=1000, orthog_TOL=1e-06, QN_method=<function BFGS1_product>, Step_finder=None, History=<function cdSY_mat>, update_conditions='Trust Region', initial_step=1e-09)[source]¶

Bases: object

TODO

Sets default values.

Parameters:

verbose : bool, optional

Turn additional output on or off. Default: False

alpha_0 : float, optional

TODO Default: 5e-9

gamma : float, optional

TODO Default: .5

c : float, optional

TODO Default: .01

beta : float, optional

TODO Default: .99

eta1 : float, optional

TODO Default: .995

eta2 : float, optional

TODO Default: .8

eta3 : float, optional

TODO Default: .05

maxmem : int, optional

The maximum steps to look back. Default: 9

tr : float, optional

The initial radius of the trust region. Default: 1e+15

ngrad_TOL : float, optional

The gradient norm tolerance. This is used as a stopping criteria for SAMSARA. Must be positive. Default: 1e-6

step_TOL : float, optional

The step size tolerance. This is used as a stopping criteria for SAMSARA. Must be positive. Default: 1e-14

Maxit : int, optional

The maximum number of iterations. This is used as a stopping criteria for SAMSARA. Must be positive. Default: 500

QN_method : function, optional

Quasi-Newton method for estimation of the function’s Hessian. Broyden implementations use samsara.step_finder.Dogleg_QN() lin search methods while BFGS implementations use samsara.step_finder.Explicit_TR(). Methods available are:

samsara.hessian.BFGS1_product()

samsara.hessian.Broyden1_product()

samsara.hessian.Broyden2_product()

Default: samsara.hessian.BFGS1_product()

Step_finder : function, optional

The step finder. Available methods are:

samsara.step_finder.Dogleg_QN()

samsara.step_finder.Explicit_TR()

If None, the step finder will be set depending on the QN_method. Default: None

History : function, optional

Ordering method for S, Y matrices in limited memory application. Finite difference ordering, samsara.history.fdSY_mat(), is recommended for Broyden implementations. For BFGS implementations, use conjugate direction ordering, samsara.history.cdSY_mat(). Default: samsara.history.cdSY_mat()

update_conditions : str, optional

Select the method for adjustment of the trust region in optimazation. Default: ‘Trust Region’

initial_step : float, optional

The norm of the inital step taken in the Cauchy direction. This multiplied against the normailzed gradient to yield the initial direction vector in order to generate the first step taken by SAMSARA.

Assign a value of 0 to use the default value which is the minimum of 1e-1 or the norm(1d-1*gradient). Default: 1e-9

run(x0_vec, xnew_vec, f0, fnew, gradf0_vec, gradfnew_vec)[source]¶

Computes the next point. Main routine of the SAMSARA toolbox.

Parameters:	x0_vec : array_like TODO xnew_vec : array_like TODO f0 : float TODO fnew : float TODO gradf0_vec : array_like TODO gradfnew_vec : array_like TODO
Returns:	xnew_vec : array_like The new point. x0_vec : array_like The old point. f0 : float The old function value. gradf0_vec : array_like The old gradient vector. stepsize : float The length of the last step.

save(filename='state.npz', **kwargs)[source]¶

Saves some values of samsara.

Saves dim, mem, it, tr, x_mat, gradf_mat, f_vec, ngradf_vec, stepsize_vec into a file.

Parameters:	filename : ‘state.npz’, optional The file to write to. **kwargs : dict, optional Additional variables to be saved.

See also

plot: If the saved file is given as a parameter, plot will use it’s values instead of the local ones.

plot(fopt=0.0, state_file=None)[source]¶

Displays a standard plot for Samsara.

If state_file is given, then it’s values we be used for the plot. Otherwise the values of the current instance of Samsara will be used.

Parameters:	objective : function The function samsara was minimising. state_file : None, optional The name of a save file created by the save function.

See also

save: Used to create the state_file.

_Samsara__first_step()¶: Initialise variables.

_Samsara__next_step()¶: Compute next point.

_Samsara__prepare_step()¶: Get missing function values.

_Samsara__set_methods()¶: Sets the methods to use.

_Samsara__update_step()¶: Updates the the matrix of steps.

_Samsara__validate_options()¶

Validates the set parameters.

Raises:	ValueError If step_TOL is not positive.

proxtoolbox.algorithms.samsara.step_finder module¶

Contains all functions that are used to calculate the next step.

proxtoolbox.algorithms.samsara.step_finder.inv_tGammPhiTPhi_product2(mem, u_vec, S_mat, Y_mat, scaleinv, omega)[source]¶

TODO

Parameters:	mem : int TODO u_vec : array_like TODO S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients. scaleinv : float The initial scaling. omega : float TODO
Returns:	array_like TODO

See also

TRFBGS1

proxtoolbox.algorithms.samsara.step_finder.TRBFGS1(mem, u_vec, ngrad, S_mat, Y_mat, tr, scale)[source]¶

TODO

Parameters:	mem : int How many steps to look back. u_vec : array_like The negative gradient vector. ngrad : float The norm of the current gradient. S_mat : array_like The matrix of steps. Y_mat : array_like The matrix of gradients. tr : float The radius of the trust region. scale : float The initial scaling.
Returns:	d_vec : array_like The next step.

See also

Explicit_TR: Calling function.
inv_tGammPhiTPhi_product2: Used in this function.

proxtoolbox.algorithms.samsara.step_finder.Step_generator(Step_finder, Scaler, History, Hessian_product, invHessian_product, it, mem, c, beta, gamma, x_mat, gradf_mat, ngradf_vec, stepsize_vec, tr, trstep, alpha_0, verbose)[source]¶

Calculates the direction of the next step and it’s inital length.

Parameters:

Step_finder : function: TODO
Scaler : function: TODO
History : function: TODO
Hessian_product : function: TODO
invHessian_product : function: TODO
it : int: The current iteration.
mem : int: TODO
c : float: TODO
beta : float: TODO
gamma : float: TODO
x_mat : array_like: TODO
gradf_mat : array_like: TODO
ngradf_vec : array_like: TODO
stepsize_vec : array_like, modified: TODO. Gets modified.
tr : float: TODO
trstep : int: TODO
alpha_0 : float: TODO
verbose : bool: TODO

Returns:

d_vec : array_like: The next step.

proxtoolbox.algorithms.samsara.step_finder.Step_length_update(History, Hessian_product, update_conditions, mem, it, x_mat, f_vec, gradf_mat, d_vec, mu_vec, stepsize_vec, tr, delta, alpha, eta1, eta2, eta3, cDDf, DDfnew, bDDf, orthog_TOL, lower_step_bound, gamma)[source]¶

Trust region adjustment routine.

Parameters:

History : function: TODO
Hessian_product : function: TODO
update_conditions : str: TODO
mem : int: TODO
it : int: The current iteration.
x_mat : array_like: TODO
f_vec : array_like: TODO
gradf_mat : array_like: TODO
d_vec : array_like, modified: TODO. Gets modified.
mu_vec : array_like, modified: TODO. Gets modified.
stepsize_vec : array_like, modified: TODO. Gets modified.
tr : float: TODO
delta : float: TODO
alpha : float: TODO
eta1 : float: TODO
eta2 : float: TODO
eta3 : float: TODO
cDDf : float: TODO
DDfnew : float: TODO
bDDf : float: TODO
orthog_TOL : float: TODO
lower_step_bound : float: TODO
gamma : float: TODO

Returns:

tr : float: TODO
mu_vec : array_like: TODO
cDDf : float: TODO
lower_step_bound : float: TODO
d_vec : array_like: TODO
stepsize_vec : array_like: TODO
accept : int: TODO

proxtoolbox.algorithms.samsara.step_finder.Dogleg_QN(Hessian_product, invHessian_product, mem, grad_vec, ngrad, S_mat, Y_mat, tr, scale, alpha)[source]¶

Stable Quasi-Newton Dogleg.

Dogleg subroutine for line search methods.

Parameters:

Hessian_product : function: The dogleg method.
invHessian_product : function: The quasi newton method.
mem : int: How far to look back.
grad_vec : array_like: The current gradient.
ngrad : float: The norm of the current gradient.
S_mat : array_like: The matrix of steps.
Y_mat : array_like: The matix of gradients.
tr : float: The radius of the trust region.
scale : float: The initial scaling.
alpha : float: A regularisation parameter.

Returns:

d_vec : array_like: The next step. Equals the step calculated with the quasi newton method, if that step already is within the trust region.

See also

step_wrapper: Wrapper for this function.

Notes

Solves the following problem:

proxtoolbox.algorithms.samsara.step_finder.Explicit_TR(invHessian_product, mem, grad_vec, ngrad, S_mat, Y_mat, tr, scale, alpha, verbose)[source]¶

Stable Explicit Trust Region.

Stable Explicit Trust Region for Symmetric PSD matrix secant methods.

Parameters:

invHessian_product : function: The quasi newton method.
mem : int: How many steps to look back.
grad_vec : array_like: The current gradient.
ngrad : float: The norm of the current gradient.
S_mat : array_like: The matrix of steps.
Y_mat : array_like: The matrix of gradients.
tr : float: The radius of the trust region.
scale : float: The initial scaling.
alpha : float: A regularisation parameter.
verbose : bool: If additional output should be printed.

Returns:

d_vec : array_like: The next step.

See also

step_wrapper: Wrapper for this function.

TRBFGS1, Dogleg_QN

proxtoolbox.algorithms.samsara.step_finder.step_wrapper(step_finder, Hessian_product, invHessian_product, mem, grad_vec, ngrad, S_mat, Y_mat, tr, scale, alpha, verbose)[source]¶

A wrapper for all step finding functions.

The wrapper provides a unified function call for all step finders.

Parameters:

step_finder : function: The step finder to use (Dogleg_QN, Explicit_TR).
Hessian_product : function: The dogleg method for Dogleg_QN.
invHessian_product : function: The quasi newton method.
mem : int: How many steps to look back.
grad_vec : array_like: The current gradient.
ngrad : float: The norm of the current gradient.
S_mat : array_like: The matrix of steps.
Y_mat : array_like: The matrix of gradients.
tr : float: The radius of the trust region.
scale : float: The initial scaling.
alpha : float: A regularisation parameter.
verbose : bool: If additional output should be printed.

Returns:

d_vec - array_like: The next step as calculated by the step_finder.

See also

Dogleg_QN, Explicit_TR