API

FidesProblem(f, grad!, x0; hess! = nothing, lb = nothing, ub = nothing)

Optimization problem to be minimized with the Fides Newton Trust Region optimizer.

Arguments

• f: The objective function to minimize. Accepts a Vector or ComponentVector as input and return a scalar.
• grad!: In-place function to compute the gradient of f on the form grad!(g, x).
• x0: Initial starting point for the optimization. Can be a Vector or ComponentVector from ComponentArrays.jl.
• hess!: (Optional) In-place function to compute the Hessian of f on the form hess!(H, x). If not provided, a Hessian approximation method must be selected when calling solve.
• lb: Lower parameter bounds. Defaults to -Inf if not specified.
• ub: Upper parameter bounds. Defaults to Inf if not specified.

See also solve and FidesOptions.

FidesProblem(fides_obj, x0; lb = nothing, ub = nothing)

Optimization problem created from a function that computes:

• Objective and gradient; fides_obj(x) -> (obj, g).
• Objective, gradient and Hessian; fides_obj(x) -> (obj, g, H).

Internally, Fides computes the objective function and derivatives simultaneously. Therefore, this constructor is the most runtime-efficient option when intermediate quantities can be reused between the objective and derivative computations.

Description of Fides method

Fides implements an Interior Trust Region Reflective method for boundary-constrained optimization, as described in [1, 2]. Optimization problems on the following form are targeted:

\[\min_x f(x) \quad \text{s.t.} \quad lb \leq x \leq ub\]

At each iteration, the Fides approximates the objective function by a second-order model:

\[\min_x m_k(x) = f(x_k) + \nabla f(x_k)^T (x - x_k) + 0.5 (x - x_k)^T B_k (x - x_k) \quad \text{s.t.} \quad |x - x_k| \leq \Delta_k\]

Where, Δₖ is the trust region radius reflecting the confidence in the second-order approximation, ∇f(xₖ) is the gradient of f at the current iteration xₖ, and Bₖ is a symmetric positive-semidefinite matrix, that is either the exact Hessian (if hess! is provided) or an approximation.

References

1. Coleman, T. F., & Li, Y. (1994). On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds. Mathematical programming, 67(1), 189-224.
2. Coleman, T. F., & Li, Y. (1996). An interior trust region approach for nonlinear minimization subject to bounds. SIAM Journal on optimization, 6(2), 418-445.

solve(prob::FidesProblem, hess_update; options = FidesOptions())

Solve the given FidesProblem using the Fides Trust Region method, with the specified hess_update method for computing the Hessian matrix.

In case a custom Hessian is provided to prob, use hess_update = Fides.CustomHessian. Otherwise, a Hessian approximation must be provided, and a complete list of available approximations can be found in the API documentation.

See also FidesOptions.

FidesOptions(; kwargs...)

Options for the Fides Optimizer.

Keyword arguments

• maxiter = 1000: Maximum number of allowed iterations
• fatol = 1e-8: Absolute tolerance for convergence based on objective (f) value
• frtol = 1e-8: Relative tolerance for convergence based on objective (f) value
• gatol = 1e-6: Absolute tolerance for convergence based on the gradient
• grtol = 0.0: Relative tolerance for convergence based on the gradient
• xtol = 0.0: Tolerance for convergence based on x (parameter vector)
• maxtime = Inf: Maximum amount of wall-time in seconds
• verbose: The logging (verbosity) level of the optimizer. Allowed values are:
  • warning (default): Only warnings are printed.
  • info: Information is printed for each iterations.
  • error: Only errors are printed.
  • debug: Detailed information is printed, typically only of interest for developers.
• stepback_strategy: Refinement method if proposed step reaches optimization boundary. Allowed options are:
  • reflect (default): Recursive reflections at boundary
  • refine: Perform optimization to refine step
  • reflect_single: Single reflection at boundary
  • mixed: Mix reflections and truncations
  • trunace: Truncate step at boundary and re-solve
• subspace_solver: Subspace dimension in which the Trust region subproblem is solved. Allowed options are:
  • 2D (default): Two dimensional Newton/Gradient subspace
  • scg: CG subspace via Steihaug’s method
  • full: Full on R^n
