All Courses
AI Career Planner
1:1 Coaching/Mentoring
Job Board
SQL
HTML/CSS/JS
Coding
Settings
LogoutLine Search is an optimization algorithm for univariate or multivariate optimization.
The algorithm requires an initial position in the search space and a direction along which to search. It will then choose the next position in the search space from the initial position that results in a better or best objective function evaluation.
The direction is a magnitude indicating both the sign (positive or negative) along the line and the maximum extent to which to search. Therefore, the direction is better thought of as the candidate search region and must be large enough to encompass the optima, or a point better than the starting point.
The line search will automatically choose the scale factor called alpha for the step size (the direction) from the current position that minimizes the objective function. This involves using another univariate optimization algorithm to find the optimal point in the chosen direction in order to select the appropriate alpha.
One approach is to use line search, which selects the step factor that minimizes the one-dimensional function […] We can apply the univariate optimization method of our choice.
— Page 54, Algorithms for Optimization, 2019.
Alpha is a scale factor for the direction, as such only values in the range between 0.0 and 1.0 are considered in the search. A single step of the line search solves a minimization problem that minimizes the objective function for the current position plus the scaled direction:
- minimize objective(position + alpha * direction)
As such, the line search operates in one dimension at a time and returns the distance to move in a chosen direction.
Each iteration of a line search method computes a search direction pk and then decides how far to move along that direction.
— Page 30, Numerical Optimization, 2006.
The line search can be called repeatedly to navigate a search space to a solution and can fail if the chosen direction does not contain a point with a lower objective function value, e.g. if the algorithm is directed to search uphill.
The solution is approximate or inexact and may not be the global solution depending on the shape of the search space. The conditions under which this algorithm is appropriate are referred to as the Wolf conditions.