Line Search and Trust-Region Methods

Once an optimizer knows which direction to move in to reduce a loss function, it still faces a second question: how far should it step? Step too little and progress crawls; step too much and it overshoots past the improvement, sometimes landing somewhere worse than where it started. Line search and trust-region methods are the two standard families of answers to that question, and most practical optimizers are built from one or the other.

Line search picks the descent direction first (often the negative gradient, or an approximation to it), then searches along that fixed ray for a step length that gives a satisfactory decrease — checking a few candidate lengths, shrinking or growing them, until one meets a condition (like the Armijo rule) that ensures the decrease is meaningful and not just accidental. Trust-region methods work the other way around: they first build a simplified local model of the function (usually quadratic) and trust it only within a bounded region around the current point, then solve for the best step inside that region, expanding the region if the model predicted the actual improvement well and shrinking it if the model was misleading.

The two approaches are like exploring a foggy hillside two different ways: line search walks a straight line downhill and inches forward step by step to see how far the slope holds up; trust-region reasoning draws a circle around where you stand, guesses the terrain inside based on nearby clues, and jumps straight to the best point it can find within that trusted circle, redrawing the circle each time based on how good the last guess turned out to be.