CMSC 477: OPTIMIZATION

Catalog Description

Linear programming including the simplex algorithm and dual linear programs, convex sets and elements of convex programming, combinatorial optimization, integer programming. Listed also as MAPL 477.

Prerequisites

CMSC/MAPL 460, 466, or 467.

Topics

  1. Convex sets (1 week)\\ Definitions of hull, cone, hyperplane, polytope, extreme points; separating hyperplane theorem; supporting hyperplane theorem.
  2. Linear programming (5 weeks)\\ Examples, standard form, geometric and algebraic structure, revised Simplex algorithm, duality, affine transformation algorithms.
  3. Unconstrained optimization (5 weeks)\\ Necessary and sufficient conditions for minimizers, order of convergence, one dimensional algorithms (Fibonacci, golden section, curve fitting, practical line search algorithms), multidimensional algorithms (steepest descent, Newton's method, conjugate gradients, quasi-Newton methods).
  4. Constrained optimization (3 weeks)\\ Necessary and sufficient conditions for minimizers, inequality constraints, gradient projection algorithms with active set strategy.

Course Text

David G. Luenberger, Linear and Nonlinear Programming, Addison-Wesley, 1984.

Typical Grading and Workload