MS&E 318/CME 338: Large-Scale Numerical Optimization

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: Generalized least squares.

• 2011 project: A Lasso solver.

• 2012 project: Experiments with LU preconditioning of LSMR for sparse least-squares problems.

Grades will be assessed from the homework () and project (). There is no mid-term or final exam.

There is no text book for the class. See ‘‘references’’ for background reading and a reminder of some of the sources out there. See ‘‘notes’’ for the topics to be covered in turn.

Location

Math Corner (Building 380) Room 380-X
Mon Wed Fri 2:15–3:30pm

First class: Mon April 1
Last class: Wed June 5

Auditors are welcome

Office hours

Instructor: Prof Saunders, Huang M03
Mondays 3:30–4:00pm (after class, before ICME colloquium),
Wednesdays and Fridays 3:30–4:30pm (after class)

Course Assistant: Tomas Tinoco De Rubira
Tuesdays and Thursdays 2:30–3:30pm, 540-103