IE684-Lab1 Solved

Exercise 1: Gradient Descent

We will start with a procedure which helps to find a minimizer of the function f(x),x ∈Rn.

We will use the following gradient descent type algorithm:

 

 Input: Starting point x0, Stopping tolerance τ, Step length η. Initialize k = 0 while k∇f(xk)k2 > τ do xk+1 ← xk − η∇f(xk)

k = k + 1

end

Output: xk.

Algorithm 1: Gradient Descent Procedure with constant step length

 

1.    Note that in the notebook file shared with you, Algorithm 1 is implemented to solve f(x) = f(x1,x2) = (x1+100)2+(x2−25)2 with a constant step length η = 0.1, stopping tolerance τ = 0.001 and with the starting point x0 = (10,10).

2.    [R] What is the minimizer and minimum function value of f(x) = f(x1,x2) = (x1 + 100)2 + (x2− 25)2?

3.    [R] With starting point x0 = (10,10) and η = 0.1, we will now study the behavior of the algorithm for different tolerance values. Try τ = 10−p where p = 1,2,...,10. For each τ, record the final minimizer, final objective function value and number of iterations taken by the algorithm to terminate. Prepare a plot where the number of iterations is plotted against τ values. Comment on the observations. Comment about the minimizers and objective function values obtained for different choices of the tolerance values.

4.    [R] With starting point x0 = (10,10) and τ = 10−5, we will study the behavior of the algorithm for different step length values. Try η ∈ {0.0001,0.001,0.01,0.1,0.2,0.4,0.5,0.6,0.7,0.8,0.9}. For each η, record the final minimizer, final objective function value and number of iterations taken by the algorithm to terminate. Prepare a plot where the number of iterations is plotted against η values. Comment on the observations. Comment about the minimizers and objective function values obtained for different choices of the step length values.

5.    [R] With τ = 10−5 and η = 0.1, we will study the behavior of the algorithm for different starting points. Consider x0 ∈{(10000,10000),(500,0),(0,1000),(1,1),(−500,−2)}. Prepare a table listing the final minimizer, final objective function value and number of iterations taken by the algorithm to terminate for the different starting points. Comment on your observations.

 

Exercise 2: Line Search

In this exercise, we will design a procedure to find a suitable step length. We consider the following algorithm:

 

 Input: Starting point x0, Stopping tolerance τ. Initialize k = 0 while k∇f(xk)k2 > τ do ηk = argminη≥0 f(xk − η∇f(xk)) xk+1 ← xk − ηk∇f(xk) k = k + 1

end

Output: xk.

Algorithm 2: Gradient Descent Procedure with line search to compute step length

 

1.    [R] Write the function f(x) = f(x1,x2) = (x1 + 100)2 + (x2 − 25)2 in the form x>Ax + 2b>x + c, where x ∈R2, A is a symmetric matrix of size 2 × 2, b ∈R2 and c ∈R.

2.    [R] It turns out that for a function of the form f(x) = x>Ax + 2b>x + c, where A ∈Rn×n is a symmetric matrix, b ∈Rn and c ∈R, the analytical solution to minα≥0 f(x−α∇f(x)) can be found in closed form. Find the solution.

3.    Use the answers to Questions 1 and 2 to design a procedure to compute the step length ηk in Algorithm 2

for the function f(x) = f(x1,x2) = (x1 + 100)2 + (x2 − 25)2. Implement the procedure as a Python function (complete the code in compute steplength module in the notebook).

4.    [R] With starting point x0 = (10,10) and the new module to compute ηk, try τ = 10−p where p = 1,2,...,10. For each τ, record the number of iterations taken by the algorithm to terminate. Prepare a plot where the number of iterations is plotted against τ values. Compare and contrast the plot with the plots obtained in Exercise 1 with fixed step length values.