This problem set is due at noon ET on Feb 17, 2023. Please upload a PDF file of your solutions and a ZIP file containing (properly commented) code to Canvas that reproduces any computer output in the solutions. You are encouraged to collaborate on problem sets with your classmates, but the final write-up (including any code) must be your own.

1.  Implementing gradient descent.   Developing good implementation of optimization algo- rithms is not easy. Your task this week is to develop a good implementation of gradient descent. As you shall see, the key to a good implementation of gradient descent (or any line search methods) is a good line search.

(a) Implement gradient descent with a backtracking line search. Use your implementation to minimize

(1.1)                                     f (s1 . s2 ) 全 (1 > s1 )2 + 100(s2 > s1(2))2 n

starting from the initial point (2. 2). Count cost function evaluations, and plot the convergence behavior (e .g. plot suboptimality gap or norm of gradient vs cost function evaluations) of your implementation.

Counting cost function evaluations: Implement the cost function in a separate subroutine that accepts a vector s e R2  and returns a tuple (f (s). ,f (s)). For example, in Python, you could implement the cost function as

def  costF(x):

fx    =  #  evaluate  cost  function  value

Dfx  =  #  evaluate  cost  function  gradient

return  fx,  Dfx

Each time you call this subroutine counts as one cost function evaluation. To minimize cost function evaluations, you can cache previous cost function evaluations.

(b) Implement gradient descent with Barzilai–Borwein step sizes:

st+1 ← st > ηt,f (st).

ft(T)zt 

ηt ←

where ft   全 st  > st_1  and zt   全 ,f (st) > ,f (st_1 ). Show that the Barzilai-Borwein step size is more aggressive than the theoretically justified    step size; i. e . ηt  -  . Use your implementation to minimize (1.1) starting from the initial point (2. 2). Count cost function evaluations and plot the convergence behavior.

(c)  Replace the backtracking line search with your own, more sophisticated line search. Use gradient descent with your line search to minimize (1.1) starting from (>1n2. 1). Describe your line search (like the algorithm/methods section of a research paper), and plot the convergence behavior of gradient descent with your line search. How close to the minimum can you get with 100 cost function evaluations? Report |,f (s)|2 , where s is the iterate from the algorithm after 100 function evaluations.