NONLINEAR PROGRAMMING

MSC380.8      ORI391Q.1

CLASS 3

FALL 2003

1 Learning Objectives

A Today's discussions:

a Review convexity material.

b Understand the basic descent algorithm.

c Understand convergence rate definitions and ideas.

d Understand Newton's method and its convergence behavior.

B Homework and reading assignment in this handout.

a Understand trust region and line search approaches for guaranteeing convergence of Newton's method.

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

2 (5-10 minutes) Initial group meetings to review the solutions to the class 2 homework handed out today.  Rotate discussion leader, recorder, and spokesperson from last time, read the solutions, and compare with yours.  Record any questions for class discussion. Also, answer the following questions: In problem 9 on p. 301 of the text, what difficulties arise in minimizing the function in part c, f3(x)?  Is f3(x) convex?  Why or why not?  Does the result of problem 11 on p. 24 apply to f3?

3 Class discussion of convexity homework, the above question, and the convexity material in readings 1.

4 (15-20 minutes) Class discussion of general optimization algorithm, search direction and step size, descent direction, linesearch. (See readings 4 and section 2.4 text). We start by discussing why, in general, solutions of NLP’s can only be obtained as the limit of an infinite sequence of steps.

5 (15 minutes) Class discussion of convergence and convergence rate.

6 (Rest of class) Lecture and class discussion on Newton's method (Section 2.7 and Ch.10, text).

7 Homework (Do in your learning groups, hand in to be graded)

A Read and bring any questions you have to class:  Text, Chapter 10, Readings packet, nos. 5-7.

B Text, p.311, problem 4, p. 323, problems 1,3. In p.323 problem 1, solve the Newton equations in any way you wish-you need not use Cholesky.

C Given the function f(x) = (x1-2)^2+10*(x2-1)^2 and the point p = (3,3):

a Sketch the contour of f passing through p.

b Define mathematically and on the sketch the set of descent directions for f at p.

c Compute the negative gradient of f at p and plot it.

d Is (-1,2) a descent direction for f at p?  Show why or why not on your graph.

e Compute the search direction, dn, for Newton's method at p and verify that p+dn = (2,1).  Plot the direction on the graph.