Numerical Optimization<br> (Advanced Topics in Numerical Analysis)

Numerical Optimization

G22.2750-001, G63.2012-002

New York University
Spring Semester 2011

Instructor: Margaret Wright, mhw@cs.nyu.edu

Office: Warren Weaver Hall (CIWW), Room 430

Office Hours: Tues 3:30-5:00pm, Wed 1:00-2:00pm, or by appointment

Class meetings: Tues, 5:10-7:00pm, in CIWW 312.
Last day of class: Tuesday, May 3.
Final project due: Wednesday, May 11.

Course Description

A large number---arguably the majority---of problems in science, engineering, medicine, and business involve optimization problems in which we seek to minimize or maximize an ``objective function'' subject to constraints. This course will survey widely used methods for continuous optimization, focusing on both theoretical foundations and implementation as numerical software. Topics include linear programming (optimization of a linear function subject to linear constraints), line search and trust region methods for unconstrained optimization, and a selection of approaches (including active-set, sequential quadratic programming, and interior methods) for constrained optimization.

Coursework

The course requirements include class attendance, written and programming homework assignments, and a course project. All of these will count in your final grade. The final grade will be calculated by averaging the two elements (homework and project) with weights of 60% and 40%, where the weighting will be chosen for each student to maximize his/her grade.

Prerequisites

Linear algebra, multivariate calculus, and (preferably) experience in programming in Matlab. Students without all elements of this background should check with the instructor for permission to take the class.

Textbook

Numerical Optimization, Jorge Nocedal and Stephen Wright, Springer-Verlag, second edition. Other material will be passed out as notes.

Programming

The instructor will use Matlab, an interactive software package and programming environment, for her own programs. If you prefer another language, this is fine as long as your code is intelligible. Matlab is a product of the Mathworks; a student version costs around $100 at the Computer Store, or you can use Matlab in a Courant computer lab. (You will need a CIMS account.) You can use Matlab remotely, with a few (solvable) complications if you wish to use its graphics capabilities. Matlab tutorials are available online from several sites, such as one at the University of Maine

Course Project

Each student is expected to choose and complete an individual project to demonstrate his/her creativity and mastery of important concepts of numerical optimization. Projects are due on Wednesday, May 11, 2011. The topic for each project must be approved in advance by the instructor following an individual meeting with the student and a short ``prospectus'' submitted by the student. Project List.

Homework

HW1, due February 15, 2011
HW2, due March 8, 2011
HW3, due March 22, 2011
HW4, due April 12, 2011
Homeworks may be submitted in written form or via email. They must be in the instructor's possession by 5pm on the due date. Without explicit permission from the instructor in advance, late homework will be marked down by 30% for every day of lateness.

Lectures

January 25. Course overview. Linear programming.
Chapter 13 of textbook.
February 1. Feasible descent directions. Optimality conditions.
Farkas' Lemma.
February 8. Simplex method for all-inequality form.
First homework assignment (HW1), due February 15.
February 15. Simplex method for all-inequality form.
Linear algebra issues; updating the LU factors.
February 22. Simplex method for standard form. Duality.
Second homework assignment (HW2), due March 8.
March 1. Systems of nonlinear equations.
Newton's method. Chapter 11 of textbook.
Interior methods for LP. Chapter 14 of textbook.
March 8. Short revisit of Newton's method for nonlinear equations and primal-dual interior LP methods.
Introduction to unconstrained optimization.
Chapters 2 and 3 of textbook.
Third homework assignment (HW3), due March 22.
List of possible projects handed out.
March 15. No class (spring break).
March 22. Local models in unconstrained optimization.
Introduction to line search and trust region methods.
Choosing the step length. Backtracking. The Wolfe conditions.
Steepest descent.
March 29. Steepest descent and its rate of convergence.
Newton's method for unconstrained optimization.
Modified Newton methods based on eigensystem, Cholesky, and symmetric indefinite factorizations.
Fourth homework assignment (HW4), due April 12.
Chapters 3,4, and 6 of textbook.
April 5. Quasi-Newton methods.
Implementation of quasi-Newton methods.
Gradient-related search directions.
Convergence of line search methods.
Chapter 8 of textbook.
April 12. Equality-constrained quadratic programming.
KKT systems.
Introduction to inequality-constrained quadratic programming.
April 19. Active-set methods for inequality-constrained quadratic programming.
Linearly constrained optimization of a nonlinear function.
Introduction to nonlinear equality constraints.
Chapter 12 of textbook.