NONLINEAR PROGRAMMING

MSC380.8      ORI391Q.1

CLASS 4      FALL 2003

1 Learning Objectives

A Today's discussions:

a Understand trust region and line search approaches for unconstrained optimization, and their application in guaranteeing convergence of Newton's method.

B Homework and reading assignment in this handout.

a  Understand basic ideas of steepest descent and quasi-Newton methods.

2 (10 minutes) Class discussion of convergence and convergence rate, following Nash and Sofer, pp. 29-32, and of Taylor series approximations on pp. 33-36.

3 (15-20 minutes) Class discussion of Newton's method using readings 5.  We also discuss the proof of order 2 convergence on pages 39-40 of Nash and Sofer, the computational experience on p. 41, and the example of divergence on pp. 42-43.

4 (30-40 minutes) Initial Group meetings:

A Rotate Discussion leader, Observer, and Recorder from last time.

B The group discusses the following issues from sections 10.4 and 10.5 of the text.  We will stop at certain points for class discussion.

C When is the Newton direction a descent direction?

D What is Cholesky factorization?

E How can this factorization be modified to generate descent directions within Newton’s method?

F How can an algorithm that decreases the function at each step fail to converge to a local minimum?

G How can you guarantee that the step size in a line search is not too large (see section 10.5, p. 315, Armijo or sufficient decrease condition)?

H How can you guarantee that the step size is not too small?

I Discuss the assumptions and conclusion of theorem 10.2, p. 316.

J Understand the Wolfe condition, pp. 318-320.

K Understand the steps of the cubic interpolation linesearch, pp. 321-322.

5 (10 minutes) Class discussion of solutions to the homework assigned in the last class.

6 (Rest of class, if time allows) Class discussion of Trust Region concepts, and of trust region variants of Newton's method (section 10.6, text).

A What are the basic ideas of the trust region approach?

B How are these ideas applied in the case of Newton’s method?

C Understand the steps of the trust region algorithm on p. 329.

D Derive the form of the solution of the trust region problem.

7 Homework (Do individually, discuss at next class with your learning group):

A Read and bring any questions you have to class:  Text, Chapter 10, section 10.6, chapter 11, sections 11.1-11.3, readings packet, no. 8.

B Text, p. 323, problems 5, 6; p. 334, problem 1. In problem 1 on page 334, use the Excel Solver to formulate and solve the first 2 trust region subproblems (the one done in the book and the next one) and to compute the ratio of actual to predicted reduction.