Trust Region Methods

“In preparing for battle I have always found that plans are useless, but planning is indispensable.” – Dwight D. Eisenhower

If more complex situations, e.g., the objective function is non-convex, or ill-conditioned, or noisy, trust region method can be deployed as an encapsulating method on top of line search methods, which makes such class of iterative methods more reliable and robust.

• a. General Method workflow:
  • i. The method applies following in nutshell:
  • ii. Approximate the local region of the current location as a quadratic function.
  • iii. Starting with a unit circular ‘trust region’.
  • iv. Use a line search method to solve each subproblem within the ‘trust region’, to find both the direction (gradient) and step size (steepest descent magnitude) of optimization.
  • v. If the magnitude exceeds the boundary of current trust region, clip the stepsize to the trust region boundary, and take optimization step based on the direction and stepsize.
  • vi. Evaluate the outcome of this step, compare the amount of actual descent with predicted descent, and adjust the trust region in the next step based on the soundness of prediction, and repeats the next cycle.
• b. Typical line search method for Trust Region subproblem:
  • i. Trust Region Cauchy Point: using equivalent of Steepest Descent as line search method.
  • ii. Trust Region Dogleg: balance between global (guided by gradient) and local (guided by optima of local quadratic approximation) optima during search.
  • iii. Trust Region Conjugated Gradient: using conjugated gradient method as line search method.

References:

https://optimization.mccormick.northwestern.edu/index.php/Trust-region_methods

https://www.youtube.com/watch?v=DQZ-ASNrXTM&list=LL&index=16&t=354s