Description

The main algorithms and software for constrained optimization, emphasizing the sparse-matrix methods needed for their implementation. Iterative methods for linear equations and least squares. Interior methods. The simplex method. Basis factorization and updates. The reduced-gradient method, augmented Lagrangian methods, and SQP methods.

3 units, Spring (Michael Saunders), Grading basis ABCD/NP

Prerequisites: Basic numerical linear algebra, including LU, QR, and SVD factorizations, and an interest in MATLAB, sparse-matrix methods, and gradient-based algorithms for constrained optimization

Homework, etc

There will be 4 or 5 homework assignments and one somewhat more challenging project. MATLAB is used for computational exercises.

• 2007 project: Experiments with LSQR on least-squares problems, using sparse LU factors to construct a preconditioner.
• 2008 project: Experiments with many direct methods for solving sparse least-squares problems.
• 2009 project: GAMS and Basis Pursuit
• 2010 project: Again, something to do with sparse matrices and optimization.

Grades will be assessed from the homework and project. There will be no final exam.

There is no text book for the class. The "References" link is background reading and a reminder of some of the sources out there.

Location

• Building 540, Room 103
• Mon Wed Fri 2:15-3:30pm
• First class: Mon March 29
• Last class: Wed June 2

Auditors are welcome