Convex and Nonsmooth Optimization

• Office: WWH 429
• Telephone: 998-3121
• Office Hours: Tuesdays 4-5 pm (except Jan 26 and Feb 9), or send email for an appointment, or try dropping by any time
• Email: overton AT cs.nyu.edu

Course Description

Convex optimization problems have many important properties, including a powerful duality theory and the property that any local minimum is also a global minimum. Nonsmooth optimization refers to minimization of functions that are not necessarily convex, usually locally Lipschitz, and typically not differentiable at their minimizers. Topics in convex optimization that will be covered include duality, CVX ("disciplined convex programming"), gradient and Newton methods, Nesterov's optimal gradient method, the alternating direction method of multipliers, the primal barrier method, primal-dual interior-point methods for linear and semidefinite programs. Topics in nonsmooth optimization that will be covered include subgradients and subdifferentials, Clarke regularity, and algorithms, including gradient sampling and BFGS, for nonsmooth, nonconvex optimization. Homework will be assigned, both mathematical and computational. Students may submit a final project on a pre-approved topic or take a written final exam.

Prerequisites

Undergraduate linear algebra and multivariable calculus

Required Text Book for first part of course

• Convex Optimization, by S. Boyd and L. Vandenberghe (BV), Cambridge University Press, 2004 (free download)

• MATLAB (free using Courant workstation, $49 for student download)
• CVX (free download)
• (You could try using Octave instead of MATLAB for most things, but CVX is not fully supported on Octave.)

• Numerical Optimization, by J. Nocedal and S.J. Wright, Springer, 2006 (free download)
• Primal-Dual Interior-Point Methods, by S.J. Wright, SIAM, 1997
• Introductory Lectures in Convex Optimization, by Y. Nesterov, Springer, 2004 (free download)
• Convex Analysis and Nonlinear Optimization, by J.M. Borwein and A.S. Lewis, Springer, 2006 (free download)
• Variational Analysis, by R.T. Rockafellar and R.J.-B. Wets, Springer, 1998 (free download from author's website)
• Lectures on Modern Convex Optimization - Analysis, Algorithms and Engineering Applications, by A. Ben-Tal and A. Nemirovski, SIAM, 2001
• Numerical Computing with IEEE Floating Point Arithmetic, by M.L. Overton, SIAM, 2001
• Steve Boyd's Lecture Notes and MOOC
• Lieven Vandenberghe's lecture notes
• Survey article on ADMM by Boyd et al

Lectures

• Jan 25: Overview (Ch 1, BV), Convex sets, including convex cones (Ch 2, BV)
• Feb 1: Convex functions (Ch 3, BV), Convex optimization problems (Ch 4, BV), introduction to CVX (disciplined convex programming)
• Feb 8: no class (instructor out of town)
• FRIDAY Feb 19, 4-6 pm: Duality (Ch 5, BV)
• Feb 22: Strong Duality (Ch 5, BV)
• Feb 29: Gradient and Newton Methods(Ch 9, BV)
• Mar 7: Nesterov's Optimal Methods (my notes on Nesterov's Chapter 2)
• Mar 14: no class (spring break)
• Mar 21: Subgradients and Subdifferential (notes), Alternating Direction Method of Multipliers (ADMM)(survey article by Boyd et al marked with my notes, proxabs.m)
• Mar 28 ADMM, continued (convergence proof by Boyd et al marked with my notes)
• Apr 4: Nuclear Norm Minimization and Semidefinite Programming, Matrix Completion (notes based on paper by Recht, Fazel and Parrilo)
• Apr 11: Primal Interior Point Method for Convex Inequality Constraints (Ch 11, BV)
• Apr 18: Primal-Dual Interior Point Methods for Linear and Semidefinite Programming (my notes) (see also Steve Wright's book, above)
• Apr 25: Nonconvex Optimization: regular subgradients, (general) subgradients, regularity, Clarke subgradients, sharp minimizers (notes)
• May 2: Algorithms for smooth nonconvex optimization: Newton's method, Armijo-Wolfe line search, Zoutenijk's Theorem, BFGS, nonlinear conjugate gradient method (notes)(see also Nocedal and Wright's book, above)
• May 9: Algorithms for nonsmooth nonconvex optimization: gradient sampling, BFGS, examples (slides)
• May 16: In-class final exam or final project due

Homework

• Homework 1, assigned Mon Jan 25, due Fri Feb 5
• Homework 2, assigned Mon Feb 1, due Fri Feb 19
• Homework 3, assigned Fri Feb 19, due Fri Feb 26
• Homework 4, assigned Mon Feb 29, due Thu Mar 10
• Homework 5, assigned Mon Mar 7, due Tue Mar 22
• Homework 6, assigned Mon Mar 21, due Fri Apr 1
• Homework 7, assigned Mon Apr 4, due Thu Apr 14
• Homework 8, assigned Mon Apr 11, due Thu Apr 21
• Homework 9, assigned Mon Apr 25, due Thu May 5

Requirements
Attend class, submit all homeworks, and either write the final exam on May 16 (which will be primarily based on material covered in the homework assignments), or submit a singly-authored final project on a topic that is pre-approved by the instructor. Approval due date: Apr 19. Project due date: May 16. Final grade will be based approximately 50% on the homework and 50% on the final project or final exam.

Class Mailing List
If you are not already a member of the class mailing list, please join the list. (Please join the list if you are planning to attend the class, whether or not you are taking it for credit.) 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).

Another Class Offered This Semester
You may want to consider also taking Professor Carlos Fernandez-Granda's class Optimization-Based Data Analysis. The topics covered by the two courses are quite complementary.

Another Class Offered Next Semester
You may want to consider also taking Professor Margaret Wright's class Numerical Optimization. Again the topics covered by her class are quite complementary to the topics in my class.