CSE 558: Convex Optimization and Applications

Instructors

Sameer Agarwal, sagarwal@cs.washington.edu 
Office Hours - 2:00PM - 3:00 PM, Mon, AC 278

Zoran Popović, zoran@cs.washington.edu
Office Hours 1:30pm 2:30pm, Tue, AC 652

Teaching Assistant

Yongjoon Lee, yongjoon@cs.washington.edu
Office Hours - 2:00PM - 3:00 PM, Wed, AC 290

Schedule

Tuesdays and Thursdays 10:30AM - 11:50AM
Place: Mary Gates Hall 284

Mailing List

Please join the mailing list for important announcements.

 

Description | References | Policies | Lectures | Homework

Course Description

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.

Top

References

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.

Top

Course Policies

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.

Top

Lectures

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

Top

Homework

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

Top