(Advanced Topics in Numerical Analysis)
New York University
Spring Semester 2011
Instructor: Margaret Wright, firstname.lastname@example.org
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.
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.
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.
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.
Numerical Optimization, Jorge Nocedal and Stephen Wright,
Springer-Verlag, second edition.
Other material will be passed out as notes.
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
at the University of Maine
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.
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
Without explicit permission from the instructor in advance,
late homework will be marked down by 30% for every day of
||Course overview. Linear programming. |
Chapter 13 of textbook.
Feasible descent directions. Optimality conditions. |
||Simplex method for all-inequality form.|
First homework assignment (HW1), due February 15.
||Simplex method for all-inequality form.|
Linear algebra issues; updating the LU factors.
||Simplex method for standard form. Duality.|
Second homework assignment (HW2), due March 8.
||Systems of nonlinear equations.|
Newton's method. Chapter 11 of textbook.
Interior methods for LP. Chapter 14 of textbook.
||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.
||No class (spring break).|
||Local models in unconstrained optimization.|
Introduction to line search and trust region methods.
Choosing the step length. Backtracking. The Wolfe conditions.
||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.
Implementation of quasi-Newton methods.
Gradient-related search directions.
Convergence of line search methods.
Chapter 8 of textbook.
||Equality-constrained quadratic programming.|
Introduction to inequality-constrained quadratic programming.
||Active-set methods for inequality-constrained quadratic programming.|
Linearly constrained optimization of a nonlinear function.
Introduction to nonlinear equality constraints.
Chapter 12 of textbook.