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 ∥∇f(xk)∥2 > τ do
xk+1 ←xk −η∇f(xk)
05-January-2022
k=k+1 end
Output: xk .
Algorithm 1: Gradient Descent Procedure with constant step length
- 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).
- [R]Whatistheminimizerandminimumfunctionvalueoff(x)=f(x1,x2)=(x1+100)2+(x2−25)2?
- [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.
- [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.
- [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.
2
IE684, IEOR Lab
Lab 01 05-January-2022
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 ∥∇f(xk)∥2 > τ do
ηk = arg minη≥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,Aisasymmetricmatrixofsize2×2,b∈R2 andc∈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 forthefunctionf(x)=f(x1,x2)=(x1+100)2+(x2−25)2. ImplementtheprocedureasaPythonfunction (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.
3
