The following is an attempt to outline the material specifically for the
comprehensive exam for July/02. 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 three books:
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 l1)
and barrier methods, gradient projection methods, sequential
quadratic programming methods, augmented Lagrangians; quadratic
programming.
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.