Introduction to Optimization

Fall 2018

MATP6600 / ISYE6780

Course basics:

Exams

Homework

Handwritten notes from Nonlinear Programming:

Convex sets:

• Definitions (Lecture 2).
• Convex hull, Caratheodory, topological properties (Lecture 2).
• Weierstrass Theorem (Lecture 3).
• Separating hyperplanes (Lecture 3).
• The ellipsoid algorithm and cutting plane methods (Lecture 3).

Convex functions

• Convex functions (Lecture 4). See also typewritten notes about two theorems.
• Differentiable convex functions (Lecture 4 and Lecture 5). See also typewritten notes about Hessians of smooth convex functions.
• Strictly convex functions. Subgradients. (Lecture 5 and Lecture 6).
• Optimality conditions with subgradients. Convex cones. (Lectures 6, 7, and 10.) See also typewritten notes about normal cones (Lecture 7).
• Level sets. Concave functions. (Lecture 7.)

Linear programming

• Definitions. Simplex algorithm in matrix form. See also these typewritten notes on basic feasible solutions. (Lecture 8.)
• More on the simplex algorithm. Degeneracy. See also these handouts on the simplex algorithm and an iteration of the simplex algorithm (Lecture 8.)
• Resolution. (skipped.)
• Duality. See also these typewritten notes on duals of linear optimization problems. (Lecture 9.)
• Duals of conic optimization problems. (Lecture 10.)

Optimality conditions for nonlinear programming

• Unconstrained optimization. Fritz-John conditions for constrained optimization. (Lecture 11.)
• Karush-Kuhn-Tucker conditions. Constraint qualification. Here's a better scan of page 95. (Lecture 12.)
• Karush-Kuhn-Tucker conditions for problems with equality constraints See also some information about the Guignard constraint qualification. (Lecture 12).
• Karush-Kuhn-Tucker sufficient conditions (Lecture 12 and Lecture 13).
• Seond-order Karush Kuhn Tucker conditions (typewritten). Here are the old handwritten notes. (Lecture 14).

Duality

• Wolfe dual. (Not covered).
• Lagrangian dual. (Lecture 15).
• Geometric interpretation of Lagrangian dual. (Lecture 15).
• Duality gap with Lagrangian dual. (Lecture 15).
• Strong duality theorem. (Lecture 15 and Lecture 16).
• Saddle point theorems. (Lecture 16).
• Properties of the dual function. See also these typewritten notes. (Lecture 16 and Lecture 17).
• A handout with an example of solving a Lagrangian dual problem with a cutting plane approach.
• Nonsmooth Karush-Kuhn-Tucker conditions, especially as it relates to optimality conditions for the dual problem. (Lecture 17.)
• Gradient method for maximizing the dual function. (Not covered).
• Example of the gradient method. (Not covered).
• Lagrangian duals of quadratic programs. (Lecture 18).
• A Lagrangian approach to solving multicommodity network flow problems. (Lecture 18).
• Quadratic programming and linear complementarity problems. (Lecture 18).

Algorithms

• Introduction to algorithms. (Lecture 19 and Lecture 20).
• Algorithms for unconstrained problems. (Lecture 21: pages 1-13. Lecture 22: pages 14-42. ) See also typewritten notes about various aspects of algorithms, zigzagging with steepest descent, and convergence of Newton's algorithm.
• Limited memory BFGS methods. (Lecture 23.)
• Alternative proofs of convergence for steepest descent and Newton's method.
• Algorithms for constrained problems. (Lecture 24: pages 1-12.) See also typewritten notes about penalty function methods, including augmented Lagrangian methods.
• Interior point methods for NLP slightly updated, along with a page on filter methods. (Lecture 23: pages 1-3.)
• Conic optimization. (Lecture 23.)
• 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 or this paper. (Not covered in 2015.)
• Reduced gradient and active set methods. (Not covered in 2015.)
• Smoothing nonsmooth functions. (Lecture 23.)
• Mirror descent algorithms. (Lecture 23.)
• Alternating direction method of multipliers. (Lecture 24.)
• A gradient sampling algorithm.

Handouts:

Resources: