## 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 notes: unconstrained minimization, interior-point methods.

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

Lecture notes: whiteboard.

Reading assignment: paper on robust bf. by Vorobyov,Gershman&Luo and book chapter on robust wideband bf by Rubsamen, El-Keyi, Gershman&Kirubarajan (optional: paper on robust bf. by Lorenz&Boyd and paper on robust bf. by Li,Stoica&Wang).

Homework: do HW#3 (due before class on 15-Oct-2018).

Lecture notes: MM-algorithms.

Reading assignment: MM tutorial.

Optional reading assignment: decomposition by partial linearization framework 2014 paper by Scutari et al.

Lecture notes: GP with applications in power control.

Reading assignment: GP tutorial by Boyd et al., paper on power control via GP.

Homework: do HW#4 (due before class on 22-Oct-2018).

Lecture notes: Sparsity via convex optimization.

Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.

Lecture notes: Sparse index tracking.

Midterm

Lecture notes: SVM.

Reading assignment: application paper by Vapnik'99.

Lecture notes: SDP relaxation for ML decoding.

Reading assignment: SPM 2010 tutorial by Luo,Ma,So,Ye&Zhang, tutorial on relaxation by Aspremont&Boyd, book chapter 4 by Luo&Chang, book chapter 5 by So&Ye, universal SDR for ML detection by Fan,Song,Palomar&Au.

Lecture notes: rank-constrained SDP.

Reading assignment: SPM 2010 tutorial by Gershman,Sidiropoulos,Shahbazpanahi,Bengtsson&Ottersten, paper on rank-const SDP by Huang&Palomar.

Lecture notes: slides low-rank matrix optimization.

Lecture notes: slides.

Reading assignment: none.

Lecture notes: slides.

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

Lecture notes: slides.

Reading assignment: understanding Vegas by Low,Peterson&Wang (additional: internet congestion control by Low,Paganini&Doyle and optimization flow control by Low&Lapsley).

Lecture notes: slides by Ken Ma (also this version).

Reading assignment: paper by Chan, Ma, Chi, and Wang.

**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 4**(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.

**Week 5**(8-Oct-2018)**Lecture 9 - Theory: numerical algorithms - interior point methods**Lecture notes: unconstrained minimization, interior-point methods.

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

**Lecture 10 -****Application: worst-case robust beamforming**Lecture notes: whiteboard.

Reading assignment: paper on robust bf. by Vorobyov,Gershman&Luo and book chapter on robust wideband bf by Rubsamen, El-Keyi, Gershman&Kirubarajan (optional: paper on robust bf. by Lorenz&Boyd and paper on robust bf. by Li,Stoica&Wang).

Homework: do HW#3 (due before class on 15-Oct-2018).

**Week 6**(15-Oct-2018)**Lecture 11 - Theory: MM-based Algorithms**Lecture notes: MM-algorithms.

Reading assignment: MM tutorial.

Optional reading assignment: decomposition by partial linearization framework 2014 paper by Scutari et al.

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

Reading assignment: GP tutorial by Boyd et al., paper on power control via GP.

Homework: do HW#4 (due before class on 22-Oct-2018).

**Week 7**(22-Oct-2018)**Lecture 13 - Application: Sparsity via Convex Optimization**Lecture notes: Sparsity via convex optimization.

Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.

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

**Week 8**(29-Oct-2018)Midterm

**Week 9**(5-Nov-2018)**Lecture 15 - Application: classification and SVM**Lecture notes: SVM.

Reading assignment: application paper by Vapnik'99.

**Lecture 16 - Application: ML decoding via SDP relaxation**Lecture notes: SDP relaxation for ML decoding.

Reading assignment: SPM 2010 tutorial by Luo,Ma,So,Ye&Zhang, tutorial on relaxation by Aspremont&Boyd, book chapter 4 by Luo&Chang, book chapter 5 by So&Ye, universal SDR for ML detection by Fan,Song,Palomar&Au.

**Week 10**(12-Nov-2018)**Lecture 17 - Application: multiuser downlink beamforming: rank-constrained SDP**Lecture notes: rank-constrained SDP.

Reading assignment: SPM 2010 tutorial by Gershman,Sidiropoulos,Shahbazpanahi,Bengtsson&Ottersten, paper on rank-const SDP by Huang&Palomar.

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

**Week 11**(19-Nov-2018)**Lecture 19 - Theory: primal/dual decomposition techniques**Lecture notes: slides.

Reading assignment: none.

**Lecture 20 - Application: alternative decompositions for NUM in wired and wireless networks**Lecture notes: slides.

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

**Week 12**(26-Nov-2018)**Lecture 21 - Application: the Internet as a convex optimization problem**Lecture notes: slides.

Reading assignment: understanding Vegas by Low,Peterson&Wang (additional: internet congestion control by Low,Paganini&Doyle and optimization flow control by Low&Lapsley).

**Lecture 22 - Application: blind deconvolution via convex optimization for image processing**Lecture notes: slides by Ken Ma (also this version).

Reading assignment: paper by Chan, Ma, Chi, and Wang.

**Extra Lectures****Application: portfolio optimization in finance**

Lecture notes: portfolio optimization in finance

Reading material: financial monograph- iterative waterfilling algorithm
- primal decomposition for MIMO transceivers
- minimax problems
- Variational Inequality with applications to Cognitive Radio Systems
**Application: segmentation and multiview 3D reconstruction in image processing:**

Lecture notes: segmentation_and_reconstruction.

Reading assignment: tutorial book chapter on relaxation in image proc. by Cremers'11, paper on segmentation'11, paper on 3D reconstruction'09.**Application: single-user MIMO linear transceiver design based on Schur-convexity**

Lecture notes: slides.

Reading assignment: paper on single-user MIMO transceiver design by Palomar,Cioffi&Lagunas, tutorial on MIMO transceiver design by Palomar, monograph on MIMO transceivers, and recent tutorial on majorization theory and applications.

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