Instructors Sameer Agarwal,
sagarwal@cs.washington.edu Teaching Assistant
Yongjoon
Lee, yongjoon@cs.washington.edu Schedule Tuesdays
and Thursdays 10:30AM  11:50AM Mailing List Please
join the mailing
list for important announcements. 
Description  References  Policies  Lectures  Homework
In this course we will cover the practical aspects of convex optimization,
focusing on ways in which it can be applied to a wide variety of problems in
computer science and elsewhere. The first part of the course will cover the
theory of convex programming and how that theory is translated into working
code. The second part of the course will focus on the art of casting specific
practical problems into convex programs, with applications to various computer
science problems including but not limited to AI, vision and graphics.
Books
The textbook for this course is Convex Optimization by S. Boyd & L. Vandenberghe, Cambridge
University Press, 2004. The book is also available online at http://www.stanford.edu/~boyd/cvxbook/.
In the first part of the course we will follow the textbook closely. In the
second part of the course additional reading material will be made available
online.
Besides the course textbook, you may find the following texts useful for
reference:
Numerical Optimization by J. Nocedal & S. J. Wright, Springer, 1999.
Nonlinear Programming by D. Bertsekas, Athena Scientific, 1999.
Nonlinear Programming by O. L. Mangasarian, SIAM, 1994.
Matrix Analysis by Horn & Johnson, Cambridge University Press, 1990.
Software
The programming assignments in the class will require you to use MATLAB and SeDuMi. SeDuMi is a high quality convex
solver that can be used to solve optimization problems with linear, second
order cone and semidefinite constraints.
In the first part of the course, homework will be assigned every week on
thursday and will be due thursday of the following week.
In lieu of exams, the course has a project which requires independent work
on a topic of your choice. You are welcome to choose a project that intersects
as much as possible with your current research interests. Course projects will
be presented in an informal poster session at the end of the quarter and the work
will be summarized in a writeup. Both individual and group projects (2
persons) are allowed.
The lecture schedule for the quarter is still evolving and is subject to
change.
Date 
Topic 
Reading 
Misc  
1. 
Mar 27 
Introduction, Convex Sets 
B&V Chapter 1 & 2 

2. 
Mar 29 
Convex Sets 
B&V Chapter 2 

3. 
Apr 03 
Convex Functions 
B&V Chapter 3 

4. 
Apr 05 
Convex Functions 
B&V Chapter 3 
Homework 1 Due 
5. 
Apr 10 
Convex Optimization Problems 
B&V Chapter 4 

6. 
Apr 12 
Convex Optimization Problems 
B&V Chapter 4 

7. 
Apr 17 
Convex Optimization Problems 
B&V Chapter 4 

8. 
Apr 19 
Duality 
B&V Chapter 5 
Homework 2 Due 
9. 
Apr 24 
Duality 
B&V Chapter 5 

10. 
Apr 26 
Duality 
B&V Chapter 5 

11. 
May 01 
Machine Learning, SVM, Dimensionality
Reduction 
TBA 

12. 
May 03 
Optimal Control, Approximate
Dynamic Programming 
TBA 

13. 
May 08 
Unconstrained Optimization 
B&V Chapter 9 

14. 
May 10 
Equality Constrained Optimization 
B&V Chapter 10 

15. 
May 15 
Barrier & Interior Point
Methods 
B&V Chapter 11 
Homework 3 Due 
16. 
May 17 
Nonsmooth Optimization, Subgradient
Methods 
TBA 

17. 
May 22 
LPs,SDPs in Approximation
Algorithms 
TBA 

18. 
May 24 
Semidefinite Programming for
Polynomial Optimization 
TBA 

19. 
May 29 
Global Optimization (Branch &
Bound) 
TBA 

20. 
May 31 
TBA 
TBA 

June 4 
Poster Session 
Homework 1: B&V Problems 2.2, 2.8, 2.9, 2.10, 2.13, 2.16, 2.21, 2.25, 2.32 Extra Credit: 2.36
Homework 2: B&V Problems 3.1, 3.6, 3.7, 3.16, 3.18, 3.22, 3.29, 3.30, 3.42, 3.43 Extra Credit: 3.26
Homework 3: B&V Problems 4.5, 4.26, 4.13, 6.3(a,b), 6.9, 8.10, 8.24 Extra Credit: 4.56