NONLINEAR PROGRAMMING

MSC380.8  ME391Q.1

Class 19   Fall 2003

1 Learning Objectives

A Today’s discussions

a NLP duality homework.

b Lagrangian Duality results.

c Lagrangian relaxation paper-Fisher.

B Homework and reading assignment in this handout

a Understand the basic ideas of GRG algorithms.

2 (15-20 minutes) Class discussion of the solutions to the two duality problems assigned for homework last class.

A Each learning group discusses the handed out solution to problem B of class 18, comparing it to theirs.

B Class discussion of this problem.  We compare the graphs of the dual objective to those in figure 8-1 on p. 410 and figure 8-2 on p. 411, readings 13.

C Class discussion of proofs of the two duality theorems handed out today.

3 (5-10 minutes) Class discussion of theorems 1 and 2 on p. 412.  Each group discusses each step of the proof of Theorem 2.  Then we discuss it as a class.

4 (10-15 minutes) Class discussion of theorem 3 on p. 413, and the geometric interpretation on pp. 415-419.

5 (Rest of Class) Class discussion of Marshall Fisher’s Lagrangian Relaxation paper.

6 Homework:

A Read readings packet numbers 14-16 (GRG algorithms), and be prepared to discuss them in the next class. Try to understand the derivation of the formula for the reduced gradient on p. 77 and its relation to the KTC on p. 78 of the RAIRO paper. Examine the iteration logs and use the algorithm description to understand what is happening.

B Code the following problem in Excel and solve it from three starting points using the Excel Solver: max 3x1-2*x2**2 subject to 2x1-x2>=0, x1+x2<=4,x1>=0,x2>=0.  Make at least one starting point infeasible.  Turn on the “show iteration results” option, record the points shown (“save scenario” is helpful here), and plot them on a graph of the feasible region.  Hand in one solution per learning group. Due in the class after next.