NUMERICAL OPTIMIZATION

Computer Science CSCI-GA.2945-002

Mathematics MATH-GA.2011-002

New York University
Fall Semester 2012

Class meetings: Tuesday, 5:10-7:00pm
Warren Weaver Hall (CIWW), Room 317

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

Office: Warren Weaver Hall (CIWW), Room 430

Office Hours: Tues 3:30-5:00pm or by appointment

Description of Course Content

A large number---one could even argue 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.

The course will consider both (i) mathematical analysis of the theoretical properties of optimization problems (such as optimality conditions) and methods (such as convergence); and (ii) numerical issues, such as how to compute the solutions of associated subproblems efficiently and stably.

Textbook

Numerical Optimization, Jorge Nocedal and Stephen Wright, second edition, Springer-Verlag, 2006.

Other material will be passed out as notes.

Coursework

The course requirements include class attendance, written and programming homework assignments, an in-class midterm, and a course project. All of these will count in your final grade.

For students who took the midterm, the final grade will be calculated via a weighted sum of three elements (homework, midterm, project), with weights of 40%, 35%, and 25%, where the weight for each element will be chosen for each student to maximize his/her grade. For students who were unable to take the midterm, the final grade will be calculated via a weighted sum of two elements (homework and project) with weights of 60% and 40%, where the weight for each element will be chosen for each student to maximize his/her grade.

Homework

HW1, due September 11, 2012.
HW2, due September 18, 2012.
HW3, due September 25, 2012.
HW4, due October 2, 2012.
HW5, due October 10, 2012.
HW6, due November 14, 2012.
HW7, due November 21, 2012.
HW8, due December 9, 2012.
Homeworks may be submitted in written form or via email. They must be in the instructor's possession before midnight 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.

Handouts

Handout 1.
Handout 2.
Handout 3.
Handout 5.
Handout 6.

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.

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.

Midterm

There will be an in-class, closed-book midterm during the first hour of the class period on Tuesday, October 23.

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. Course projects are due in electronic form by 11:59pm on December 14, 2012. Details about the project requirement, including deadlines and a list of possible projects, are given at Project information.
Looking at projects from earlier classes may be helpful in illustrating form and content. Two excellent projects from previous courses are from an earlier Numerical Optimization course and from an earlier Numerical Computing course.