Optim.jl

Optim.jl provides univariate and multivariate optimization in Julia. Its primary focus is on unconstrained optimization, where solvers attempt to find an x that minimizes a function f(x).

Key features include:

• Local Optimization: Most solvers are designed to converge to a local minimum under certain conditions.
• Global Optimization: For finding global minima, Optim provides methods such as (bounded) simulated annealing and particle swarm.
• Constraints: While primarily unconstrained, there is support for box-constrained and Riemannian optimization.
• Automatic Differentiation: Being written in Julia, Optim has native access to automatic differentiation features via the JuliaDiff ecosystem.
• Extensibility: The package leverages Julia's multiple dispatch to allow for features like custom preconditioners.

Optim.jl is a mathematical optimization package for Julia that provides a wide range of routines for solving optimization problems. It is designed to allow researchers and developers to solve problems without implementing algorithms from scratch.

Key Features:

• Supported Domains: Optimization on manifolds, functions of complex numbers, and arbitrary precision vectors/matrices.
• Derivative Handling: Users can provide their own derivatives or use automatic differentiation (AD) or finite difference methods.
• Constraint Support: Currently focuses on unconstrained optimization, but supports box-constrained optimization. Comprehensive constraint support is in development.
• Algorithm Types: Includes derivative-free, first-order, and second-order methods.

You can extend Optim.jl by implementing your own manifold type. To do so, you must provide implementations for the following two methods:

1. project_tangent!(M::YourManifold, g, x): Projects a vector g onto the tangent space of the manifold at point x.
2. retract!(M::YourManifold, x): Performs the retraction step to move an iterate back onto the manifold.

In Optim.jl, GradientDescent is implemented as a quasi-Newton solver where the matrix $P$ is an identity matrix. The update rule is:

$$x_{n+1} = x_n - \alpha P^{-1}\nabla f(x_n)$$

Key characteristics:

• Direction: It moves in the exact opposite direction of the gradient, meaning it does not use Hessian curvature information.
• Step Size: A scalar $\alpha$ is determined by a line search algorithm to ensure sufficient descent.
• Performance: While logical, this method can be very slow for ill-conditioned problems. To improve performance in such cases, use a preconditioner (see the preconditioners section in the documentation).

Preconditioning is supported by the GradientDescent, ConjugateGradient, and LBFGS methods. It acts as a change of coordinates to improve the conditioning of the Hessian, which can substantially improve convergence speed.

To use a custom preconditioner P, you must implement two specific methods:

1. ldiv!(pgr, P, gr): Applies the preconditioner P to a vector gr and stores the result in pgr. Conceptually, this performs pgr = P \ gr.
2. dot(x, P, y): Computes the inner product induced by P. Conceptually, this computes dot(x, P * y).

Note that P is typically a matrix that approximates the Hessian (not the inverse Hessian).

using ForwardDiff, Optim, SparseArrays

# Example of a preconditioner structure
# P must implement:
# ldiv!(pgr, P, gr)
# dot(x, P, y)

Simulated Annealing is a probabilistic, derivative-free optimization method. It uses a temperature $T$ to control the volatility of changes.

Given a current objective value $f_{current}$ and a proposed value $f_{proposal}$, the probability of accepting the proposal is calculated as:

exp(-(f_proposal - f_current)/T)

Key behaviors:

• If $f_{proposal} \le f_{current}$, the solution is guaranteed to be accepted.
• If $f_{proposal} > f_{current}$, the solution may still be accepted. Higher temperatures increase the likelihood of accepting worse solutions, allowing the algorithm to escape local minima.

Each algorithm in Optim.jl maintains an OptimizationState (a subtype of Optim.OptimizationState) that encapsulates all information about the current iteration of the optimization process. This state is used to track progress, maintain search directions, and is passed to callback functions.

Important Exceptions:

• SAMIN: Does not maintain an OptimizationState.
• Univariate Optimization Algorithms: Do not use the OptimizationState structure.

Callback Behavior for Exceptions: If you are using an algorithm that does not use OptimizationState (like SAMIN or univariate algorithms), your callback functions will receive a NamedTuple instead of an OptimizationState object. To avoid type errors, do not use type annotations for the state argument in your callback functions if you want them to be compatible with these algorithms.

To use first- and second-order optimization methods (like BFGS() or Newton()), you must provide gradients and Hessians. You can specify them in three ways:

1. Analytic: Provide manually computed g! (gradient) and h! (Hessian) functions. This is the fastest method but requires manual derivation.
2. Finite Differences: If you do not provide g! or h!, Optim.jl uses FiniteDiff.jl by default. This is easy to use but slow in high dimensions and less accurate.
3. Automatic Differentiation (AD): Uses DifferentiationInterface.jl to compute exact derivatives automatically. This is a middle ground between analytic and finite differences.

To use analytic derivatives, pass the g! and h! functions directly to the optimize call.

# Example of providing analytic derivatives
Optim.optimize(f, g!, h!, initial_x, BFGS())

N-GMRES and O-ACCEL are acceleration methods that take a step provided by a nonlinear preconditioner (nlprecon) and propose an accelerated step on a subspace spanned by the previous wmax iterates.

• N-GMRES: Accelerates based on a minimization of an approximation to the $\ell_2$ norm of the gradient. It was originally developed for nonlinear systems and reduces to GMRES for linear problems.
• O-ACCEL: Accelerates based on a minimization of an approximation to the objective function.

Recommendation: Before using N-GMRES or O-ACCEL, it is recommended to try LBFGS, as it is often more efficient for many problems despite having similar computational and memory requirements.