Official Course Description
Spring 2005, Thursdays, 1:25-3:15, WWH Room 613
Instructor: Michael L. Overton
Nonlinear optimization problems arise in many different application areas.
The goal is to minimize some function, such as cost or energy,
often subject to constraints on the variables. This course presents
and analyzes numerical methods for solving nonlinear optimization problems,
together with the underlying mathematical theory on which they are based.
Programming projects, using Matlab and software libraries, will be assigned.
Topics covered include: Newton, quasi-Newton and conjugate gradient methods
for unconstrained optimization in both line search and trust region frameworks,
and penalty, barrier and successive quadratic programming methods for
Should you take this course?
The course lectures take place only once a week, and this means they will
move fast. The course is about nonlinear optimization which is a very
important practical tool but also has a rich mathematical theory. Hopefully,
if you like math and computing, you will like this class. On the other hand,
if your math background is weak, or you have no experience with computing,
you are likely to find it difficult. Don't hesitate to discuss these
issues with me, in my office or after class.
Undergraduate linear algebra and multivariable calculus (some key ideas are
summarized in the appendix of the text, see below), and experience with
writing computer programs (in any language).
- (Jan 20) Overview and introduction to line search methods.
- (Jan 27) Line Search Methods: global convergence via the Wolfe conditions,
and Zoutendijk's theorem. Convergence rate of steepest descent.
- (Feb 3) Convergence rate of Newton's method. Dennis-More theorem.
Implementation of Newton's method with a line search, need to check
indefiniteness. LDL' version of Cholesky factorization.
- (Feb 10) Modified Cholesky factorization. Linear conjugate gradient method.
- (Feb 17) Conjugate direction methods. The Newton-CG method. Nonlinear CG methods.
- (Feb 24) Global convergence of Fletcher-Reeves. Quasi-Newton methods.
- (Mar 3) Quasi-Newton methods, global convergence of BFGS
- (Mar 10) Theory of Constrained Optimization: the KKT Theorem
- (Mar 24) Proof of the KKT Theorem
- (Mar 31) Linear Programming and the Simplex Method
- (Apr 7) Primal-Dual Interior Point Algorithms for LP
- (Apr 14) Linear Algebra Details for LP Algorithms. Second-Order Optimality Conditions for Nonlinear Programming and the Inertia of the KKT Matrix.
- (Apr 21) Penalty, Augmented Lagrangiang and Primal Barrier Methods
for Nonlinear Programming.
- (Apr 28) Successive Quadratic Programming Methods for Nonlinear Programming.
NEW: INFO ON NEXT SEMESTER'S COURSE ON CONVEX AND NONSMOOTH OPTIMIZATION
- Homework 1, assigned Jan 27, due Feb 10
- Homework 2 (pdf), (ps),
assigned Feb 3, due Feb 17
- Homework 3 (pdf), (ps),
modified Cholesky code assigned Feb 14, due Feb 25(4 pm)
- Homework 4 (pdf), (ps),
limited-memory matrix-vector product code assigned Feb 21, due Mar 21
- Homework 5 (pdf), (ps),
assigned Apr 1, due Apr 8
- Homework 6 (pdf), (ps),
LP test examples, assigned Apr 11, due date changed to Apr 25
- Homework 7 (pdf), (ps),
assigned Apr 29, due May 3
Unless indicated otherwise, homework assignments are due at midnight
on the date indicated.
It is important that you do the homework yourself, but when you get stuck,
I encourage you to consult with other students, or the math computer
consultant, or me, to get help when necessary. However, when you get help,
it's important to acknowledge it in writing. Passing off other people's
work as your own is called plagiarism and is not acceptable.
Homework may be given to me in class or in my office, or left under my office door.
Please do not leave homework in my lobby mailbox or send it by email.
Please staple all pages together. Late homework will be penalized 20%.
Homework will not be accepted more than one week late, except in special circumstances.
Oral Final Exam:
25 minutes in my office, ideally Mon May 9, Tue May 10 or Wed May 11.
Please email me if you don't yet have an appointment.
The emphasis will be on what you did for the homework. Here are the
You choose one topic and I choose one, and we
will talk about what you learned about it. I will not choose the same
topic for all students. You do not have to
memorize complicated details, but you should be able to explain
the main ideas that we talked about in class and that you explored in
the homework. You are not expected to read details in the text that
we did not cover in class. In particular, I don't expect you to read
the last four chapters of the text that I just posted; they are in
very rough form and are posted "fyi".
- Line search methods and convergence via Zoutendijk's theorem
- Newton's Method: quadratic convergence and approaches to indefiniteness
- Conjugate gradient methods: linear and nonlinear
- Quasi-Newton methods: BFGS and limited-memory BFGS
- First and second order optimality conditions for nonlinear programming
- The simplex method for linear programming
- Primal-dual interior point methods for linear programming
- Methods for nonlinear programming
Nonlinear Optimization, by Nocedal and Wright.
For experimenting with our own optimization programs, Matlab is a good
choice. Matlab is an excellent environment for small-scale numerical
computing. However, its Optimization Toolbox is not very good.
See here for
an excellent up-to-date guide to optimization software.
Optimization problems can be submitted over the web to
Another great resource is the modeling language
Matlab is a product of The MathWorks.
You can order your own copy of
Matlab for $99
or you can use Matlab on the Courant Sparcstation network (or dial in from home).
For Matlab documentation, type "helpdesk" at the Matlab prompt. To get started,
A Free Matlab Online Tutorial or
or look for others by a web
search. You may want to look at a very outdated but still useful
Introductory Matlab Primer (3rd and last edition, postscript file).
There are many books on Matlab; I recommend
Matlab Guide, by
Higham and Higham, but you will find many other resources on the web,
including the latest information on Matlab 7.0.
Math Computer Consultant
There is a volunteer
Math Computer Consultant (email: firstname.lastname@example.org).
Please contact the consultant if you have trouble with the Courant
computer facilities or questions about the software we are using.
The consultant is there to help, but cannot debug programs for you.
Class Mailing List
Important: you must join the
class mailing list .
There are two steps to joining the list; the
first is to follow the instructions on the web page (including picking
a password), and the second is to REPLY TO the confirmation message sent
to you by the system. This list will be used for important announcements.
You can also send questions or comments to this list yourself (contact me
if you have questions about when this is appropriate). If you do not
want to use an NYU email address, be sure to notify me in person or by
email from an NYU address about your preferred address, so I can add it
to my spam filter.
If you don't have a Sun workstation account, please request one, even if you
plan to do most of the homework on your home computer. You might need it later,
depending on software requirements.
Request this account from petagna@cs if you are registered in CS
and from the math department if you are registered in math.
As an NYU graduate student you have the opportunity to join
SIAM for free. SIAM is the main professional
organization for applied and computational math, and offers a number of
benefits to members. I've been a member since I was a graduate student,
and have benefitted in many ways from my association with SIAM.
Don't Hesitate to Ask for Help
If you have questions, send me email, give me a call, or drop by my office.
Don't wait until it's too late!