subroutines

Numerical subroutines shared by the optimizers: line searches, BFGS, Newton-CG, trust-region subproblems and step rules.

AdaMax

Bases: Adam

AdaMax optimizer kingma2014

apply_update(control, gradient, **kwargs)

An AdaMax step (Adam with the infinity norm on the second moment); returns (new_control, step).

Adam

A class implementing the Adam optimizer for gradient-based optimization kingma2014.

The Adam update equation for the control x using gradient g, iteration t, and small constants ε is given by:

m_t = β1 * m_{t-1} + (1 - β1) * g

v_t = β2 * v_{t-1} + (1 - β2) * g^2

m_t_hat = m_t / (1 - β1^t)

v_t_hat = v_t / (1 - β2^t)

x_{t+1} = x_t - α * m_t_hat / (sqrt(v_t_hat) + ε)

Attributes:

Name	Type	Description
step_size	float	The initial step size provided during initialization.
beta1	float	The exponential decay rate for the first moment estimates.
beta2	float	The exponential decay rate for the second moment estimates.
vel1	1-D array_like	First moment estimate.
vel2	1-D array_like	Second moment estimate.
eps	float	Small constant to prevent division by zero.
_step_size	float	Private attribute for temporarily modifying step size.
temp_vel1	1-D array_like	Temporary first moment estimate.
temp_vel2	1-D array_like	Temporary Second moment estimate.

Methods:

Name	Description
apply_update	Apply an Adam update to the control parameter.
apply_backtracking	Apply backtracking by reducing step size temporarily.
restore_parameters	Restore the original step size.

__init__(step_size, beta1=0.9, beta2=0.999)

A class implementing the Adam optimizer for gradient-based optimization. The Adam update equation for the control x using gradient g, iteration t, and small constants ε is given by:

m_t = β1 * m_{t-1} + (1 - β1) * g

v_t = β2 * v_{t-1} + (1 - β2) * g^2

m_t_hat = m_t / (1 - β1^t)

v_t_hat = v_t / (1 - β2^t)

x_{t+1} = x_t - α * m_t_hat / (sqrt(v_t_hat) + ε)

Parameters:

Name	Type	Description	Default
step_size	float	The step size (learning rate) for the optimization.	required
beta1	float	The exponential decay rate for the first moment estimates (default is 0.9).	0.9
beta2	float	The exponential decay rate for the second moment estimates (default is 0.999).	0.999

apply_backtracking(shrink=0.5)

Apply backtracking by scaling the step size temporarily.

apply_update(control, gradient, **kwargs)

Apply a gradient update to the control parameter.

Note

This is the steepest descent update: x_new = x_old - x_step.

Parameters:

Name	Type	Description	Default
control	array_like	The current value of the parameter being optimized.	required
gradient	array_like	The gradient of the objective function with respect to the control parameter.	required
**kwargs	dict	Additional keyword arguments, including 'iter' for the current iteration.	{}

Returns:

Type	Description
new_control, temp_velocity: tuple	The new value of the control parameter after the update, and the current state step.

get_step_size()

Current step size.

restore_parameters()

Restore the original step size.

CMA

__call__(cov, step, X, J)

Performs the CMA update.

Parameters:

Name	Type	Description	Default
cov	array_like, of shape (d, d)	Current covariance or correlation matrix.	required
step	array_like, of shape (d,)	New step of control vector. Used to update the evolution path.	required
X	array_like, of shape (n, d)	Control ensemble of size n.	required
J	array_like, of shape (n,)	Objective ensemble of size n.	required

Returns:

Name	Type	Description
out	array_like, of shape (d, d)	CMA updated covariance (correlation) matrix.

__init__(ne, dim, alpha_mu=None, n_mu=None, alpha_1=None, alpha_c=None, corr_update=False, equal_weights=True)

This is a rather simple simple CMA class hansen2006.

Parameters:

Name	Type	Description	Default
ne	int	Ensemble size	required
dim	int	Dimensions of control vector	required
alpha_mu	float	Learning rate for rank-mu update. If None, value proposed in [1] is used.	None
n_mu	int, `n_mu < ne`	Number of best samples of ne, to be used for rank-mu update. Default is int(ne/2).	None
alpha_1	float	Learning rate fro rank-one update. If None, value proposed in [1] is used.	None
alpha_c	float	Parameter (inverse if backwards time horizen)for evolution path update in the rank-one update. See [1] for more info. If None, value proposed in [1] is used.	None
corr_update	bool	If True, CMA is used to update a correlation matrix. Default is False.	False
equal_weights	bool	If True, all n_mu members are assign equal weighting, w_i = 1/n_mu. If False, the weighting scheme proposed in [1], where w_i = log(n_mu + 1)-log(i), and normalized such that they sum to one. Defualt is True.	True

