torch_numopt.trust_region module

Trust-region methods for optimization.

Trust-region algorithms compute a step by solving a subproblem within a region where the quadratic model is trusted. This module provides Cauchy point, dogleg, exact (with Lagrange multiplier), and Steihaug-Toint (CG) solvers.

create_trust_region_solver(method, curvature_estimator, solver='solve', **kwargs)

Factory function for trust-region solvers.

Parameters:

methodstr

One of "cauchy", "dogleg", "exact", "steihaug-toint".

curvature_estimatorCurvatureEstimator

Curvature estimator used to build the quadratic model.

solverstr, default=”solve”

Linear solver for exact/Steihaug-Toint methods.

**kwargs

Additional arguments passed to the solver constructor.

Returns:

TrustRegionSolver

Instance of the requested solver.

class TrustRegionSolver(curvature_estimator, solver='solve')

Bases: ABC

Abstract base class for trust-region subproblem solvers.

Subclasses must implement the optimize_model method to compute a step that approximately minimizes the quadratic model within a given radius.

Parameters:

curvature_estimatorCurvatureEstimator

Estimator used for the quadratic model.

solverstr, default=”solve”

Linear solver for steps that require solving a linear system.

Methods

model(objective, step_dir, params, loss, ...)	Evaluate the quadratic model at a given step.
optimize_model(objective, params, radius, ...)	Solve the trust-region subproblem.

model(objective, step_dir, params, loss, grad_params)

Evaluate the quadratic model at a given step.

The model is m(p) = f + gᵀp + ½ pᵀ H p.

Parameters:

objectiveObjectiveFunction

Objective function.

step_dirParams

Candidate step p.

paramsParams

Current parameters.

lossfloat

Current loss value f.

grad_paramsParams

Current gradient g.

Returns:

torch.Tensor

Model value m(p).

abstract optimize_model(objective, params, radius, grad_params)

Solve the trust-region subproblem.

Parameters:

objectiveObjectiveFunction

Objective function.

paramsParams

Current parameters.

radiusfloat

Trust-region radius.

grad_paramsParams

Current gradient.

Returns:

Params

Step direction (p) that lies within the trust region.

class ExactTRSolver(curvature_estimator, iters=20, tol=1e-12)

Bases: TrustRegionSolver

Exact trust-region solver using the Lagrange multiplier method.

Solves the problem minimize m(p) subject to ||p|| ≤ Δ by finding the root of the secular equation. This is computationally expensive as it requires factorizing the matrix (H + λI).

Parameters:

curvature_estimatorCurvatureEstimator

Curvature estimator.

itersint, default=20

Maximum number of iterations for the root-finding.

tolfloat, default=1e-12

Tolerance for the norm constraint.

Methods

model(objective, step_dir, params, loss, ...)	Evaluate the quadratic model at a given step.
optimize_model(objective, params, radius, ...)	Solve the trust-region subproblem.

optimize_model(objective, params, radius, grad_params)

Solve the trust-region subproblem.

Parameters:

objectiveObjectiveFunction

Objective function.

paramsParams

Current parameters.

radiusfloat

Trust-region radius.

grad_paramsParams

Current gradient.

Returns:

Params

Step direction (p) that lies within the trust region.

class CauchyPointTRSolver(curvature_estimator, solver='solve')

Bases: TrustRegionSolver

Cauchy point trust-region solver.

The Cauchy point is the step that minimizes the quadratic model along the steepest descent direction within the trust region. It is cheap and ensures a minimum decrease.

Methods

model(objective, step_dir, params, loss, ...)	Evaluate the quadratic model at a given step.
optimize_model(objective, params, radius, ...)	Solve the trust-region subproblem.

optimize_model(objective, params, radius, grad_params)

Solve the trust-region subproblem.

Parameters:

objectiveObjectiveFunction

Objective function.

paramsParams

Current parameters.

radiusfloat

Trust-region radius.

grad_paramsParams

Current gradient.

Returns:

Params

Step direction (p) that lies within the trust region.

class DoglegTRSolver(curvature_estimator, solver='solve')

Bases: TrustRegionSolver

Dogleg trust-region solver.

Combines the steepest descent and Newton steps to form a piecewise linear path. The step is the point on this path that reaches the trust-region boundary.

Methods

model(objective, step_dir, params, loss, ...)	Evaluate the quadratic model at a given step.
optimize_model(objective, params, radius, ...)	Solve the trust-region subproblem.

optimize_model(objective, params, radius, grad_params)

Solve the trust-region subproblem.

Parameters:

objectiveObjectiveFunction

Objective function.

paramsParams

Current parameters.

radiusfloat

Trust-region radius.

grad_paramsParams

Current gradient.

Returns:

Params

Step direction (p) that lies within the trust region.

class SteihaugTointTRSolver(curvature_estimator, max_iter=20, atol=1e-08, tol=0.0001, min_iter=2)

Bases: TrustRegionSolver

Steihaug-Toint conjugate gradient trust-region solver.

Uses the CG method to solve the trust-region subproblem, with early termination when the boundary is reached or negative curvature is detected. This is the recommended method for large-scale problems.

Parameters:

curvature_estimatorCurvatureEstimator

Curvature estimator.

max_iterint, default=20

Maximum CG iterations.

atolfloat, default=1e-8

Absolute tolerance for residual norm.

tolfloat, default=1e-4

Relative tolerance for residual norm.

min_iterint, default=2

Minimum number of CG iterations before early stop.

Methods

model(objective, step_dir, params, loss, ...)	Evaluate the quadratic model at a given step.
optimize_model(objective, params, radius, ...)	Solve the trust-region subproblem.

optimize_model(objective, params, radius, grad_params)

Solve the trust-region subproblem.

Parameters:

objectiveObjectiveFunction

Objective function.

paramsParams

Current parameters.

radiusfloat

Trust-region radius.

grad_paramsParams

Current gradient.

Returns:

Params

Step direction (p) that lies within the trust region.