MATH:4820 (22M:174) Optimization Techniques
Homework 3 — due Friday March 2nd
1. The Armijo line search algorithm is a very well-known line search method
(and has be re-discovered many times):
Input: f, f, x, a0 > 0,
0 f(x)+c1adT f(x)
a a=2
end while
Show that this algorithm terminates in finite time provided dT f(x) 0, then B is not positive definite. Give
an example of a matrix B that is not positive definite, and vectors d and g
where Bd = g but dTg < 0. This means that Bd = g and dTg < 0 does
not guarantee that B is positive definite.
3. Write a function in Matlab or other suitable programming language to im-
plement Newton’s method for optimization, using the Armijo/backtracking
line search and switching to steepest descent (dk = f(xk)) if the Hessian
matrix Hess f(xk) is not positive definite. Whenever we use the Newton
step (dk = [Hess f(xk)] 1 f(xk)) we use the initial step length parame-
ter a0 = 1 in the line search. Apply this to the function in HW1 Q1 with
various starting points including several close to the saddle point. Report
numbers of function, gradient and Hessian matrix evaluations, and the gra-
dient of the objective function at the end. [Note: It is good programming
practice to have the function or functions for the f and its gradient and Hes-
sian matrix to be separate from the code implementing Newton’s method.
This way, the function etc. can be tested independently of the optimization
method.]
4. Suppose that B is a symmetric positive definite matrix and d = B 1g
with g6= 0. Show that cosq = ( dTg)=kdkkgk (q being the angle be-
tween d and g) is bounded below by l1=ln where the eigenvalues of
1
B are 0 < l1 l2 ln. [Hint: Assume that Bvi = livi where vi,
i = 1;2;:::;n are a set of orthonormal eigenvectors of B, and write d and g
as linear combinations of the vi’s.]