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
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
There will be 4 or 5 homework assignments and one somewhat more
challenging project. MATLAB is used for computational exercises.
Grades will be assessed from the homework and project.
There will be no final exam.
- 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.
There is no text book for the class. The "References" link
is background reading and a reminder of some of the sources out there.
Auditors are welcome