EE546 index

EE546, Frontiers in Optimization: Convex Optimization Algorithms

Instructors: Maryam Fazel (UWEE) and Lin Xiao (Microsoft Research)
Spring 2012

Modern large-scale convex optimization algorithms have had an immense impact in areas including machine learning, signal processing, and engineering design. The objectives of this course are to

  • Develop working experience of practical optimization algorithms along with their complexity analysis
  • Introduce the methodology of structural convex optimization, and develop the capability of designing customized algorithms by exploiting problem structure
  • Expose students to research frontiers in convex optimization and its applications

Lecture notes

1. Introduction

Smooth optimization:
2. Gradient methods
3. Optimal methods

Non-smooth optimization:
4. Subgradients
5. Subgradient methods

Proximal gradient methods:
6. Proximal mapping
7. Proximal gradient methods
8. Smoothing

Decomposition and coordinate descent:
9. Dual decomposition and dual algorithms
10. Augmented Lagrangian, alternating direction multiplier method
11. Coordinate descent method

12. Stochastic and online optimization

Interior-point methods:
13. Newton's method, self-concordant analysis
14. Interior-point methods

15. Cutting plane methods

16. Conclusions


Homeworks

There will be two homework sets, focusing on implementation (in Matlab) and insights into algorithms discussed in class.

Click here to submit HW files to the Dropbox.

Here is a helpful Matlab tutorial, including object oriented features: Yagtom

Homework 1: assigned 4/9, due 4/18. (pdf file) (matlab files). Solutions have been posted on the dropbox (click on HW 1 link).
Homework 2: assigned 4/25, due 5/7. Files are in the Dropbox.


Course project

Projects can be done individually or in groups of 2. Project types can be:
  • novel applications and modeling, solution with standard algorithms
  • extensive study of particular algorithms: survey, comparison, extensions
Project timeline: proposal due: April 25; presentations: May 21,23,30; final report due: June 4
Project proposal: 2 pages, including description of topic and problem to be explored and relevant references. Due 4/25.
Project presentations: Please email us by 5/9 to sign up for a 20 minute time slot (15 min talk, 5 min questions) on one of these 3 class days: May 21, 23, or 30.


Course information

Credit: 3 units
Lectures: Mondays and Wednesdays, 1:30-2:50pm, Savery Hall room 166.

Instructors:

  • Maryam Fazel, office: Paul Allen Center, Room CSE 230.
  • Lin Xiao, office: TBD

    Instructors' office hourse: Wednesdays 3-5pm (or Mondays by appointment)

    Prerequisites: EE 578 (Convex optimization) or Math 516 (Numerical Optimization), or consent of the instructors.

    Course requirements:

  • Homeworks: 2 homework sets (mainly algorithm implementation)
  • Final project: project proposal, in-class presentation, and final report

  • Grading: homeworks 30%, final project 70%.


    References

    The lectures notes are largely based on the following books, and on the lectures notes of Lieven Vandenberghe for EE236C at UCLA, and Stephen Boyd for EE364B at Stanford University.