Numerical Optimization

orbithunter.optimize.hunt(orbit_instance, *methods, **kwargs)

Main optimization function for orbithunter; wraps many different SciPy and custom routines

Parameters

orbit_instanceOrbit

The orbit instance serving as the initial condition for optimization.

methodsstr or multiple str or tuple of str

Represents the numerical methods to hunt with, in order of indexing. Not all methods will work for all classes, performance testing is part of the development process. Options include: ‘newton_descent’, ‘lstsq’, ‘solve’, ‘adj’, ‘gd’, ‘lsqr’, ‘lsmr’, ‘bicg’, ‘bicgstab’, ‘gmres’, ‘lgmres’, ‘cg’, ‘cgs’, ‘qmr’, ‘minres’, ‘gcrotmk’,’nelder-mead’, ‘powell’, ‘cg_min’, ‘bfgs’, ‘newton-cg’, ‘l-bfgs-b’, ‘tnc’, ‘cobyla’, ‘slsqp’, ‘trust-constr’, ‘dogleg’, ‘trust-ncg’, ‘trust-exact’, ‘trust-krylov’, ‘hybr’, ‘lm’,’broyden1’, ‘broyden2’, ‘linearmixing’, ‘diagbroyden’, ‘excitingmixing’, ‘df-sane’, ‘krylov’, ‘anderson’

kwargsdict, optional

May contain any and all extra keyword arguments required for numerical methods and Orbit specific methods.

factory : callable

Callable with signature: factory(orbit_instance, method, kwargs) that yields relevant callables or options for root, minimize, or sparse.linalg methods. See Notes for details.

maxiter : int, optional

The maximum number of steps; computation time can be highly dependent on this number i.e. maxiter=100 for adjoint descent and lstsq have very very different computational times.

tol : float, optional

The threshold for the cost function for an orbit approximation to be declared successful.

ftol : float, optional

The threshold for the decrease of the cost function for any given step.

min_step : float, optional

Smallest backtracking step size before failure; not used in minimize.optimize algorithms.

scipy_kwargs : dict, optional

Additional arguments for SciPy solvers. There are too many to describe and they depend on the particular algorithm utilized, see references for links for more info. This set of kwargs is copied and then passed to numerical methods. They can include options that need to be passed to methods such as Orbit.eqn() during runtime.

Returns

OrbitResult :

Object which includes optimization properties like exit code, costs, tol, maxiter, etc. and the final resulting orbit approximation.

Notes

Description, links, and other comments on numerical methods. Before beginning testing/exploration I highly recommend checking the options of each solver. Typically the linear algebra solvers try to solve \(Ax=b\) within a strict error tolerance; however, because of nonlinearity we want to iteratively update this and solve it sequentially. Therefore, I recommend reducing the tolerance (sometimes dramatically) and use the orbithunter “outer iterations” (i.e. number of steps in the sequence x_n used to define and solve A_n x_n = b_n), to control the absolute error. Additionally, I have tried to provide a crude heuristic via the “progressive” keyword argument. This will crank up the strictness per every outer iteration loop, as it is presumed that more outer iterations means higher accuracy. Personally I just recommend to increase maxiter and keep the tolerances low.

The other issue is that scipy has different keyword arguments for the “same thing” everywhere. For example, the keyword arguments to control the tolerance across the set of methods that this provides access to are gtol, ftol, fatol, xtol, tol, atol, btol, … They do typically represent different quantities, but that doesn’t make it any less confusing.

scipy.optimize.minimize

To access options of the scipy solvers, must be passed as nested dict: hunt(x, scipy_kwargs={“options”:{}})

1. Do not take jacobian information: “nelder-mead”, “powell”, “cobyla”

2. Take Jacobian (product/matrix) “cg_min”, “bfgs”, “newton-cg”, “l-bfgs-b”, “tnc”, “slsqp”

3. Methods that either require the Hessian matrix (dogleg) or some method of computing it or its product. “trust-constr”, “dogleg”, “trust-ncg”, “trust-exact”, “trust-krylov”

Support for Hessian based methods [‘trust-constr’, ‘dogleg’, ‘trust-ncg’, ‘trust-exact’, ‘trust-krylov’]. For the ‘dogleg’ method, an argument hess is required to be passed to hunt in scipy_kwargs

hess{callable, ‘2-point’, ‘3-point’, ‘cs’, HessianUpdateStrategy}

For the other mehods, hessp is sufficient, but usage of hess is viable.

hessp{callable, optional}

Alternatively, SciPy accepts the finite difference methods str ‘2-point’, ‘3-point’, ‘cs’ or HessianUpdateStrategy objects. The Hessian based methods have never been tested as they were never used with the KSe.

Factory function returns a (callable, dict) pair. The callable is cost function C(orbit_instance, kwargs). The dict contains keywords “jac” and one of the following “hess”, “hessp” with the relevant callables/str see SciPy scipy.optimize.minimize for more details

Approximating the Hessian with finite difference strategy ‘cs’ requires the ability to handle complex input; while 100% not meant to handle complex input, the state variables of the OrbitKS class and subclasses can be overloaded to be complex to allow this to work; the parameters however must be cast as reals.

scipy.optimize.root

To access options of the scipy solvers, must be passed as nested dict: hunt(x, scipy_kwargs={“options”:{}}) To access the “jac_options” options, it is even more annoying: hunt(x, scipy_kwargs={“options”:{“jac_options”:{}}})

1. Methods that take jacobian as argument: ‘hybr’, ‘lm’

2. Methods which approximate the jacobian; take keyword argument “jac_options” [‘broyden1’, ‘broyden2’, ‘anderson’, ‘krylov’, ‘df-sane’]

3. Methods whose performance, SciPy warns, is highly dependent on the problem. [‘linearmixing’, ‘diagbroyden’, ‘excitingmixing’]

Factory function should return root function F(x) (Orbit.eqn()) and if ‘hybr’ or ‘lm’ then also jac as dict.

scipy.sparse.linalg

1. Methods that solve \(Ax=b\) in least squares fashion : ‘lsmr’, ‘lsqr’. Do not use preconditioning.

2. Solves \(Ax=b\) if A square (n, n) else solve normal equations \(A^T A x = A^T b\) in iterative/inexact fashion: ‘minres’, ‘bicg’, ‘bicgstab’, ‘gmres’, ‘lgmres’, ‘cg’, ‘cgs’, ‘qmr’, ‘gcrotmk’. Use preconditioning.

Factory function should return (A, b) where A is Linear operator or matrix and b is vector.

Other factoids worth mentioning, the design choice has been made for function/callable factories that they should build in constants into their definitions of the callables using nonlocals within the scope of the factory instead of passing constants as args. The reason for this is because the latter is not allowed for LinearOperator (sparse linalg) methods.

References

User should be aware of the existence of scipy.optimize.show_options() Options for each optimize method scipy.optimize scipy.optimize.minimize scipy.optimize.root scipy.sparse.linalg