GradientDescent

A class for performing gradient descent optimization with momentum and backtracking. The gradient descent update equation with momentum is given by:

\[ \begin{align} v_t &= \beta * v_{t-1} + \alpha * gradient \\ x_t &= x_{t-1} - v_t \end{align} \]

Attributes:

Name	Type	Description
step_size	float	The initial step size provided during initialization.
momentum	float	The initial momentum factor provided during initialization.
velocity	array_like	Current velocity of the optimization process.
temp_velocity	array_like	Temporary velocity
_step_size	float	Private attribute for temporarily modifying step size.
_momentum	float	Private attribute for temporarily modifying momentum.

Methods:

Name	Description
apply_update	Apply a gradient update to the control parameter.
apply_backtracking	Apply backtracking by reducing step size and momentum temporarily.
restore_parameters	Restore the original step size and momentum values.

__init__(step_size, momentum)

Parameters:

Name	Type	Description	Default
step_size	float	The step size (learning rate) for the gradient descent.	required
momentum	float	The momentum factor to apply during updates.	required

apply_backtracking(shrink=0.5)

Apply backtracking by reducing step size and momentum temporarily.

apply_smc_update(control, gradient, **kwargs)

Apply a gradient update to the control parameter.

Parameters:

Name	Type	Description	Default
control	array_like	The current value of the parameter being optimized.	required
gradient	array_like	The gradient of the objective function with respect to the control parameter.	required
**kwargs	dict	Additional keyword arguments.	{}

Returns:

Name	Type	Description
new_control	ndarray	The new value of the control parameter after the update.

apply_update(control, gradient, **kwargs)

Apply a gradient update to the control parameter.

Note

This is the steepest descent update: x_new = x_old - x_step.

Parameters:

Name	Type	Description	Default
control	array_like	The current value of the parameter being optimized.	required
gradient	array_like	The gradient of the objective function with respect to the control parameter.	required
**kwargs	dict	Additional keyword arguments.	{}

Returns:

Type	Description
new_control, temp_velocity: tuple	The new value of the control parameter after the update, and the current state step.

get_momentum_for_nesterov()

The momentum term, beta * velocity, used for the Nesterov look-ahead.

get_step_size()

Current step size.

restore_parameters()

Restore the original step size and momentum value.

Steihaug

A class implementing the Steihaug conjugate-gradient trust region optimizer. This code is based on the minfx optimisation library, https://gna.org/projects/minfx

__init__(maxiter=1000000.0, epsilon=1e-08, delta_max=100000.0, delta0=1.0)

Page 75 from 'Numerical Optimization' by Jorge Nocedal and Stephen J. Wright, 1999, 2^nd ed. The CG-Steihaug algorithm is:

• epsilon > 0
• p0 = 0, r0 = g, d0 = -r0
• if ||r0|| < epsilon:
  • return p = p0
• while 1:
  • if djT.B.dj <= 0:
    • Find tau such that p = pj + tau.dj minimises m(p) in (4.9) and satisfies ||p|| = delta
    • return p
  • aj = rjT.rj / djT.B.dj
  • pj+1 = pj + aj.dj
  • if ||pj+1|| >= delta:
    • Find tau such that p = pj + tau.dj satisfies ||p|| = delta
    • return p
  • rj+1 = rj + aj.B.dj
  • if ||rj+1|| < epsilon.||r0||:
    • return p = pj+1
  • bj+1 = rj+1T.rj+1 / rjT.rj
  • dj+1 = rj+1 + bj+1.dj

Parameters:

Name	Type	Description	Default
maxiter	float	Maximum number of iterations.	1000000.0
epsilon	float	Tolerance for iterations.	1e-08
delta_max	float	Maximum thrust region size.	100000.0
delta0	float	Initial thrust region size.	1.0

apply_backtracking(shrink=0.5)

Apply backtracking by scaling the trust radius temporarily.

apply_update(xk, dfk, **kwargs)

Apply a Steihaug update to the control vector.

Parameters:

Name	Type	Description	Default
xk	array_like	The current value of the parameter being optimized.	required
dfk	array_like	The gradient of the objective function with respect to the control parameter.	required
**kwargs	dict	Additional keyword arguments, including the hessian of the objective function with respect to the control parameter.	{}

