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 34: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 QuasiNewton methods; Line Search methods
 Standard formulations of constrained optimization: Linear, Quadratic, Conic and SemiDefinite Programming
 KKT optimality conditions
 Lagrangian duality, constraint qualification, weak and strong duality
 Fenchel conjugacy and its relationship to Lagrangian duality
 Multiobjective optimization
 Equality constrained Newton method
 Log Barrier (Central Path) methods, and PrimalDual 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.
 Largescale 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 biweekly 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 subgradients as linear lower bounds
 Operating and supporting hyperplanes
Required Reading: Boyd and Vandenberghe Sections
2.12.3,2.5,3.13.3
Homework 1 out (due April 12th)
 Lecture I: Thursday April 1st

 Formulation of Optimization Problems
 Convex and NonConvex Optimization Problems
 Feasibility, Optimality, Suboptimality
 Unconstrained Optimization: Optimality Condition
Boyd and Vandenberghe Sections 1.11.4,4.14.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.19.3,9.5
 Lecture III: Thursday April 8th

 Analyzis of Newton's Method
 SelfConcordence analyzis and Newton's Method
 Conjugate Gradient Descent
 QuasiNewton Methods: BFGS
 Summary of Unconstrained Optimization
Boyd and Vandenberghe Sections 9.59.6; Bertsekas Sections 1.61.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.24.3,5.1,5.2,5.4,5.5.1
 Lecture V: Thursday April 15th

 Dual solutions as certificates for suboptimality and infeasibility
 Geometric interpretation of duality; Slater's condition (Section 5.3)
 Dual of a linear program
 Dual of a nonconvex problem: maxcut clustering
 Dual of leastsquares solution to underdetermined linear system
 Lecture VI: Tuesday April 20th

 Leastsquares solution: recovering the primal optimum from the dual optimum
 Complimentary slackness (5.5.2)
 Example: Maxflow/mincut
 KKT conditions (5.5.3)
 Examples: waterfiling (Boyd and Vandenberghe Example 5.2), largemargin 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 logdet function.
 Lecture VIII: Tuesday April 27th

 Matrix inequalities, semidefinite constraints, and semidefinite programming (Section 4.6)
 Examples: covariance estimation, fastest mixing Markov chain, embedding problems.
 Goemans and Williamson Maxcut SDP relaxation.
 Lagrangian duality for semidefinite constraints (Section 5.9)
 Lecture IX: Thursday April 29th

 Complimentary slackness and KKT optimality conditions for semidefinite constraints (Section 5.9)
 Normconstrained matrix factorization as an example of an SDP and its dual.
 Equality constrained Newton's method (10.110.2).
 Lecture X: Tuesday May 4th

 Optimization of problems with implicit constraints
 Logbarrier problems and the central path interior point method (Sections 11.1, 11.2, 11.3.1)
 Analysis of the logbarrier central path method (11.5)
 Logbarrier method for semidefinite 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.
 Logbarrier and weakened KKT conditions (10.3.4).
 PrimalDual Interior Point Methods, including infeasible start (11.7).
 Lecture XII: Tuesday May 11th

 Multiobjective 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: centerofmass method, oracle lower bound, the Eillipsoid method (Chapters 13 of Nemirovksi's "Efficient Methods in Convex Programming").
 Lecture XIV: Tuesday May 18th

 Review and limitations of methods with polynomial convergence.
 Largescale, slowly converging, first order methods.
 Subgradient 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 subgradient descent, stepsize 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