Outline

1.

Optimization

(a)

Background

i.

Taylor's theorem for functions of several variables

ii.

Rates of convergence

iii.

The contractive mapping theorem

(b)

Basic optimization theory

i.

Unconstrained optimization

a.

First-order necessary conditions

b.

Second-order necessary conditions

c.

Second-order sufficient conditions

ii.

Constrained optimization (including equality and inequality constraints)

a.

First-order necessary conditions

b.

Second-order necessary conditions

c.

Second-order sufficient conditions

d.

Necessary and sufficient conditions for a solution of the trust region subproblem

iii.

Convexity

a.

Necessary and sufficient conditions

b.

Global optimization

(c)

Algorithms for unconstrained optimization

i.

Newton's method (for both unconstrained optimization and nonlinear equations)

ii.

Quasi-Newton methods (esp. BFGS)

iii.

Globalization techniques

a.

Line search

b.

Trust region

(d)

Algorithms for constrained optimization

i.

The quadratic penalty method for equality constrained optimization

ii.

The augmented Lagrangian method for equality constrained optimization

iii.

The logarithmic barrier method for inequality constrained optimization

Note: The test primarily covers unconstrained optimization. The coverage of constrained optimization is limited to (i) optimality conditions; (ii) methods, such as penalty and barrier methods and the augmented Lagrangian method, that reduce the problem to a sequence of unconstrained optimization problems.

(e)

Convergence theory

i.

Local convergence of Newton's method

ii.

Global convergence of Newton's method

a.

with line search

b.

with trust region

iii.

Local convergence of penalty and augmented Lagrangian methods for equality-constrained optimization

iv.

Local convergence of logarithmic barrier method for inequality constrained optimization

2.

Numerical Linear Algebra

(a)

Fundamentals

i.

Vector and matrix norms

a.

Definition of common vector norms

b.

Definition of induced matrix norm

c.

Computation of the matrix norms induced by the $\ell^1$, $\ell^2$, and $\ell^{\infty}$ vector norms.

ii.

Stability and backwards error analysis

(b)

Solving a system of linear equations

i.

Gaussian elimination

a.

partial pivoting

b.

complete pivoting

c.

stability of Gaussian elimination with partial or complete pivoting

ii.

Gaussian elimination and the LU factorization

iii.

Special classes of matrices:

a.

Symmetric positive definite matrices and the Cholesky factorization

b.

Diagonally dominant matrices

iv.

The condition number of A:

a.

when solving Ax=b and b is regarded as data (A is known exactly);

b.

when solving Ax=b and both A and b are regarded as data.

(c)

Least-square problems

i.

The projection theorem; orthogonal projectors

ii.

The normal equations

a.

Derivation

b.

Condition number of A^TA

iii.

The QR factorization

a.

Solving the least-squares problem via the QR factorization

b.

Computation of the QR factorization using Householder transformations

c.

Advantage of QR method over the normal equations method

iv.

The SVD

a.

Solving the least-squares problem via the SVD

b.

(Note: Algorithms for computing the SVD are not covered on this examination.)

(d)

Eigenvalue problems

i.

Computing eigenvalues/eigenvectors via:

a.

The characteristic polynomial

• Why we cannot find eigenvalues by computing the roots of the characteristic polynomial
• Why no finite algorithm for computing the eigenvalues of a general matrix can exist

b.

The power method, inverse power method, and shifted inverse power method

c.

The QR algorithm

• The basic algorithm and why it works (relationship to simultaneous iteration and the power method)
• Accelerating the algorithm using shifts
• Reduction to upper Hessenberg form for efficiency

(e)

Miscellaneous

i.

Computing the numerical rank of a matrix via the SVD

ii.

Computing the condition number of a matrix via the SVD