## ELEC5470/IEDA6100A - Convex Optimization

The Hong Kong University of Science and Technology (HKUST), Fall 2019-20

Prof. Daniel P. Palomar

Prof. Daniel P. Palomar

## Description

In the last three decades, a number of fundamental and practical results have been obtained in the area of convex optimization theory. It is a well-developed area, both in the theoretical and practical aspects, and the engineering community has greatly benefited from these recent advances by finding key applications.

This graduate course introduces convex optimization theory and illustrates its use with many applications where convex and nonconvex formulations arise. The emphasis will be on i) the art of unveiling the hidden convexity of problems by appropriate manipulations, ii) a proper characterization of the solution either analytically or algorithmically, and iii) multiple practical ways to approach nonconvex problems.

The course follows a case-study approach by considering recent successful applications of convex optimization published within the last decade in top scientific journals in the areas of signal processing, finance, machine learning, and big data. Problems covered include portfolio optimization in financial markets, filter design, beamforming design in wireless communications, classification in machine learning, circuit design, robust designs under uncertainty, sparse optimization, low-rank optimization, graph learning from data, discrete maximum likelihood decoding, network optimization, distributed algorithms, Internet protocol design, etc.

This graduate course introduces convex optimization theory and illustrates its use with many applications where convex and nonconvex formulations arise. The emphasis will be on i) the art of unveiling the hidden convexity of problems by appropriate manipulations, ii) a proper characterization of the solution either analytically or algorithmically, and iii) multiple practical ways to approach nonconvex problems.

The course follows a case-study approach by considering recent successful applications of convex optimization published within the last decade in top scientific journals in the areas of signal processing, finance, machine learning, and big data. Problems covered include portfolio optimization in financial markets, filter design, beamforming design in wireless communications, classification in machine learning, circuit design, robust designs under uncertainty, sparse optimization, low-rank optimization, graph learning from data, discrete maximum likelihood decoding, network optimization, distributed algorithms, Internet protocol design, etc.

## Textbooks

- S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.
- Daniel P. Palomar and Yonina C. Eldar, Eds., Convex Optimization in Signal Processing and Communications, Cambridge University Press, 2009.

## Lectures

Course syllabus.

Lecture notes: intro

Reading assignment: overview of convex optimization theory in Chapter 1 of B&V textbook.

Lecture notes: convex sets, convex functions.

Reading assignment: mathematical background in Appendix A of B&V textbook (optional: Chapters 2 and 3).

Lecture notes: convex problems

Reading assignment (optional): Chapter 4 of B&V textbook.

Lecture notes: filter design

Reading assignment (optional): Chapters 9 and 11 of B&V textbook.

Reading assignment: cvx user guide, cvx for Matlab, cvx for Python, cvx for R, cvx for Julia.

Lecture notes: duality

Reading assignment (optional): Chapter 5 of B&V textbook.

Lecture notes: whiteboard.

Lecture notes: Markowitz portfolio optimization

Lecture notes: MM-algorithms

Reading assignment: 2017 MM tutorial

Optional reading assignment: Tyler estimator via MM 2014 paper and Cauchy estimator via MM 2015 paper (R package fitHeavyTail), SCA 2014 paper

Lecture notes: risk parity portfolio

Optional reading assignment: SCA for rpp 2015 paper

Software: R package riskParityPortfolio

Lecture notes: GP with applications in power control

Optional reading assignment: power control 2007 paper

Lecture notes: sparsity via convex optimization

Lecture notes: sparse index tracking

Optional reading assignment: index tracking 2018 paper, 2018 book

Software: R package sparseIndexTracking

Midterm

Lecture notes: SVM

Lecture notes: low-rank matrix optimization

Lecture notes: robust optimization

Lecture notes: graph learning

Software: R package spectralGraphTopology

Lecture notes: SDP relaxation for ML decoding

Optional reading assignment: universal binary SDP relaxation 2013 paper

Lecture notes: rank-constrained SDP

Optional reading assignment: 2010 paper, dual 2010 paper

Lecture notes: primal-dual decompositions, alternative decompositions for NUM in wired and wireless networks

Reading assignment: tutorial paper by Palomar&Chiang, more detailed paper by Palomar&Chiang.

Lecture notes: optimizing the Internet

**Week 1**(9-Sep-2019)**Lecture 1 - Introduction**Lecture notes: intro

