Back to the on-screen lesson ·
Two answers to how far, the sufficient-decrease condition, and when a trust region is the safer one.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to run a backtracking line search by hand, state the sufficient-decrease condition and explain with an example why accepting any decrease lets a method stall short of the minimum. You will also be able to describe a trust region, compute and read its ratio of actual to predicted improvement, and say which of the two step controls suits a problem depending on whether the direction or the local model is the doubtful part.
From lesson 14: the step size decides between crawling, converging, oscillating and diverging, and the threshold depends on a curvature nobody told you. Guessing it once for the whole run is what this lesson replaces, with two different answers that differ in which decision they make first.
Line search. Fix a descent direction $d_k$, then choose how far along it. The useful version is backtracking: try a full step, and while it fails a test, halve it.
The test is not "did the objective fall". Any-decrease is not enough, because improvements can shrink fast enough to sum to a finite amount and stall short of the minimum. The sufficient decrease (Armijo) condition asks for
$$f(x_k + t d_k) \le f(x_k) + c\, t\, \nabla f(x_k)^\top d_k$$
with a small $c$ (typically $10^{-4}$). It demands a fall proportional to how far you went and how steep it was — which is what ties the improvements to the distance travelled and rules out stalling.
Trust region. Reverse the two decisions. Choose a radius $\Delta_k$ you believe the local model over, build a model $m_k$ (usually quadratic), and minimise it inside the ball of that radius. Then judge the result:
$$\rho_k = \frac{\text{actual improvement}}{\text{predicted improvement}}.$$
| $\rho_k$ | Reading | Action |
|---|---|---|
| near $1$ | the model was accurate | accept, and enlarge $\Delta$ |
| moderate | usable | accept, keep $\Delta$ |
| near $0$ or negative | the model was wrong | reject, and shrink $\Delta$ |
Which to use. If the direction is trustworthy and only the length is in question, a line search is simpler. If the model is the doubtful part — noisy objectives, poor curvature estimates, or an indefinite Hessian — a trust region handles it better, because a bad model then produces a short step rather than a confident stride in the wrong direction.
Another way: picture
Two ways to cross unfamiliar ground in fog. In the first you pick a bearing and then decide how many paces to walk on it. In the second you decide you can see fifty paces and then choose the best point within fifty paces. When the fog is thick, the second is the one that keeps you safe.
Another way: steps
Backtracking line search, in full:
Each rejection costs one objective evaluation and no gradient evaluation, which is why the loop is cheap even when it rejects several times.
Minimise $f(x) = x^2$ from $x_0 = 2$, and suppose a method takes steps that leave $x_k = 1 + 2^{-k}$. Every step strictly decreases the objective — the sequence of values is decreasing — and every step passes an "is it lower" test.
But $x_k \to 1$, and $f(1) = 1$, while the minimum is $0$. The method converges to a non-minimiser, having improved at every single iteration.
What went wrong is that the improvements shrank faster than the distance remaining. The sufficient-decrease condition forbids exactly this: it requires the fall to be at least proportional to $t\,\|\nabla f\|^2$, so a step taken where the gradient is still substantial has to earn its keep. It is one inequality and it is the difference between a method that descends and a method that converges.
Accepting any decrease. As above: it converges, to the wrong place.
A fixed step size chosen once. It is the special case where the search does no searching, and it has to be tuned per problem and re-tuned when the problem changes.
Never allowing the step to grow. A backtracking search that only ever shortens will crawl once it has been forced small. The trial step is reset each iteration for that reason, and trust-region radii are allowed to grow on a good ratio.
Using the model's prediction as the improvement. The ratio compares predicted against actual precisely because they differ. Reporting the prediction is reporting what the model hoped for.
A single number chosen before the run has to be small enough for the steepest part of the whole trajectory, which makes it far too small everywhere else — and when the problem changes, it has to be found again by trial and error. A line search or a trust region turns that setting into a computation: each iteration asks how far is safe here, using information the run has just produced. The cost is a few extra objective evaluations per iteration; what it buys is a method that works on a problem nobody has tuned it for, which is the only kind of method worth having outside a textbook.
$f(x) = x^4$ at $x = 1$, so $f = 1$ and $f' = 4$. Direction $d = -4$; trial step $t = 1$ gives $x = 1 - 4 = -3$ and $f = 81$. Far worse: reject.
The full step overshoots badly.
Halve: $t = 1/2$ gives $x = -1$ and $f = 1$. No decrease at all: reject.
Still not enough.
Halve again: $t = 1/4$ gives $x = 0$ and $f = 0$. A decrease, and a large one: accept. Two rejections cost two objective evaluations and the gradient was computed once — which is the economics that make this loop worth running every iteration.
Cheap rejections, one gradient.
At $x_k$ the quadratic model predicts the objective will fall by $10$ if a step of length $\Delta = 2$ is taken.
The prediction.
The step is taken and the objective falls by $1$. The ratio is $\rho = 0.1$: the model was badly optimistic over that distance.
The reality.
So the step is rejected and $\Delta$ is cut to $0.5$. The model is not fixed — it is the same model — but it is now only trusted over a quarter of the distance, where it is more likely to be right. The method is learning how far its own approximation is good for, which is something a line search never asks.
The radius is the thing being learned.
$f(1) = 1$, $f'(1) = 2$, direction $d = -2$. Trial $t = 1$: $x = 1 - 2 = -1$, $f = 1$. No decrease at all, so it fails any test: reject.
Start with the full step.
Halve: $t = 1/2$ gives $x = 0$, $f = 0$. A fall of $1$, against a sufficient-decrease requirement of about $c \cdot \tfrac12 \cdot 4 = 2c$, which for $c = 10^{-4}$ is tiny. Accept.
One halving. And note this landed exactly on the minimum, which is what $t = 1/2$ does on $x^2$ — the search found the ideal step by trying the obvious one and halving once, with no knowledge of the curvature at all. That is the appeal: it needs nothing about the problem beyond the ability to evaluate it.
Match each step-control observation to the appropriate action.
| Shorten the trial line-search step | Increase the trust-region radius | Decrease the trust-region radius | |
|---|---|---|---|
| Backtracking trial fails sufficient decrease | |||
| Trust-region ratio is close to one | |||
| Trust-region ratio is close to zero |
A backtracking line search starts at step size $14$ and halves it after each rejected trial. Fill in the trial step sizes.
| trial step size | |
|---|---|
| First trial | 14 |
| After one rejection | |
| After two rejections | |
| After three rejections |
Why does a line search demand a decrease *proportional to the step*, rather than accepting any decrease at all?
| Can stall short of the minimum | May have finite total improvement | Rules out inadequate progress | Shorten the step and retry | |
|---|---|---|---|---|
| Accept any strictly lower objective value | ||||
| Improvements form a rapidly shrinking series | ||||
| Require decrease proportional to step and gradient size | ||||
| Trial step fails sufficient decrease |
Put the steps of a backtracking line search in order.
Number the steps in order (write the number in the box):
A trust-region method enlarges its radius when the ratio of actual to predicted improvement is at least $3/4$, and shrinks it below $1/4$. For which ratios $r$ is the radius left unchanged? Give the set.
This task has no paper form; do it on a device.
After 6 noisy iterations, a method's local model is unreliable and its curvature estimate is poor. Which step control suits it better?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
After 2 noisy iterations, a method's local model is unreliable and its curvature estimate is poor. Which step control suits it better?
You can run a backtracking search, say why sufficient decrease is needed, and read a trust-region ratio. Next: a direction that uses curvature rather than only slope.
9. Your turn: how many halvings to accept a step on $f(x) = x^2$ from $x = 1$?, step 3