Advanced Numerical Optimization

CMSC764 / AMSC604 - Spring 2017

This is a detailed survey of optimization from both a computational and theoretical perspective. Special emphasis will be put on scalable methods with applications in machine learning, model fitting, and image processing. There are no formal pre-requisites for this course, however students should have a strong background in applied mathematics (especially linear algebra) and computer programming.
Theoretical topics will include convex analysis, duality, rates of convergence, and advanced topics in linear algebra. Computational topics will include gradient methods, splitting methods, interior point methods, linear programming, and methods for large matrices. Homework assignments will require both mathematical work on paper and implementation of algorithms.

The basics

   
When: TuTh 11:00pm - 12:15pm       Where: CSI 3120
Instructor: Tom Goldstein Office Hours: Th 1-2pm, AVW π 3141
TA: Hao Li Office Hours: Mon 10-12, AVW 4431

Final Exam: Sat, May 13 @ 8am (tentative)

Coursework & grading

Homework will be assigned approximately once per week. Homework assignments will consist of both programming exercises and theoretical problem sets. Programming assignments will be cumulative - you will need the results of early assignments to complete assignments that are given later in the course. The completed homework assignments you turn in must represent your own work.

You may complete your assignments in either Matlab or Python 2.7. Other languages (including Python 3+) will not be allowed. When programming assignments are given, you will be required to prepare a short pdf document containing outputs from your code, and this pdf will be turned in with your code.

The approximate grade breakdown of the course will be

  • 50% homework
  • 25% midterm exam
  • 25% final exam.

Note: This is a PhD qualifying course for computer science.

Homework

Homework will be turned in using Elms/Canvas. Follow this link to Elms, and then look for the course page after logging in. I recommend generating your pdf using latex. Have a look at these example solutions, and the corresponding latex source.

Homework 1: linear algebra basics (Due Feb 7)

Homework 2: FFT & and optimization test problems (Due Feb 14)
Homework 3: gradients (Due Feb 22)
Homework 4: backprop (Due Feb 28)

Homework 5: numerical linear algebra (Due Mar 8)

Homework 6: convex functions (Due Mar 14)

Homework 7: gradient methods (Due April 14)

Homework 8: duality (Due April 26)

Homework 9: prox methods (Due May 3)

Homework 10: ADMM (Due May 10)

Lecture Slides

Course Overview
Linear Algebra Review
Optimization Problems
TV, FFT, and Calculus
Quadratic Forms
Convex Functions
Gradient Methods
Quasi-Newton Methods
Duality
Proximal Methods
Lagrangian Methods
Random topics | MCMC code example

Book & Other Sources

All course materials are available for free online. Suggested reading material for various topics includes: