|
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 write-up. 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 |
Non-smooth Optimization, Sub-gradient
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