Nonlinear Programming

Fall 2009

MATP6600 / DSES6780

Course basics:

Exams

Homework

Handwritten notes:

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, ... Nov).

Handouts:

Resources: