Spring 2005, Thursdays, 1:25-3:15, WWH Room 613

Instructor: Michael L. Overton

- Office: WWH 529
- Telephone: 998-3121
- Office Hours: Drop by any time except just before class, or send email or call for appointment
- Email: information on my address and spam filtering.

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 nonlinear programming.

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.

- 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.

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 topics.

- 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 NEOS. Another great resource is the modeling language AMPL.

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, try out A Free Matlab Online Tutorial or Another Tuturial 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.

There is a volunteer Math Computer Consultant (email: mconsult@cims.nyu.edu). 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.

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.

If you have questions, send me email, give me a call, or drop by my office. Don't wait until it's too late!