IE684 Lab 05 Solved

Exercise 1: BFGS Method

k ← 0;
Start with a suitable point xk ∈ Rn; while not converged do

pk ← −(Bk)∇f(xk);
αk ← argminα≥0f(xk + αpk);
xk+1 ←xk +αkpk;
sk = xk+1 − xk ;
yk =∇f(xk+1)−∇f(xk);
Implement the update rule to update Bk+1. ; k ← k + 1;

end

Algorithm 1: BFGS Method
1. [R] What is a suitable initial choice of B (denoted by B0)? Justify with proper reasons.

09-February-2022

2. ImplementthemodulesofBFGSmethodtosolvetheproblemminx∈Rn f(x)wherewehavef(x)=f(x1,x2,…,xn) =􏰈n−1 􏰆4(x2 − x )2 + (x − 1)2 )􏰇. Use backtracking line search with α0 = 0.9, ρ = 0.5, γ = 0.5 in the imple-

i=1 i i+1 i
mentation of BFGS method. Take the starting point to be x0 = (0, 0, . . . , 0).

3. [R] Take n ∈ {1000, 2500, 5000, 7500, 10000}, find minimizer of the objective function in each case and compute the time taken by the BFGS method with backtracking line search. Tabulate the time taken by BFGS method for each n.
4. Use Newton’s method to solve the problem minx∈Rn f(x) . In Newton’s method implementation, use back- tracking line search with α0 = 0.9,ρ = 0.5,γ = 0.5. Take the starting point to be x0 = (0,0,…,0) in the implementation of Newton’s Method.
5. [R] Take n ∈ {1000, 2500, 5000, 7500, 10000}, find minimizer of the objective function in each case and compute the time taken by the Newton’s method with backtracking line search. Tabulate the time taken by Newton’s method for each n.
6. [R] Compare the time taken by BFGS method with backtracking line search against the time taken by Newton’s method with backtracking line search for each value of n. Plot the time taken by both methods vs n using different colors. Comment on your observations.

2

IE684, IEOR Lab Lab 05

Exercise 2:

In this exercise we shall consider the following problem:
min n q(x1,x2,…,xn)=􏰂􏰄(xi −1)2 +(x1 −x2i)2􏰅.

x=(x1 ,x2 ,…,xn )∈R

09-February-2022

1. Implement the required modules to compute the objective function value, gradient and Hessian for q(x).
2. Use BFGS method to solve the problem minx∈Rn q(x). Use backtracking line search with α0 = 0.9, ρ = 0.5, γ =

   0.5 in the implementation of BFGS method. Take the starting point to be x0 = (0, 0, . . . , 0).

3. [R] Take n ∈ {1000, 2500, 5000, 7500, 10000}, find minimizer of the objective function in each case and compute the time taken by the BFGS method with backtracking line search. Tabulate the time taken by BFGS method for each n.
4. Use Newton’s method to solve the problem minx∈Rn q(x). In Newton’s method implementation, use back- tracking line search with α0 = 0.9,ρ = 0.5,γ = 0.5. Take the starting point to be x0 = (0,0,…,0) in the implementation of Newton’s Method.
5. [R] Take n ∈ {1000, 2500, 5000, 7500, 10000}, find minimizer of the objective function in each case and compute the time taken by the Newton’s method with backtracking line search. Tabulate the time taken by Newton’s method for each n.
6. [R] Compare the time taken by BFGS method with backtracking line search against the time taken by Newton’s method with backtracking line search for each value of n. Plot the time taken by both methods vs n using different colors. Comment on your observations.

n i=1

3