Reading assignment: overview of convex optimization theory in Chapter 1 of B&V textbook.

**Lecture 2 - Theory: convex sets and convex functions**Lecture notes: convex sets, convex functions.

Reading assignment: mathematical background in Appendix A of B&V textbook (optional: Chapters 2 and 3).

**Week 2**(16-Sep-2019)**Lecture 3 - Theory: convex problems and taxonomy (LP, QP, SOCP, SDP, GP)**Lecture notes: convex problems

Reading assignment (optional): Chapter 4 of B&V textbook.

**Lecture 4 - Application: filter design**Lecture notes: filter design

**Week 3**(23-Sep-2019)**Lecture 5 - Theory: numerical algorithms - interior point methods**Reading assignment (optional): Chapters 9 and 11 of B&V textbook.

**Lecture 6 - Theory: disciplined convex programming - cvx**Reading assignment: cvx user guide, cvx for Matlab, cvx for Python, cvx for R, cvx for Julia.

**Week 4**(30-Sep-2019)**Lecture 7 - Theory: Lagrange duality and KKT conditions**Lecture notes: duality

Reading assignment (optional): Chapter 5 of B&V textbook.

**Lecture 8 - Application: waterfilling solutions**Lecture notes: whiteboard.

**Week 5**(14-Oct-2019)**Lecture 9 - Application: Markowitz Portfolio Optimization**Lecture notes: Markowitz portfolio optimization

**Lecture 10 - Theory&Application: MM-based Algorithms**Lecture notes: MM-algorithms

Reading assignment: 2017 MM tutorial

Optional reading assignment: Tyler estimator via MM 2014 paper and Cauchy estimator via MM 2015 paper (R package fitHeavyTail), SCA 2014 paper

**Week 6**(21-Oct-2019)**Lecture 11 - Application: Risk parity portfolio in finance**Lecture notes: risk parity portfolio

Optional reading assignment: SCA for rpp 2015 paper

Software: R package riskParityPortfolio

**Lecture 12 - Theory&Application: Geometric Programming (GP)**Lecture notes: GP with applications in power control

Optional reading assignment: power control 2007 paper

**Week 7**(28-Oct-2019)**Lecture 13 - Application: Sparsity via Convex Optimization**Lecture notes: sparsity via convex optimization

**Lecture 14 - Application: Sparse index tracking in finance**Lecture notes: sparse index tracking

Optional reading assignment: index tracking 2018 paper, 2018 book

Software: R package sparseIndexTracking

**Week 8**(4-Nov-2019)Midterm

**W****eek 9**(6-9pm Mon 18-Nov, Rm5508 - lifts 25-26)**Lecture 15 - Application: classification and SVM**Lecture notes: SVM

**Lecture 16 - Application: low-rank optimization problems (e.g., Netflix, video security)**Lecture notes: low-rank matrix optimization

**W****eek 10****Lecture 17 - Application: Robust optimization with applications**(3-4:30pm Wed 20-Nov, Rm4621 - lifts 31-32)Lecture notes: robust optimization

**Lecture 18 - Application: Graph learning from data**(3-4:30pm Fri 22-Nov, Rm4621 - lifts 31-32)Lecture notes: graph learning

Software: R package spectralGraphTopology

**Week 11**(2-5pm 25-Nov Rm2303 - lifts 17/18)**Lecture 19 - Application: ML decoding via SDP relaxation**Lecture notes: SDP relaxation for ML decoding

Optional reading assignment: universal binary SDP relaxation 2013 paper

**Lecture 20 - Application: Rank-constrained SDP and multiuser downlink beamforming**Lecture notes: rank-constrained SDP

Optional reading assignment: 2010 paper, dual 2010 paper

**W****eek 12****Lecture 21 - Application: primal/dual decomposition techniques with applications**(3-4:30pm Wed 27-Nov, Rm4621 - lifts 31-32)Lecture notes: primal-dual decompositions, alternative decompositions for NUM in wired and wireless networks

Reading assignment: tutorial paper by Palomar&Chiang, more detailed paper by Palomar&Chiang.

**Lecture 22 - Application: the Internet as a convex optimization problem**(3-4:30pm Fri 29-Nov, Rm4621 - lifts 31-32)Lecture notes: optimizing the Internet