Information

Course Description and Syllabus

This course will provide a thorough background on computational methods for the solution of linear and nonlinear optimization problems. Particular attention will be given to the description and analysis of methods that can be used to solve practical problems. Although the focus is on methods, it is necessary to learn the theoretical properties of the problem and of the algorithms designed to solve it. The general problem addressed may be written as:

where x is an n-vector, c(x) is an m-vector, and F(x) and the elements of c(x) are twice continuously differentiable scalar functions. Smoothness in the functions is critical to the methods described in this course. However, methods to solve this class of optimization problem are critical in solving non-smooth problems and also optimal control problems. The associated problem of solving systems of nonlinear equations is covered in the course.

The flow of the course is to start with problems in one variable and then progressively introduce more complexity in the following manner:

• Unconstrained nonlinear problems
• Linear equality constrained problems
• Linear inequality constrained problems
• Nonlinear equality constrained problems
• Nonlinear inequality constrained problems

Within each of these categories, problem-specific subclasses will also be described. For example, when covering methods for unconstrained optimization we shall also describe special methods for the problem of nonlinear least squares (very common in finding the parameters in modeling) and methods of solving systems of nonlinear equations. Similarly, linear and quadratic programming will be covered in methods for linear inequality constrained problems.

Aspects covered for all categories of problems include derivation of the optimality conditions, proof of global convergence, and asymptotic rate of convergence.

Methods covered may all be viewed as variants or generalizations of Newton's method. We shall need to describe the methods in detail and that leads to careful attention to precisely how the numerical linear algebra operations are performed.

This leads among other things to describing how to update matrix factorizations.

Specific methods covered include:

• Linesearch methods
• Trust-region methods
• Newton's method
• Modified Newton's methods
• Quasi-Newton methods
• The linear and nonlinear conjugate gradient methods
• The Simplex method
• Penalty function methods
• Barrier function methods
• Augmented Lagrangian methods
• Sequential linearly constrained methods
• Sequential quadratic programming methods