C&O Comprehensive Exam Syllabus (for July/01 Only)
Continuous Optimization

Examiners:

    Mike Best and Henry Wolkowicz

Disclaimer:

    The following is an attempt to outline the material specifically for the comprehensive exam for July/97. This is only a rough outline for this specific exam.

The questions on the exam emphasize breadth of knowledge, rather than depth. An individual who has successfully taken one of the two courses CO663 or CO666, and who has done some additional reading, should do well.

References:

    The material is covered (with some overlap) in the two books:

1. Numerical Optimization, by Jorge Nocedal, and Stephen Wright, 1999, Springer Verlag.
2. Linear and Nonlinear Programming, D.G. Luenberger, Second Edition
3. The Mathematics of Nonlinear Programming, Peressini, Sullivan, Uhl

Outline:

    The exam covers the basic theory (e.g. attainment, uniqueness of optimal solutions, characterization of optimal solutions) and fundamental algorithms (e.g. Newton's Method, Quasi-Newton Methods, Steepest Descent).

Unconstrained Optimization:

   Basic first and second order algorithms; steepest descent, Newton method, quasi-Newton methods (no memorization of formulae of updates is required), conjugate gradient methods; sufficient decrease criteria and intervals of uncertainty; convergence theorems for Newton's method, line search and trust region methods (global convergence analysis).

Linear Programming:

    Simplex Method, Geometry, Duality and Sensitivity.

Constrained Optimization:

   Equality and inequality constraints; penalty (quadratic and $\ell_1$) and barrier methods, gradient projection methods, sequential quadratic programming methods, augmented Lagrangians; quadratic programming.

Convex Analysis:

    Separating hyperplanes, polarity, subgradients, Lagrange multipliers, duality, convex sets and functions.

Optimality Conditions:

    First and second order optimality conditions, Karush-Kuhn-Tucker theorem, local and global optimality, existence and uniqueness of optima (e.g. coercive functions, strict convexity).

Complexity and NP-Completeness:

    The classes P and NP, NP-completeness. Reference: Combinatorial Optimization, Cook-Cunningham-Pulleyblank-Schrijver, pages 309-323.