CS 8292: Advanced Topics in Convex Optimization and its Applications

Class Lecturer

Dr Chee Wei Tan

Lecture Schedule

Every Wednesday, 9:30- 12:20, ACAD G5-128.

Course Description

The goal of this course is to expose students to modern and fundamental developments in convex optimization, a subject which has experienced tremendous growth in the last 15 years or so. This course will focus on the conceptual and algorithmic sides of convex optimization. On the conceptual side, emphasis will be put on geometric programming, and conic programming, in particular, semidefinite programming, whose rich expressive power makes it suitable for a wide spectrum of important optimization problems arising in engineering and applied science. On the algorithmic side, the course will cover interior point methods, novel and efficient first-order methods for smooth and nonsmooth convex optimization which are suitable for large-scale problems. Distributed algorithms in optimization for a variety of engineering applications will be selectively drawn from the following: computer networking, Internet and network protocols, communication systems, signal processing, social networks and data mining.

Acknowledgement

I would like to thank Professors Mung Chiang (Princeton), Stephen Boyd (Stanford) and Steven Low (Caltech) for many of the course materials on convex optimization.

Primary Textbook

S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

Course Syllabus

CS8292 Class Outline

Week 1:
Lecture 1: Introduction
Lecture 2: Convex Functions and Sets

Week 2:
Lecture 3: Convex Optimization and Lagrange Duality
Lecture 4: Linear and Quadratic Programming

Week 3:
Lecture 5: Unconstrained Optimization Algorithms
Lecture 6: Disciplined Convex Programming & CVX (Slides from Boyd’s ele364a)

Week 4:
Lecture 7: Real-time Embedded Convex Optimization (Slides from Boyd’s ISMP Plenary Talk)
Reading: J. Mattingley and S. Boyd, “Real-time Convex Optimization in Signal Processing”, IEEE Signal Processing Magazine, 27(3): 50-61, May 2010
Lecture 8: Midterm Revision

Week 5:
Lecture 9: Constrained Optimization Algorithms
In-class Midterm

Week 6:
Lecture 10: Geometric Programming

Week 7:
Lecture 11: Wireless Power Control
Reading: C. W. Tan, "Wireless Network Optimization by Perron-Frobenius Theory", Foundations and Trends in Networking, vol. 9, no. 2-3, pp. 107-218, 2015.

Week 8:
Lecture 12: Nonconvex Wireless Power Control

Week 9:
Lecture 13: Primal and Dual Decomposition: Theory and Distributed Algorithms
Lecture 14: Internet Congestion Control
Reading: S. Shakkottai, R. Srikant, "Network optimization and control", Foundations and Trends in Networking, vol. 2, no. 3, pp. 271-379, 2007.

Week 10:
Lecture 15: Semidefinite Programming
Lecture 16: Max-Cut Problem and Approximation Algorithms

Week 11:
Lecture 17: Convex-Cardinality Programming: Part I, Part II (from Boyd’s ele364b)
Lecture 18: Branch and Bound Algorithm (from Boyd’s ele364b)
Lecture 19: Data Mining: Nonnegative Matrix Factorization

Week 12:
Lecture 20: Conclusion and Revision
Project Presentation

Week 13:
Revision

Other References

1. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering, SIAM, 2001
2. D. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods. 1stEdition, Prentice Hall, 1989
3. Matlab and the CVX optimization environment will be used for analysis and programming synthesis. CVX can be downloaded from Stanford University

Grading

Four sets of homework assignments (5%)
One in-class quiz (5%)
One individual final project where each student either conducts original research or implements existing algorithms (30%)
One in-class final exam (60%)

Prerequisite

Basic understanding of linear algebra, advanced calculus and basic knowledge of Matlab. Previous exposure to linear programming will help but is not needed.