IE684-Lab5 Solved

Exercise 1: BFGS Method

 

k ← 0;

 

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

2.    Implement the modules of BFGS method to solve the problem minx∈Rn f(x) where we have f(x) = f(x1,x2,...,xn)

 . Use backtracking line search with α0 = 0.9,ρ = 0.5,γ = 0.5 in the imple-

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 backtracking 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.

Exercise 2:

In this exercise we shall consider the following problem:

 .

x

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 backtracking 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.