CMSC 34500: Optimization
This is a webpage for the Spring 2010 course at TTIC and the University of Chicago (known as CMSC 34500 at the University).
Tuesdays and Thursdays 3-4:30pm at TTIC 530 (located at 6045 S. Kenwood Ave, fifth floor)
Lecturer: Nati Srebro.
TAs: Karthik Sridharan and Andy Cotter.
Homework Submissions: 
.
Course Description
The course will cover techniques in unconstrained and constrained
convex optimization and a practical introduction to convex duality.
The course will focus on (1) formulating and understanding convex
optimization problems and studying their properties; (2) presenting
and understanding optimization approaches; and (3) understanding the
dual problem. Limited theoretical analysis of convergence properties
of methods will be presented. Examples will be mostly from data
fitting, statistics and machine learning.
Specific Topics:
- Formalization of optimization problems
- Smooth unconstrained optimization: Gradient Descent, Conjugate Gradient Descent, Newton and Quasi-Newton methods; Line Search methods
- Standard formulations of constrained optimization: Linear, Quadratic, Conic and Semi-Definite Programming
- KKT optimality conditions
- Lagrangian duality, constraint qualification, weak and strong duality
- Fenchel conjugacy and its relationship to Lagrangian duality
- Multi-objective optimization
- Equality constrained Newton method
- Log Barrier (Central Path) methods, and Primal-Dual optimization methods
- Overview of the simplex method as an example of an active set method.
- Overview of the first order oracle model, subgradient and separation oracles, and the Ellipsoid algorithm.
- Large-scale subgradient methods: subgradient descent, mirror descent, stochastic subgradient descent.
Text Books
The required textbook for the class is:
The book is available online here. About 75% of the material covered
in the class can be found in the above book.
Supplemental recommended books:
Requirements and Grading:
There will be roughly bi-weekly homework assignments, counting
toward 30% of the grade. Assignments must be typed (not handwritten)
and submitted electronically in PDF. Collaborative work on the
homeworks is encouraged, but each student must eventually write up the
solution independently.
There will also be several MATLAB programming and experimentation
assignments, counting toward another 30% of the grade.
The remaining 40% of the grade will be based on a final exam.
Students may also choose to do an optional project, which could
replace some of the above requirements.
Lectures and Required Reading:
- Lecture 0: Tuesday March 30th
- (lecture by Ambuj Tewari)
- Convex functions and convex sets
- Gradients and sub-gradients as linear lower bounds
- Operating and supporting hyperplanes
Required Reading: Boyd and Vandenberghe Sections
2.1-2.3,2.5,3.1-3.3
Homework 1 out (due April 12th)
- Lecture I: Thursday April 1st
-
- Formulation of Optimization Problems
- Convex and Non-Convex Optimization Problems
- Feasibility, Optimality, Sub-optimality
- Unconstrained Optimization: Optimality Condition
Boyd and Vandenberghe Sections 1.1-1.4,4.1-4.2,9.1
- Lecture II: Tuesday April 6th
-
- Unconstrained Optimization: Descent Methods; Descent Direction
- Gradient Descent
- Line Search: Exact Line Search and Backtracking Line Search
- Analyzis of Gradient Descent with Exact and Backtracking Line Search
- Problems with badly conditioned functions; Preconditioning
- Newton's Method
Boyd and Vandenberghe Sections 9.1-9.3,9.5
- Lecture III: Thursday April 8th
-
- Analyzis of Newton's Method
- Self-Concordence analyzis and Newton's Method
- Conjugate Gradient Descent
- Quasi-Newton Methods: BFGS
- Summary of Unconstrained Optimization
Boyd and Vandenberghe Sections 9.5-9.6; Bertsekas Sections 1.6-1.7
Programming assignment 1 out (source code) (due May 3rd)
Written Assignment 1 (due April 26th)
- Lecture IV: Teusday April 13th
-
- Constrained Optimization: Formulation and Optimality Condition
- Linear Programming
- The Lagrangian, the dual problem, weak duality
- Slater's condition and strong duality
Boyd and Vandenberghe Sections 4.2-4.3,5.1,5.2,5.4,5.5.1
- Lecture V: Thursday April 15th
-
- Dual solutions as certificates for sub-optimality and infeasibility
- Geometric interpretation of duality; Slater's condition (Section 5.3)
- Dual of a linear program
- Dual of a non-convex problem: max-cut clustering
- Dual of least-squares solution to under-determined linear system
- Lecture VI: Tuesday April 20th
-
- Least-squares solution: recovering the primal optimum from the dual optimum
- Complimentary slackness (5.5.2)
- Example: Max-flow/min-cut
- KKT conditions (5.5.3)
- Examples: water-filing (Boyd and Vandenberghe Example 5.2), large-margin linear discrimination.
- Lecture VII: Thursday April 22nd
-
- Expressing the dual in terms of Fenchel conjugates (Section 3.3, 5.1.6, 5.7.1)
- Example: Logistic regression
- Minimum volume covering ellipsoid and the log-det function.
- Lecture VIII: Tuesday April 27th
-
- Matrix inequalities, semi-definite constraints, and semi-definite programming (Section 4.6)
- Examples: covariance estimation, fastest mixing Markov chain, embedding problems.
- Goemans and Williamson Max-cut SDP relaxation.
- Lagrangian duality for semi-definite constraints (Section 5.9)
- Lecture IX: Thursday April 29th
-
- Complimentary slackness and KKT optimality conditions for semi-definite constraints (Section 5.9)
- Norm-constrained matrix factorization as an example of an SDP and its dual.
- Equality constrained Newton's method (10.1-10.2).
- Lecture X: Tuesday May 4th
-
- Optimization of problems with implicit constraints
- Log-barrier problems and the central path interior point method (Sections 11.1, 11.2, 11.3.1)
- Analysis of the log-barrier central path method (11.5)
- Log-barrier method for semi-definite constraints (11.6).
- Lecture XI: Thursday May 6th
-
- Feasibility problems and Phase I methods (Sections 11.4.1, 11.4.3).
- Reducing Optimization to feasibility.
- Log-barrier and weakened KKT conditions (10.3.4).
- Primal-Dual Interior Point Methods, including infeasible start (11.7).
- Lecture XII: Tuesday May 11th
-
- Multi-objective problems and Pareto optimality (Boyd and Vandenberghe Section 4.7).
- The Simplex method (Nocedal and Wright Chapter 13).
- Lecture XIII: Thursday May 13th
-
- The first order oracle model: subgradients and seperation oracles.
- Classical first order methods: center-of-mass method, oracle lower bound, the Eillipsoid method (Chapters 1-3 of Nemirovksi's "Efficient Methods in Convex Programming").
- Lecture XIV: Tuesday May 18th
-
- Review and limitations of methods with polynomial convergence.
- Large-scale, slowly converging, first order methods.
- Sub-gradient descent with projection, step size and analysis for Lipschitz functions over a bounded domain (Section 5.3.1 of Nemirovksi's "Lectures on Modern Convex Optimization").
- Lecture XV: Thursday May 20th
-
- More about sub-gradient descent, step-size selection and constraints.
- Gradient descent as a proximal point method.
- From gradient descent to bundle methods (more information in Section 5.3.2 of Nemirovksi's "Lectures on Modern Convex Optimization").
- Mirror Descent formulation and basic concepts: strong convexity with respect to a norm, dual norm, distance generating function and Bergman divergence (Section 5.4.1 of Nemirovksi's "Lectures on Modern Convex Optimization").
- Lecture XVI: Tuesday May 25th
-
- Lecture XVII: Thursday May 27th
-
- Stochastic Gradient Descent and Stochastic Optimization. (Section 14.1 of Nemirovksi's "Efficient Methods in Convex Programming")
- Overview of further results for first order methods: robustness, faster rates with strong convexity, faster rates with smoothness, acceleration with smoothness.
- Lecture XVIII: Tuesday June 1st
-
Assignments:
Last modified: Tue Jun 01 01:46:24 Central Daylight Time 2010