TrustRegionMethods.Dogleg
— TypeThe dogleg method.
A simple and efficient heuristic for solving local trust region problems. Does not necessarily find the optimum, but improves on the Cauchy point.
TrustRegionMethods.ForwardDiffBuffer
— Typestruct ForwardDiffBuffer{TX, TF, TR, TC}
A buffer for wrapping a (nonlinear) mapping f
to calculate the Jacobian with ForwardDiff.jacobian
.
TrustRegionMethods.GeneralizedEigenSolver
— TypeGeneralized eigenvalue solver (Adachi et al 2017).
TrustRegionMethods.MinimizationModel
— Typestruct MinimizationModel{TG, TA}
A quadratic model for a minimization problem, relative to the origin, with the objective function
\[m(p) = p' g + 1/2 g' A g\]
TrustRegionMethods.MinimizationModel
— MethodMinimizationModel(model)
Convert a model for a residual to a minimization model using the L2 norm.
TrustRegionMethods.ResidualModel
— Typestruct ResidualModel{TR, TJ}
A linear model for system of nonlinear equations, relative to the origin.
The L2 norm induces the objective function
\[m(p) = p' J' r + 1/2 p' J' J p\]
approximating some f(x) = \| r(x) \|^2_2
as
\[1/2 \| f(x + p) \|_2^2 pprox 1/2 \| r + J p \|_2^2 = \| r \|_2^2 + p'J'r + 1/2 p' J' J p\]
TrustRegionMethods.TrustRegionResult
— Typestruct TrustRegionResult{T<:Real, TX<:AbstractArray{T<:Real, 1}, TFX}
Fields
Δ
The final trust region radius.
x
The last value (the root only when converged).
fx
f(x)
at the lastx
.residual_norm
The Euclidean norm of the residual at
x
.converged
A boolean indicating convergence.
iterations
Number of iterations (≈ number of function evaluations).
TrustRegionMethods.ForwardDiff_wrapper
— MethodForwardDiff_wrapper(f, n, jacobian_config)
Wrap an $ℝⁿ$ function f
in a callable that can be used in trust_region_solver
directly. Remaining parameters are passed on to ForwardDiff.JacobianConfig
, and can be used to set eg chunk size.
Non-finite residuals will be treated as infeasible.
julia> f(x) = [1.0 2; 3 4] * x - ones(2)
f (generic function with 1 method)
julia> ff = ForwardDiff_wrapper(f, 2)
AD wrapper via ForwardDiff for ℝⁿ→ℝⁿ function, n = 2
julia> ff(ones(2))
(r = [2.0, 6.0], J = [1.0 2.0; 3.0 4.0])
julia> trust_region_solver(ff, [100.0, 100.0])
Nonlinear solver using trust region method converged after 9 steps
with ‖x‖₂ = 3.97e-15, Δ = 128.0
x = [-1.0, 1.0]
r = [-1.78e-15, 3.55e-15]
TrustRegionMethods._check_residual_Jacobian
— Method_check_residual_Jacobian(x, fx)
Checks residual and Jacobian and throws an appropriate error if they are not both finite.
Internal, each evaluation of f
should call this.
TrustRegionMethods._factorize
— Method_factorize(J)
Return (F, is_valid_F)
where
F
is a form (usually a factorization) of the argument that supportsF \ r
for vectorsr
,is_valid_F
is a boolean indicating whetherF
can be used in this form (egfalse
for a singular factorization).
TrustRegionMethods.cauchy_point
— Methodcauchy_point(Δ, model)
Find the Cauchy point (the minimum of the linear part, subject to $\| p \| ≤ Δ$) of the problem.
Return three values:
the Cauchy point vector
pC
,the (Euclidean) norm of
pC
a boolean indicating whether the constraint was binding.
Caller guarantees non-zero gradient.
TrustRegionMethods.dogleg_boundary
— Functiondogleg_boundary(Δ, D, pC)
dogleg_boundary(Δ, D, pC, pC_norm)
Finds au
such that
\[\| p_C + τ D \|_2 = Δ\]
pC_norm
is \| p_C \|_2^2
, and can be provided when available.
Caller guarantees that
pC_norm ≤ Δ
,norm(pC + D, 2) ≥ Δ
.dot(pC, D) ≥ 0
.
These ensure a meaningful solution 0 ≤ τ ≤ 1
. None of them are checked explicitly.
TrustRegionMethods.dogleg_implementation
— Methoddogleg_implementation(Δ, model, pU, pU_norm)
Implementats the branch of the dogleg method where it is already determined that the unconstrained optimum is lies outside the Δ
ball. Returns the same kind of results as solve_model
.
TrustRegionMethods.ellipsoidal_norm
— Methodellipsoidal_norm(x, _)
Ellipsoidal norm $\| x \|_B = x'Bx$.
TrustRegionMethods.ges_kernel
— Methodges_kernel(Δ, model, B)
Kernel for the generalized eigenvalue solver (methods specialize on the ellipsoidal norm matrix B
). Solves the M̃(λ)
pencil in Adachi et al (2017), eg Algorithm 5.1.
Returns
λ
, the largest eigenvalue,the gap to the next eigenvalue (see note below)
y1
andy2
, the two parts of the corresponding generalized eigenvalue,
All values are real, methods are type stable.
When theorerical assumptions are violated, gap
will be non-finite and a debug statement is emitted. No other values should be used in this case.
TrustRegionMethods.reduction_ratio
— Methodreduction_ratio(model, p, r′)
Ratio between predicted (using model
, at p
) and actual reduction (taken from the residual value r′
). Will return an arbitrary negative number for infeasible coordinates.
TrustRegionMethods.solve_model
— Functionsolve_model(method, Δ, model)
Optimize the model
with the given constraint Δ
using method
. Returns the following values:
- the optimum,
- the norm of the optimum,
- a boolean indicating whether the constraint binds.
TrustRegionMethods.trust_region_solver
— Methodtrust_region_solver(f, x; parameters, local_method, stopping_criterion, maximum_iterations, Δ)
Solve f ≈ 0
using trust region methods, starting from x
.
f
is a callable (function) that
takes vectors real numbers of the same length as
x
,returns a value with properties
residual
andJacobian
, containing a vector and a conformable matrix, with finite values for both or a non-finite residual (for infeasible points; Jacobian is ignored). ANamedTuple
can be used for this, but any structure with these properties will be accepted. Importantly, this is treated as a single object and can be used to return extra information (a “payload”), which will be ignored by this function.
Returns a TrustRegionResult
object.
TrustRegionMethods.trust_region_step
— Methodtrust_region_step(parameters, local_method, f, Δ, x, fx)
Take a trust region step using local_method
.
f
is the function that returns the residual and the Jacobian (see trust_region_solver
).
Δ
is the trust region radius, x
is the position, fx = f(x)
. Caller ensures that the latter is feasible.
TrustRegionMethods.unconstrained_optimum
— Methodunconstrained_optimum(model)
Calculate the unconstrained optimum of the model, return its norm as the second value.
When the second value is infinite, the unconstrained optimum should not be used as this indicates a singular problem.