APPM 4720/5720, Special Topics: Advanced Topics in Convex Optimization, Spring 2017

The course investigates landmark convex optimization algorithms and their complexity results. We aim to cover both key theory, such as polynomial time algorithms for linear programming and the optimality of Nesterov’s method, while also surveying current practical state-of-the-art methods. Homework will consist of a choice between theory and programming.

Announcements

Quick Links

Course Information

The course is 4720-009 / 5720-009.

There is no required textbook for the course; see syllabus for more information on supplemental resources.

Some supplemental resources:

  • Lijun Chen teaches a similar optimization course in the CS department, CSCI 5254. That course uses the Boyd and Vandenberghe book
  • S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Free online.
    • The books is very useful, and I recommend you buy a copy. We will follow the book closely at the beginning of the semester. The appendices A and C are also quite useful if you do not have an applied math background.
    • L. Vandenberghe has slides online for his EE235c large-scale optimization course at UCLA.
    • S. Boyd has slides online for his EE364a optimization course at Stanford
  • Ben Recht's CS 726: Nonlinear Optimization I at Wisconsin 2012
  • Sebastian Bubeck's ORF523: The complexities of optimization at Princeton (blog style) and his monograph on the same topic (pdf, published in Foundations and Trends in Machine Learning, Vol. 8: No. 3-4, pp 231-357, 2015).

More advanced resources:

More resources are mentioned in the syllabus.

Lecture Times and Location

Instructor Room Number Time
Stephen Becker ECCR 151 MWF 1 to 1:50 PM

Lecture schedule and references

The quizzes are found on the Stanford EE364a lecture slides page.

Week Date Topic Further references
1 1/18/17 Intro, convexity [Boyd and Vandenberghe 2004, ch 1]. Take the convex intro quiz.
2 1/23/17 Convex sets [Boyd and Vandenberghe 2004, ch 2]. Take the convex set quiz.
3 1/30/17 Convex functions [Boyd and Vandenberghe 2004, ch 3; and strong convexity and Lipschitz constants handout]. Take the convex function quiz.
4 2/6/17 Convex functions

[Boyd and Vandenberghe 2004, ch 3; and P. L. Combettes and V. R. Wajs, "Signal recovery by proximal forward-backward splitting" (2005)].

see also What shape is your Conjugate (Yves Lucet, SIAM Review 2009; free version); and Proximal splitting methods in signal processing (P. L. Combettes and J.-C. Pesquet, 2011) for proximal calculs rules

Office Hours

Instructor/TA Room Number Office Hours
Stephen Becker ECOT 231 Wednesday, 2-4 PM; Thurs 1-2 PM

Homeworks

Homework solutions are to uploaded to D2L.  

Homeworks are due every two weeks.

Homework Due date Comments
Homework 1 and 2 Fri Jan 27 2017 Solutions posted on D2L
Homework 3 and 4 Fri Feb 10 2017 Solutions posted on D2L
Homework 5 and 6; see also logistic regression handout on D2L Fri Feb 24 2017 Solutions posted on D2L
Homework 7 and 8 Fri Mar 10 2017 Solutions posted on D2L
Homework 9 and 10 Fri Mar 24 2017  

Exams

There are no exams

Projects

There will be one class project, worth 25% of your grade. We suggest working in groups of up to three, but you may work alone if necessary.

Policies