**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**

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.