• delta_init = 1.0: Initial trust region radius
• mu = 0.25: Acceptance threshold for trust region ratio
• eta = 0.75: Trust region increase threshold for trust region ratio
• theta_max = 0.95: Maximal fraction of step that would hit bounds
• gamma1 = 0.25: Factor by which trust region radius will be decreased
• gamma2 = 2.0: Factor by which trust region radius will be increased
• history_file = nothing: Records statistics when set

FidesSolution

Solution information from a Fides optmization run.

Fields

• xmin: Minimizing parameter vector found by the optimization rung
• fmin: Minimum objective value found by the optimization run
• niterations: Number of iterations for the optimization run
• runtime: Runtime in seconds for the optimization run
• retcode: Return code from the optimization run. Possible values are:
  • DELTA_TOO_SMALL: Trust Region Radius too small to proceed
  • DID_NOT_RUN: Optimizer did not run
  • EXCEEDED_BOUNDARY: Exceeded specified boundaries
  • FTOL: Converged according to fval difference
  • GTOL: Converged according to gradient norm
  • XTOL: Converged according to x difference
  • MAXITER: Reached maximum number of allowed iterations
  • MAXTIME: Reached maximum runtime
  • NOT_FINITE: Encountered non-finite fval/grad/hess

CustomHessian()

User‑provided Hessian function.

The Hessian function should be provided when creating a FidesProblem.

See also: FidesProblem

BFGS(; init_hess = nothing, enforce_curv_cond::Bool = true)

The Broyden-Fletcher-Goldfarb-Shanno (BFGS) update strategy is a rank-2 update method that preserves both symmetry and positive-semidefiniteness [1].

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.
• enforce_curv_cond = true: Whether the update should attempt to preserve positive definiteness. If true, updates from steps that violate the curvature condition are discarded.

References

1. Nocedal, Jorge, and Stephen J. Wright, eds. Numerical optimization. New York, NY: Springer New York, 1999.

SR1(; init_hess = nothing)

The Symmetric Rank 1 update strategy as described in [1]. This is a rank 1 update strategy that preserves symmetry but does not preserve positive-semidefiniteness.

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.

References

1. Nocedal, Jorge, and Stephen J. Wright, eds. Numerical optimization (Chapter 6.2). New York, NY: Springer New York, 1999.

DFP(; init_hess = nothing, enforce_curv_cond::Bool = true)

The Davidon-Fletcher-Powell update strategy [1]. This is a rank 2 update strategy that preserves symmetry and positive-semidefiniteness.

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.
• enforce_curv_cond = true: Whether the update should attempt to preserve positive definiteness. If true, updates from steps that violate the curvature condition are discarded.

References

1. Avriel, M. (2003). Nonlinear programming: analysis and methods. Courier Corporation.

Broyden(phi; init_hess = nothing, enforce_curv_cond::Bool = true)

The update scheme, as described in [1], which is a generalization of the BFGS/DFP methods where phi controls the convex combination between the two. This rank-2 update strategy preserves both symmetry and positive-semidefiniteness when 0 ≤ phi ≤ 1.

Arguments

• phi::AbstractFloat: The convex combination parameter interpolating between BFGS (phi=0) and DFP (phi=1).

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.
• enforce_curv_cond = true: Whether the update should attempt to preserve positive definiteness. If true, updates from steps that violate the curvature condition are discarded.

References

1. Nocedal, Jorge, and Stephen J. Wright, eds. Numerical optimization. New York, NY: Springer New York, 1999.

BG(; init_hess = nothing}

Broydens “good” method as introduced in [1]. This is a rank 1 update strategy that does not preserve symmetry or positive definiteness.

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.

References

1. Broyden, C. G. (1965). A class of methods for solving nonlinear simultaneous equations. Mathematics of computation, 19(92), 577-593.

BB(; init_hess = nothing}

The Broydens “bad” method as introduced in [1]. This is a rank 1 update strategy that does not preserve symmetry or positive definiteness.

Keyword arguments

• init_hess = nothing: Initial Hessian for the update scheme. If provided as a Matrix, the given matrix is used; if set to nothing (default), the identity matrix is used.

References

1. Broyden, C. G. (1965). A class of methods for solving nonlinear simultaneous equations. Mathematics of computation, 19(92), 577-593.