Returns:

Type	Description
new_control, step: tuple	The new value of the control parameter after the update, and the current state step.

get_step_size()

Current trust-region radius, which plays the role of the step size.

get_tau(pj, dj)

Function to find tau such that p = pj + tau.dj, and ||p|| = delta.

restore_parameters()

Restore the original step size.

bfgs_update(Hk, sk, yk)

Perform the BFGS update of the inverse Hessian approximation.

Parameters: - Hk: np.ndarray, current inverse Hessian approximation (n x n) - sk: np.ndarray, step vector (x_{k+1} - x_k), shape (n,) - yk: np.ndarray, gradient difference (grad_{k+1} - grad_k), shape (n,)

Returns: - Hk_new: np.ndarray, updated inverse Hessian approximation

line_search(step_size, xk, pk, fun, jac, fk=None, jk=None, **kwargs)

Line search algorithm to find step size alpha that satisfies the Wolfe conditions.

Parameters:

Name	Type	Description	Default
step_size	float	Initial step size to start the line search.	required
xk	ndarray	Current point in the optimization process.	required
pk	ndarray	Search direction.	required
fun	callable	Objective function	required
jac	callable	Gradient of the objective function	required
fk	float	Function value at xk. If None, it will be computed.	None
jk	ndarray	Gradient at xk. If None, it will be computed.	None
**kwargs	dict	Additional parameters for the line search, such as: - amax : float, maximum step size (default: 1000) - maxiter : int, maximum number of iterations (default: 10) - c1 : float, sufficient decrease condition (default: 1e-4) - c2 : float, curvature condition (default: 0.9)	{}

Returns:

Name	Type	Description
alpha	float	Step size that satisfies the Wolfe conditions.
fval	float	Function value at the new point xk + step_size*pk.
jval	ndarray	Gradient at the new point xk + step_size*pk.
nfev	int	Number of function evaluations.
njev	int	Number of gradient evaluations.

line_search_backtracking(step_size, xk, pk, fun, jac, fk=None, jk=None, **kwargs)

Backtracking line search algorithm to find step size alpha that satisfies the Wolfe conditions.

Parameters:

Name	Type	Description	Default
step_size	float	Initial step size to start the line search.	required
xk	ndarray	Current point in the optimization process.	required
pk	ndarray	Search direction.	required
fun	callable	Objective function	required
jac	callable	Gradient of the objective function	required
fk	float	Function value at xk. If None, it will be computed.	None
jk	ndarray	Gradient at xk. If None, it will be computed.	None
**kwargs	dict	Additional parameters for the line search, such as: - rho : float, backtracking factor (default: 0.5) - maxiter : int, maximum number of iterations (default: 10) - c1 : float, sufficient decrease condition (default: 1e-4) - c2 : float, curvature condition (default: 0.9)	{}

Returns:

Name	Type	Description
alpha	float	Step size that satisfies the Wolfe conditions.
fval	float	Function value at the new point xk + step_size*pk.
jval	ndarray	Gradient at the new point xk + step_size*pk.
nfev	int	Number of function evaluations.
njev	int	Number of gradient evaluations.

newton_cg(gk, Hk=None, maxiter=None, **kwargs)

Newton-CG search direction for gradient gk and Hessian Hk (Hessian-vector products by finite differences of jac when Hk is None); -gk when no descent direction is found.

solve_trust_region_subproblem(xk, fk, gk, Hk, radius, method='iterative', **kwargs)

Solve the trust-region subproblem.

Parameters:

Name	Type	Description	Default
xk	ndarray	Current point in the optimization process.	required
fk	float	Function value at xk.	required
gk	ndarray	Gradient at xk.	required
Hk	ndarray	Hessian at xk.	required
radius	float	Trust-region radius.	required
method	str	Method to solve the trust-region subproblem. Options are 'iterative' or 'CG-Steihaug'. Default is 'iterative'. If a callable is provided, it will be used as the solver with the signature: method(xk, fk, gk, Hk, radius, **kwargs)	'iterative'
**kwargs	dict	Additional parameters for the solver.	{}

Returns:

Name	Type	Description
pk	ndarray	Solution to the trust-region subproblem.
hits_boundary	bool	Indicates whether the solution lies on the boundary of the trust region.

zoom(alo, ahi, f, df, f0, df0, maxiter, c1, c2, iter_id=0)

Zoom function for line search algorithm. (This is the same as for scipy)