EE546 index

EE546, Special Topics: Convex Optimization Algorithms

Instructor: Maryam Fazel
Spring 2014

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
  • Discuss structural convex optimization, to develop the capability of designing customized algorithms by exploiting problem structure
  • Expose students to research frontiers in convex optimization and its applications

Achnowledgement: Course material prepared in collaboration with Dr. Lin Xiao, Researcher at Microsoft Research, Redmond, WA.


Announcements

  • Project presentations in the week of June 2: see project section for the schedule. Class will start slightly earlier on 6/2 and 6/4.
  • Reza Eghbali will be teaching in the week of May 19th. He will also hold office hours on Wed May 21 at the usual time, 3-4:55pm, in room EEB 258.
  • HW 2 is assigned, due 5/23. See HW section for details.
  • Some inetresting seminars/workshops at UW related to Optimization:


Lecture notes

1. Introduction

Smooth optimization:
2. Gradient methods
3. Optimal gradient methods

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

6. Stochastic and online optimization (guest lecture by Dr. Lin Xiao)

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

Decomposition and coordinate descent:
9. Dual decomposition and dual algorithms
10. Augmented Lagrangian, alternating direction multiplier method
11. Smoothing methods
12. Coordinate descent method (guest lecture by Dr. Lin Xiao)

Interior-point methods:
13. Newton's method, self-concordant analysis (guest lecture by Reza Eghbali)
14. Interior-point methods (guest lecture by Reza Eghbali)

15. Conclusions


Homeworks

There will be two homework sets, including some theory, but with more focus on implementation (in Matlab) and insights into algorithms discussed in class.

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

Homework 1: assigned 4/16, due 4/23. See the homework pdf file and a zip folder with related Matlab files here.
Please upload submissions here.

HW 1 solutions are posted, please check the Catalyst sharespace (same link as the HW files).

Homework 2: assigned 5/12, due 5/23 (Friday), 11:45pm. See the homework pdf file and a zip folder with related Matlab files here.
Please upload submissions here.


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
The requirements for the projects are (1) proposal, due in mid quarter, (2) in-class presentation or poster, and (3) a written report, due towards the end of the quarter.

Project timeline: proposal due: Thurs 5/1 (by 11:45pm); presentations: 6/2, 6/4 (you will be assigned to one of the days); final report due: Tues 6/10.
Project proposal: 2 pages, including description of topic and problem to be explored and relevant references. Due 5/1, please upload on our class dropbox.

Project presentations: 15 minute presentation (12 min talk, 3 min questions, strict time!). Please prepare a short set of slides. Presentation should cover the main ideas and your results; details will be covered in your report. You can continue work on your project after presenting until project report is due.

Schedule of presentations:
(If you cannot present on the date denoted above, you can try swapping with someone else.)

Mon June 2, 1:15pm-3pm:
Abe Engle
Hao Fang + Yi Luan
Roy Han
Luheng He
Phillip Lee
David Perlmutter

Wed June 4, 1:00pm-3pm:
Sam Potter
Roy Scott
Mushfiqur Sarker + Yushi Tan
Akshay Srinivasan
Jon Swenson
Chad Young
Tao Zhu

Project report: due Tues June 10. Up to 8 pages including plots (there's no limit on the bibliography).


Course information

Credit: 3 units
Lectures: Mondays and Wednesdays, 1:30-2:50pm, MEB room 245

Instructor: Maryam Fazel, office: Paul Allen Center, Room CSE 230.

Office hourse: Wednesdays 3-5pm

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

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. Note that the second and third book are freely available online. The first and the fourth book are on reserve at the UW engineering library.