Does line search require a linear objective?

No. It evaluates a possibly nonlinear objective along a chosen line in parameter space.

Is exact line search always preferable?

No. Its extra computation may not justify the benefit compared with an appropriate inexact rule.

Can line search guarantee a global optimum?

Not by itself. Such guarantees depend on the full optimization method and properties of the objective.

AI Glossary / Graphs and symbolic AI / Intermediate

Line search

Definition

Line search is an optimization procedure that chooses how far to move from a current point along a selected direction. It evaluates or estimates the objective along that line and selects a step size according to an acceptance rule. The direction and the step size are separate decisions, even when both belong to the same optimization algorithm.

What it means

Suppose the current parameter vector is x and a proposed direction is p. A line search considers points x + t p for step sizes t, usually positive in a descent method. Even if x has many components, choosing t is a one-dimensional problem along the specified direction.
The word line does not mean that the original objective must be linear. A nonlinear loss surface can be searched along a straight direction in parameter space. Line search is also different from linear search through a list of records, which is a data-retrieval procedure rather than an optimization step.

How it works

An exact line search seeks a minimizing step along the chosen direction under the specified range. Inexact methods instead accept a step satisfying suitable conditions, avoiding the expense of solving the one-dimensional problem precisely.
Backtracking starts with a trial step and reduces it until an acceptance test is met. A common test asks for sufficient objective decrease relative to the local slope. Other methods use Wolfe conditions, combining decrease and curvature requirements. The objective's properties and the chosen direction matter: a descent-based rule should not be assumed to work with an arbitrary ascent direction or noisy evaluations without further care.

Three practical examples

A gradient-based optimizer selects a step along the negative gradient rather than using an unchanged step size at every iteration.
A Newton-type method reduces a proposed step when the full step does not satisfy its acceptance conditions.
An optimization lesson compares the cost of exact minimization along a direction with a cheaper sufficient-decrease test.

Think of it this way

Think of choosing both a walking direction and how many steps to take before checking your position again. Line search handles the distance choice after the direction has been selected. The analogy is limited because mathematical acceptance tests use objective values and derivatives, and a good step in one direction does not guarantee the best destination across the whole landscape.

Worked example

Consider the invented one-dimensional objective f(x) = (x - 3)^2. Start at x = 0, where f(0) = 9 and the derivative is -6. Choose the negative-gradient direction p = 6, so candidate points are x + t p = 6t.
Use a backtracking sufficient-decrease test f(x + t p) <= f(x) + c t f'(x)p with c = 0.1. Since f'(x)p = -6 times 6 = -36, the right-hand side is 9 - 3.6t.
First try t = 1. The candidate is x = 6 and f(6) = 9. The acceptance threshold is 5.4, so 9 does not satisfy the test. Halve the step to t = 0.5. The candidate is x = 3, with objective zero, and the threshold is 7.2. The test now passes.
For this simple quadratic, t = 0.5 also happens to be the exact minimizing step, but backtracking does not generally return an exact line minimizer. The example demonstrates a checked acceptance calculation, not a universal choice of c or a claim that one iteration solves arbitrary optimization problems.

Illustrative case study

In a fictional modeling project, Birch Fit applies every proposed parameter update at full length. Some iterations increase the objective substantially. Developers add a documented line-search rule and inspect whether the proposed directions satisfy the assumptions needed by that rule.
They compare total objective evaluations and final optimization quality rather than counting only outer iterations. The invented case illustrates step-size control. It does not claim that adding line search fixes an incorrect gradient, an unsuitable model, or every difficulty associated with nonconvex optimization.

Common misconceptions and mistakes

Line search does not choose the best direction across all possibilities; it searches along the direction supplied to it. An exact line minimum is therefore not automatically a global minimum of a multidimensional objective.
Do not equate every smaller step with a better step. Excessively small steps can make progress slow, while large steps can fail the acceptance condition. Also, an inexact line search is not necessarily a careless approximation: its conditions can support rigorous convergence results under appropriate assumptions. Those guarantees must be matched to the objective and outer optimization method.

Business use

The concept matters when a business model or planning component depends on numerical optimization. A suitable line search can improve the reliability of parameter updates, but each trial may require an expensive objective or gradient calculation.
Measure total computation and convergence behavior on representative problems. Check gradients, scaling, stopping conditions, and how the implementation reports a failed search. For noisy objectives, determine whether the selected line-search assumptions are appropriate. Treat the step-selection procedure as one component of the optimizer rather than a substitute for validating the overall model and its solution quality.

Check your understanding

Why is the first trial rejected in the worked example even though it does not increase the objective?

Answer: The chosen test requires sufficient decrease, not merely no increase. The objective remains 9, while the threshold at t = 1 is 5.4.

Related terms

Step size
Gradient descent
Objective function
descent direction
backtracking
Armijo condition
Wolfe conditions
Newton's method

Learn next

Repeat the worked example with trial step t = 0.25 and check the same inequality. Then compare the accepted step with the exact minimizer along the line, keeping direction choice separate from step-size choice.

Step size

Sources

Sources: Boyd and Vandenberghe, Convex Optimization, original lecture slides on descent methods and line search: https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf SciPy, official line_search documentation: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.line_search.html

Previous: Line sampling Next: Line spectral pairs