Nonlinear Programming

Fall 2009

MATP6600 / DSES6780

Course basics:

Course outline
Scores on homeworks and the midterm, for students who handed in all 5 homeworks. The homeworks and the midterm are weighted equally.

Exams

The final exam will be in class on Friday, December 11. Several old exams are available:

Midterm exam, due at beginning of class on Friday November 6. The solutions are available.

Homework

Homework 1, due September 11. The solutions are available.
Homework 2, due September 25. The solutions are available.
Homework 3, due October 9. The solutions are available.
Homework 4, due October 23. Here is some information about AMPL. The solutions to questions 1, 2, and 3 and the AMPL model file, run file, and output file are available.
Homework 5, due November 20.
Homework 6, due December 4.

Handwritten notes:

Introduction (1 Sep).

Convex sets:

Definitions (1 Sep).
Convex hull, Caratheodory, topological properties (4 Sep).
Weierstrass Theorem (4 Sep).
Separating hyperplanes (4 and 8 Sep).
The ellipsoid algorithm and cutting plane methods (8 Sep).

Convex functions

Convex functions (8 and 11 Sep).
Differentiable convex functions (11 Sep).
Strictly convex functions. Subgradients. (11 and 15 Sep).
Optimality conditions with subgradients. Convex cones. (15, 18, and 22 Sep.)
Level sets. Concave functions. (22 Sep.)

Linear programming

Definitions. Simplex algorithm in matrix form. (22 Sep.)
More on the simplex algorithm. Degeneracy. (25 Sep.)
Resolution. (25 Sep.)
Duality. (25 Sep.)

Optimality conditions for nonlinear programming

Unconstrained optimization. Fritz-John conditions for constrained optimization. (25 and 29 Sep.)
Karush-Kuhn-Tucker conditions. Constraint qualification (2 Oct).
Karush-Kuhn-Tucker conditions for problems with equality constraints (6 Oct).
Karush-Kuhn-Tucker sufficient conditions (6 Oct).
Second order Karush-Kuhn-Tucker conditions (9 Oct).

Duality

Wolfe dual. (16 Oct).
Lagrangian dual. (16 Oct).
Geometric interpretation of Lagrangian dual. (16 Oct).
Duality gap with Lagrangian dual. (16 and 20 Oct).
Strong duality theorem. (20 Oct).
Saddle point theorem. (20 and 23 Oct).
Properties of the dual function. (23 Oct).
Gradient method for maximizing the dual function. (27 Oct).
Example of the gradient method. (27 Oct).
Lagrangian duals of quadratic programs. (31 Oct).
A Lagrangian approach to solving multicommodity network flow problems. (31 Oct).

Algorithms

Introduction to algorithms. (3 and 6 Nov).
Algorithms for unconstrained problems. (6, 10, 13, 17, and 20 Nov).
Alternative proofs of convergence for steepest descent (10 Nov) and Newton's method (13 Nov).
Algorithms for constrained problems. (24 Nov, 1, 4, 8 Dec).
Conic optimization (1 Dec).
A gradient sampling algorithm (8 Dec).
Nonsmooth Karush-Kuhn-Tucker conditions (8 Dec).

Handouts:

Extreme points and rays, and resolution (25 Sep).
The simplex algorithm (22 Sep).
An iteration of the simplex algorithm (22 Sep).
Dimension and faces (22 Sep).
Linear algebra (1 Sep).
Subspaces, affine sets, convex sets, and cones (1 Sep).

Resources:

An introduction to the conjugate gradient method without the agonizing pain, by Jonathan Shewchuk.

Convex Optimization by Boyd and Vandenberghe.

John Mitchell's homepage | Dept of Mathematical Sciences Course Materials