Write a backtracking line search for the Rosenbrock function

PHYSICS · Multi-part · Fermi University Physics · Computational Physics · Scientific programming for physicists · Scientific programming for physicists

Scientific Computing for Physicists, Ch Minimisation with guarantees, with constraints and with randomness

Problem

Write a backtracking line search for the Rosenbrock function f(x,y)=(1−x)2+100(y−x2)2f(x,y)=(1-x)^2+100(y-x^2)^2. Given the current point x\mathbf{x} and a direction d\mathbf{d}, it tries α=1\alpha=1, halves α\alpha while the Armijo condition with c1=10−4c_1=10^{-4} fails, and returns the first α\alpha accepted. It evaluates f(x)f(\mathbf{x}) and ∇f(x)⋅d\nabla f(\mathbf{x})\cdot\mathbf{d} once per call, and stops with an error after 5050 halvings. ((a)) By hand, take one steepest-descent step, d=−∇f\mathbf{d}=-\nabla f, with this search from (0,0)(0,0). Give the number of halvings, the accepted α\alpha and the new value of ff. ((b)) Run steepest descent with your routine for 10001000 iterations from (−1.2,1)(-1.2,1). Give ff at the end and the total number of halvings over the run, and compare the cost with the 2222 iterations Newton's method needs from the same start. ((c)) Pass your routine the uphill direction d=+∇f\mathbf{d}=+\nabla f at (−1.2,1)(-1.2,1) with the cap removed. What does it return, and why is the cap needed?

Browse the problem library