Nonlinear Optimization

G22.2750/G63.2031
Spring 2005, Thursdays, 1:25-3:15, WWH Room 613
Instructor: Michael L. Overton

  • Coordinates
  • Official Course Description
    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.

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

  • Prerequisites
    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).

  • Lectures
    1. (Jan 20) Overview and introduction to line search methods.
    2. (Jan 27) Line Search Methods: global convergence via the Wolfe conditions, and Zoutendijk's theorem. Convergence rate of steepest descent.
    3. (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.
    4. (Feb 10) Modified Cholesky factorization. Linear conjugate gradient method.
    5. (Feb 17) Conjugate direction methods. The Newton-CG method. Nonlinear CG methods.
    6. (Feb 24) Global convergence of Fletcher-Reeves. Quasi-Newton methods.
    7. (Mar 3) Quasi-Newton methods, global convergence of BFGS
    8. (Mar 10) Theory of Constrained Optimization: the KKT Theorem
    9. (Mar 24) Proof of the KKT Theorem
    10. (Mar 31) Linear Programming and the Simplex Method
    11. (Apr 7) Primal-Dual Interior Point Algorithms for LP
    12. (Apr 14) Linear Algebra Details for LP Algorithms. Second-Order Optimality Conditions for Nonlinear Programming and the Inertia of the KKT Matrix.
    13. (Apr 21) Penalty, Augmented Lagrangiang and Primal Barrier Methods for Nonlinear Programming.
    14. (Apr 28) Successive Quadratic Programming Methods for Nonlinear Programming.
  • Homework
  • NEW: INFO ON NEXT SEMESTER'S COURSE ON CONVEX AND NONSMOOTH OPTIMIZATION

    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 topics.
    1. Line search methods and convergence via Zoutendijk's theorem
    2. Newton's Method: quadratic convergence and approaches to indefiniteness
    3. Conjugate gradient methods: linear and nonlinear
    4. Quasi-Newton methods: BFGS and limited-memory BFGS
    5. First and second order optimality conditions for nonlinear programming
    6. The simplex method for linear programming
    7. Primal-dual interior point methods for linear programming
    8. Methods for nonlinear programming
    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".

  • Text Book
    Nonlinear Optimization, by Nocedal and Wright.

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

  • Math Computer Consultant
    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.

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

  • Sun Account
    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.

  • SIAM
    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!