line search

line search is an mathematical optimization technique used in iterative descent methods to find an appropriate step size, , that minimizes the objective function along a given direction starting from a current point .

The intuition is to think of as a measure of how far we have moved away from a point in the direction . In essence, the line search algorithm involves

1. Fixing a direction vector at the current point .
2. Minimizing the objective function along the line , where is the step size.
3. Finding the optimal step size that sufficiently reduces the function value along the direction .

Usage: In Descent Method

Line search is typically integrated into descent method (e.g., gradient descent, Newton-Raphson method, conjugate gradient) to determine the optimal step size for each iteration.

1. Initialize at the starting point .
2. Compute the direction for descent, typically the negative gradient direction in gradient descent or other calculated directions in other methods.
3. Perform line search to find the optimal step size that minimizes the function along the direction :
4. Update the point .
5. Repeat until convergence.

Why Line Search is Important

1. Stability & Improved convergence: Without line search, a fixed step size might lead to overshooting or slow convergence. line search adapts the step size based on the current landscape of the objective function, ensuring more stable updates.
2. Efficiency: By choosing the optimal step size, line search ensures that the algorithm makes meaningful progress at each iteration, avoiding unnecessarily small steps (slow convergence) or overly large steps (which might overshoot the minimum).

Types of Line Search

Aspect	exact line search	inexact line search
Definition	Finds the step size that exactly minimizes .	Finds an that sufficiently reduces , without needing to find the exact minimum.
Precision	Solves the line search problem precisely by determining the exact optimal that minimizes along the search direction.	Approximates the solution to the line search problem, typically using heuristics or conditions like Wolfe conditions
Convergence	Ensures optimality of the step size at every iteration but may not always be necessary for fast convergence.	Balances progress and efficiency, often converging more quickly in practice by accepting good-enough step sizes.
Method Example	Can be solved using numerical approximation method such as bisection method or Newton-Raphson method to minimize .	Typically uses methods like backtracking line search for an efficient estimate of the step size.
Applicability	Best used when the cost of evaluating at each iteration is low or in scenarios where precise step sizes are crucial (e.g., very sensitive problems).	Commonly used in high-dimensional or complex problems or where exact line search is too costly. Often used in algorithms like gradient descent and conjugate gradient