3.3 Trust region methods

Trust region methods are a powerful approach to unconstrained optimization. They work by creating a local model of the objective function within a trusted area, then solving a subproblem to find the best step.

These methods balance exploration and reliability by adjusting the trust region size. They're especially useful for handling non-convex functions and can be more robust than line search methods in challenging scenarios.

Trust Region Fundamentals

Trust Region Concept and Model Function

Top images from around the web for Trust Region Concept and Model Function

• 

  Approximating Areas · Calculus View original

  Is this image relevant?

• 

  Trust region - Wikipedia View original

  Is this image relevant?

• 

  Gradient descent/ nonlinear optimization intuition needed - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Approximating Areas · Calculus View original

  Is this image relevant?

• 

  Trust region - Wikipedia View original

  Is this image relevant?

1 of 3

Top images from around the web for Trust Region Concept and Model Function

• 

  Approximating Areas · Calculus View original

  Is this image relevant?

• 

  Trust region - Wikipedia View original

  Is this image relevant?

• 

  Gradient descent/ nonlinear optimization intuition needed - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Approximating Areas · Calculus View original

  Is this image relevant?

• 

  Trust region - Wikipedia View original

  Is this image relevant?

1 of 3

• Trust region defines area where quadratic model approximates objective function accurately
• Model function serves as local approximation of objective function within trust region
• Quadratic model typically used as model function due to computational efficiency
• Trust region constrains step size to ensure model remains valid approximation
• Model function incorporates gradient and Hessian information of objective function

Trust Region Radius and Acceptance Ratio

• Trust region radius determines size of region where model is considered reliable
• Radius dynamically adjusted based on agreement between model and actual function
• Acceptance ratio measures quality of model prediction compared to actual function change
• Ratio calculated as actual reduction in objective function divided by predicted reduction
• Acceptance ratio guides algorithm in updating trust region size and accepting steps

Trust Region Algorithm Process

• Algorithm iteratively solves subproblem within current trust region
• Proposed step evaluated using acceptance ratio to determine quality
• High acceptance ratio (close to 1) indicates good model agreement, may increase trust region
• Low acceptance ratio suggests poor model fit, leads to trust region reduction
• Process repeats until convergence criteria met (gradient near zero or step size sufficiently small)

Trust Region Subproblem

Subproblem Formulation and Solution Methods

• Trust region subproblem minimizes model function subject to trust region constraint
• Constraint typically expressed as Euclidean norm of step bounded by trust region radius
• Exact solution computationally expensive for large-scale problems
• Approximate solutions often sufficient for practical optimization
• Iterative methods (conjugate gradient, Lanczos) can efficiently solve large-scale subproblems

Cauchy Point and Its Significance

• Cauchy point represents steepest descent step within trust region
• Calculated by minimizing model along negative gradient direction
• Provides guaranteed reduction in model function
• Serves as fallback option when more sophisticated methods fail
• Convergence theory often based on achieving at least Cauchy point reduction

Dogleg Method for Subproblem Solution

• Dogleg method combines steepest descent and Newton steps
• Constructs piecewise linear path from origin to Newton point
• Path consists of steepest descent segment followed by direct line to Newton point
• Intersection of path with trust region boundary determines step
• Computationally efficient for problems where Hessian factorization is feasible
• Dogleg method often outperforms Cauchy point in practice