The Pierce Lab

ACM 113 (Spring 2001)

Introduction to Optimization

Instructor

Niles A. Pierce
165 Broad
Open office hours

Overview

Optimization problems arise throughout science, engineering and every-day life. Both the problem structure and the solution algorithm may vary widely with application area, and optimization is now a sufficiently large topic that researchers and textbooks rarely span all major problem classes. This course is intended to provide a broad yet meaningful introduction to the fundamental theory and important algorithms associated with a variety of optimization problems.

Unconstrained Optimization

  • optimality conditions, convexity
  • line search methods: Wolfe conditions, backtrack, sufficient descent, Zoutendijk's condition and global convergence of steepest descent, Newton and quasi-Newton line searches, linear convergence of steepest descent, quadratic convergence of Newton's method, Dennis and More's superlinear convergence theorem applied to quasi-Newton methods, properties of linear conjugate gradient methods for solving linear systems, convergence behavior of Fletcher-Reeves and Polak-Ribiere nonlinear conjugate gradient methods, nonlinear CG global convergence results, inexact Newton steps, truncated Newton-CG methods for possibly indefinite Hessians, Hessian-free Newton methods via finite differencing or the complex variable method, quasi-Newton methods, the BFGS update, BFGS global and local convergence results
  • trust region methods: trust metric, trust region control, the Cauchy point, trust region CG methods for possibly indefinite Hessians, Cauchy point reduction, the global convergence theorem of Schultz, Schnabel and Byrd, local convergence and preconditioning

Linear Programming

  • standard form, extreme points, basic feasible points, fundamental theorems of LP, the dual problem, weak duality, strong duality, complementary slackness, optimality conditions
  • the simplex method, basis selection, descent, finite termination, initialization by the two-phase method, pricing, resolving degneracy by lexicographic perturbation, complexity
  • primal-dual interior-point methods, the central path, convergence and complexity analysis of a long-step path-following method, a practical predictor-corrector primal-dual method

Nonlinear Programming

  • Lagrange multipliers and the Lagrangian, constraint qualifications, regularity, Karsuh-Kuhn-Tucker necessary conditions, strict complementarity and degenerate constraints, sufficient conditions, sensitivity
  • interior-point methods for convex quadratic programming, logarithmic barrier methods, quadratic penalty methods, augmented Lagrangian methods

Integer Programming

  • cutting plane methods, branch and bound methods, complexity theory, the classes P and NP, NP completeness

Texts

  • S.G. Nash and A. Sofer, Linear and Nonlinear Programming, McGraw-Hill, 1996.
  • J. Nocedal and S.J. Wright, Numerical Optimization, Springer, 1999.
  • C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Dover, 1998.

Reserve Texts

  • D.P. Bertsekas, Nonlinear Programming, Athena Scientific, 1999.
  • R. Fletcher, Practical Methods of Optimization, Wiley, 1987.
  • L.A. Wolsey, Integer Programming, Wiley, 1998.

Grading

Problem Sets: 70%
Final Exam: 30%
Final Project: Extra credit