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
- 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