## ELEC5470 - Convex Optimization

Hong Kong University of Science and Technology (HKUST), Fall 2018-19

Prof. Daniel P. Palomar

Prof. Daniel P. Palomar

## Description

In the last two 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 applications.

This graduate course introduces the basic theory and illustrates its use with many recent applications in communication systems and signal processing. The emphasis will be on i) the art of unveiling the hidden convexity of problems by appropriate manipulations, and ii) a proper characterization of the solution either analytically or algorithmically. The course follows a case-study approach by considering recent successful applications of convex optimization published within the last decade in scientific journals.

Problems will be covered in areas of signal processing such as filter/beamforming design, circuit design, robust designs under uncertainty, sparsity optimization, low-rank optimization, image processing, classification methods, portfolio optimization in financial systems, discrete maximum likelihood decoding, transceiver design for MIMO channels, cognitive radio systems, network optimization, distributed algorithms, wireless network power control, Internet protocol design, etc.

This graduate course introduces the basic theory and illustrates its use with many recent applications in communication systems and signal processing. The emphasis will be on i) the art of unveiling the hidden convexity of problems by appropriate manipulations, and ii) a proper characterization of the solution either analytically or algorithmically. The course follows a case-study approach by considering recent successful applications of convex optimization published within the last decade in scientific journals.

Problems will be covered in areas of signal processing such as filter/beamforming design, circuit design, robust designs under uncertainty, sparsity optimization, low-rank optimization, image processing, classification methods, portfolio optimization in financial systems, discrete maximum likelihood decoding, transceiver design for MIMO channels, cognitive radio systems, network optimization, distributed algorithms, wireless network power control, 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 Appendix A of MIMO-majorization monograph and 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).

Homework: HW#1 (due before next class).

Lecture notes: B&V-slides on approximation&fitting and notes on whiteboard.

Reading assignment: paper on image restoration by Combettes&Pesquet (Sections I and IV), paper on pixel recovery via l1 wavelet minim. by Selesnick et al. (optional: Chapter 6 of B&V textbook).

Lecture notes: filter design.

Reading assignment: SPM 2010 tutorial by Davidson (optional: paper on antenna array pattern synthesis by Lebret&Boyd).

Lecture notes: slides1, slides2, slides3, slides4.

Reading assignment: cvx user guide.

Homework: install cvx package and do HW#2 (due on 8-Oct before class). You can use different programming languages like Matab (cvx package), Python (cvx package), R (cvx package), Julia (cvx package), Octave, etc. (Matlab tutorials: crash course and official manual. R tutorials: Cookbook R, Quick-R, R tutorial.)

Lecture notes: duality.

Reading assignment: (optional: Chapter 5 of B&V textbook and historical note by Kuhn).

Lecture notes: whiteboard.

Reading assignment: paper on iterative waterfilling by Yu,Rhee,Boyd&Cioffi.

Lecture 9 - Theory: numerical algorithms - interior point methods

Lecture 10 - Application: worst-case robust beamforming

Lecture 11 - Theory: MM-based Algorithms

Lecture 12 - Theory&Application: Geometric Programming (GP)

Lecture 13 - Application: l1-Norm Minimization for Convex-Cardinality Problems

Lecture 14 - Application: Sparse index tracking in finance

Lecture 15 - Application: classification and SVM

Lecture 16 - Application: ML decoding via SDP relaxation

Lecture 17 - Application: multiuser downlink beamforming: rank-constrained SDP

Lecture 18 - Application: portfolio optimization in financial engineering

Lecture 19 - Application: low-rank optimization problems (e.g., Netflix, video security)

Lecture 20 - Application: blind deconvolution via convex optimization for image processing

Lecture 21 - Theory: primal/dual decomposition techniques

Lecture 22 - Application: alternative decompositions for NUM in wired and wireless networks

Lecture 23 - Application: the Internet as a convex optimization problem

Lecture 24 - Summary

**Week 1**(3-Sep-2018)**Lecture 1 - Introduction**Lecture notes: intro.

Reading assignment: overview of convex optimization theory in Appendix A of MIMO-majorization monograph and 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**(10-Sep-2018)**Lecture 3 - Theory: convex problems and classes of convex problems (LP, QP, SOCP, SDP, GP)**Lecture notes: convex problems.

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

Homework: HW#1 (due before next class).

**Lecture 4 - Application: norm minimiz. with applications to image processing**Lecture notes: B&V-slides on approximation&fitting and notes on whiteboard.

Reading assignment: paper on image restoration by Combettes&Pesquet (Sections I and IV), paper on pixel recovery via l1 wavelet minim. by Selesnick et al. (optional: Chapter 6 of B&V textbook).

**Week 3**(21-Sep-2018)**Lecture 5 - Application: filter design**Lecture notes: filter design.

Reading assignment: SPM 2010 tutorial by Davidson (optional: paper on antenna array pattern synthesis by Lebret&Boyd).

**Lecture 6 - Theory: disciplined convex programming - cvx**Lecture notes: slides1, slides2, slides3, slides4.

Reading assignment: cvx user guide.

Homework: install cvx package and do HW#2 (due on 8-Oct before class). You can use different programming languages like Matab (cvx package), Python (cvx package), R (cvx package), Julia (cvx package), Octave, etc. (Matlab tutorials: crash course and official manual. R tutorials: Cookbook R, Quick-R, R tutorial.)

**Week 2**(24-Sep-2018)**Lecture 7 - Theory: Lagrange duality and KKT conditions**Lecture notes: duality.

Reading assignment: (optional: Chapter 5 of B&V textbook and historical note by Kuhn).

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

Reading assignment: paper on iterative waterfilling by Yu,Rhee,Boyd&Cioffi.

Lecture 9 - Theory: numerical algorithms - interior point methods

Lecture 10 - Application: worst-case robust beamforming

Lecture 11 - Theory: MM-based Algorithms

Lecture 12 - Theory&Application: Geometric Programming (GP)

Lecture 13 - Application: l1-Norm Minimization for Convex-Cardinality Problems

Lecture 14 - Application: Sparse index tracking in finance

Lecture 15 - Application: classification and SVM

Lecture 16 - Application: ML decoding via SDP relaxation

Lecture 17 - Application: multiuser downlink beamforming: rank-constrained SDP

Lecture 18 - Application: portfolio optimization in financial engineering

Lecture 19 - Application: low-rank optimization problems (e.g., Netflix, video security)

Lecture 20 - Application: blind deconvolution via convex optimization for image processing

Lecture 21 - Theory: primal/dual decomposition techniques

Lecture 22 - Application: alternative decompositions for NUM in wired and wireless networks

Lecture 23 - Application: the Internet as a convex optimization problem

Lecture 24 - Summary

* I would like to thank Stephen Boyd (Stanford University) and Lieven Vanderberghe (UCLA) for their course material used in some of the lectures.