Exercise · ZW-LINE-SEARCH-009 · ★★★ Advanced
With \(f(x)=x^2\), \(x_k=2\), \(p_k=-4\), \(c_1=0.25\), \(\rho=0.5\) and starting at \(\alpha=1\), which step does backtracking accept?
Choose one option.
Show answer
- B. \(\alpha=\tfrac12\)
Explanation
With \(\alpha=1\) the point is \(-2\), with \(f=4\), and the bound is \(0\), so it fails. With \(\alpha=\tfrac12\) the point is \(0\), with \(f=0\) against a bound of \(2\), so it holds. Steps of \(2\) and \(\tfrac32\) are never reached, since backtracking has already stopped.
Review the concept: Line search
Line search is a procedure that chooses the step size \(\alpha\) along a descent direction \(p_k\) to reduce the value of the objective function.
\[f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k\]
More practice problems: line search
- ZW-LINE-SEARCH-001 What does the Armijo condition require of the step α?
- ZW-LINE-SEARCH-002 What is the name of the method that reduces α by multiplying it by rho until the condition holds?
- ZW-LINE-SEARCH-003 What must the direction p_k satisfy for line search to make sense?
- ZW-LINE-SEARCH-004 What happens if the step α is too large?
- ZW-LINE-SEARCH-005 Which parameter controls the minimum slope required by the Armijo condition?
- ZW-LINE-SEARCH-006 With f(x)=x^2, x_k=1, p_k=-2, c_1=0.5 and rho=0.5, which step does backtracking accept if it starts…
- ZW-LINE-SEARCH-007 With f(x)=x^2, x_k=1, p_k=-2 and α=tfrac12, what is x_k+1?
- ZW-LINE-SEARCH-008 With ∇ f(x_k)^top p_k=-4, c_1=0.25 and α=2, what is c_1α∇ f(x_k)^top p_k?