Convex and Nonsmooth Optimization

• Office: WWH 429
• Telephone: 998-3121
• Office Hours: Tuesdays 4-5 pm (except Feb 20), 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, linear and semidefinite programming, CVX ("disciplined convex programming"), gradient and Newton methods, Nesterov's complexity bound, the alternating direction method of multipliers, the nuclear norm and matrix completion, 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: now available for free to NYU students

• 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)
• First-Order Methods in Optimization, by A. Beck, SIAM, 2017
• 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 (free download: access only with NYU netid)
  
• Steve Boyd's Lecture Notes and MOOC
• Lieven Vandenberghe's lecture notes
• Survey article on ADMM by Boyd et al

Lecture Plan (tentative)

• Jan 22: Overview (BV Ch 1), convex sets, including separating hyperplane and supporting hyperplane theorems (BV 2.1, 2.2, 2.3.1, 2.3.2, 2.5)
• Jan 29: Convex cones (BV 2.6.1), convex functions (BV 3.1 except 3.1.6, 3.1.8; BV 3.2 (except 3.2.4, 3.2.6); introduction to CVX (disciplined convex programming)
• Feb 5: Duality (BV 5.1, 5.2, 5.3) (skipping conjugate functions for now)
• Feb 12: Linear and semidefinite programming duality (notes), complementarity and KKT conditions, a saddle point theorem (BV 5.4, 5.5, 5.9)
• Feb 19: no class (presidents' day)
• Feb 26: Gradient and Newton Methods (Ch 9, BV) (Gradient method notes), (Newton method notes)
• Mar 5: Nesterov's complexity bounds (summary notes on gradient descent, notes on complexity bounds)
• Mar 12: no class (spring break)
• Mar 19: Conjugate function (BV 3.3), subgradients and subdifferential (notes), Alternating Direction Method of Multipliers (ADMM) (annotated copy of ADMM paper)
• Mar 26 ADMM, continued
• Apr 2: Nuclear norm characterization via SDP duality and matrix completion via nuclear norm minimization (notes, annotated copy of article by Recht, Fazel, Parrilo)
• Apr 9: Extn of Newton's method to linear equality constraints (Ch 10, BV), primal interior point method for convex inequality constraints (Ch 11, BV)
• Apr 16: Primal-dual interior point methods for linear and semidefinite programming
• Apr 23: Nonconvex optimization: regular subgradients, (general) subgradients, regularity, Clarke subgradients, sharp minimizers (notes)
• Apr 30: Algorithms for smooth nonconvex optimization: Newton's method, Armijo-Wolfe line search, Zoutenijk's theorem, BFGS, linear and nonlinear conjugate gradient methods (notes, notes on linear CG method)
• May 7: Algorithms for nonsmooth nonconvex optimization: gradient sampling, BFGS (slides)
• May 14: In-class final exam or final project due

Requirements
Attend class, submit all homeworks, and either write the final exam on May 14 (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 16. Project due date: May 14. Final grade will be based approximately 60% on the homework and 40% on the final project or final exam.

Homework

• HW 1, assigned Jan 22, due Jan 29 at midnight
• HW 2, assigned Jan 30, due Feb 6 at midnight
• HW 3, assigned Feb 5, due Feb 13 at midnight
• HW 4, assigned Feb 12, deadline postponed to Mar 5 at midnight, (latex source, if you want you can use this as a template for your solution)
• HW 5, assigned Mar 5, due Mar 19 at midnight
• HW 6, assigned Mar 22, due Apr 2 at midnight
• HW 7, assigned Apr 2, due Apr 12 at midnight
• HW 8, assigned Apr 9, due Apr 23 at midnight
• HW 9, assigned Apr 23, due May 3 at midnight, (latex source, if you want you can use this as a template for your solution)