Nonlinear Programming

Fall 2011

MATP6600 / DSES6780

Course basics:

Scores for the course. Your grade should now be available via SIS. Have a good break!

Exams

• The final exam will be in class on December 9. You can bring one sheet of handwritten notes. Here are some old final exams:
  • 2009 final. Here are the solutions. The mean was 66%.
  • Midterm Exam from Fall 2009. The solutions are available. The mean was 75%.
  • 2007 final. Here are the solutions to a draft of the exam. The mean was 63%.
  • Midterm Exam from Fall 2007. Here are the solutions. The mean was 85%.
  • 2004 final. Here are the solutions. The mean was 47%.
  • Midterm Exam from Fall 2004. Here are the solutions. The mean was 87%.
  • 1999 final. The mean was 74%.
  • Midterm Exam from Fall 1999. Here are the solutions. The mean was 85%.
• Midterm exam, due November 4. Here are the solutions.

Homework

• Homework 1. Here are the solutions.
• Homework 2. Here are the solutions.
• Homework 3. Here are the solutions.
• Homework 4. Here are the solutions to questions 1--3. For questions 4 and 5, an AMPL model file can be constructed, and it can be submitted to the NEOS server along with a run file, resulting in an edited output file.
• Homework 5. Here are the solutions.
• Homework 6. Here are the solutions to questions 1 and 2. Here are my model, data, and output files for question 3.

Handwritten notes:

Convex sets:

• Definitions (30 Aug).
• Convex hull, Caratheodory, topological properties (2 Sep).
• Weierstrass Theorem (2 Sep).
• Separating hyperplanes (2 and 6 Sep).
• The ellipsoid algorithm and cutting plane methods (6 Sep).

Convex functions

• Convex functions (9 Sep).
• Differentiable convex functions (9 and 16 Sep).
• Strictly convex functions. Subgradients. (16 and 20 Sep).
• Optimality conditions with subgradients. Convex cones. (20 and 23 Sep.)
• Level sets. Concave functions. (23 and 27 Sep.)

Linear programming

• Definitions. Simplex algorithm in matrix form. (27 Sep.)
• More on the simplex algorithm. Degeneracy. (27 Sep.)
• Resolution. (27 Sep.)
• Duality. (27 and 30 Sep.)

Optimality conditions for nonlinear programming

• Unconstrained optimization. Fritz-John conditions for constrained optimization. (30 Sep and 4 Oct.)
• Karush-Kuhn-Tucker conditions. Constraint qualification (4 Oct).
• Karush-Kuhn-Tucker conditions for problems with equality constraints (7 Oct).
• Karush-Kuhn-Tucker sufficient conditions (7 Oct).
• Second order Karush-Kuhn-Tucker conditions (14 Oct).

Duality

• Wolfe dual. (Only covered briefly, on 18 Oct).
• Lagrangian dual. (18 Oct).
• Geometric interpretation of Lagrangian dual. (18 Oct).
• Duality gap with Lagrangian dual. (18 Oct).
• Strong duality theorem. (18 and 21 Oct).
• Saddle point theorem. (21 Oct).
• Properties of the dual function. (25 Oct).
• Gradient method for maximizing the dual function. (Not covered).
• Example of the gradient method. (Not covered).
• Lagrangian duals of quadratic programs. (28 Oct).
• A Lagrangian approach to solving multicommodity network flow problems. (1 Nov).
• Quadratic programming and linear complementarity problems. (1 Nov).

Algorithms

• Introduction to algorithms. (4 and 8 Nov).
• Algorithms for unconstrained problems. (11 Nov: pages 1-13. 15 Nov: pages 14-32. 18 Nov: pages 33-45. 22 Nov: pages 46-55.)
• Alternative proofs of convergence for steepest descent and Newton's method.
• Algorithms for constrained problems. (22 Nov: pages 1-12. 29 Nov: pages 13-20. 2 Dec: page 21. 6 Dec: pages 22-25, 32-38.)
• Interior point methods for NLP slightly updated, along with a page on filter methods. (29 Nov: pages 1-2. 2 Dec: pages 3-4.)
• Conic optimization. The material on a conic representation for nonconvex quadratic programming was based on the paper "On the Copositive Representation of Binary and Continuous Nonconvex Quadratic Programs" by Sam Burer, Mathematical Programming, vol 120, 2009, 479-495. (2 Dec.)
• Smoothing nonsmooth functions. (6 Dec.)
• Alternating direction method of multipliers. (6 Dec.)
• A gradient sampling algorithm.
• Nonsmooth Karush-Kuhn-Tucker conditions

Handouts:

Resources: