## ELEC5470 - Convex Optimization

Hong Kong University of Science and Technology (HKUST), Fall 2016-17

Daniel P. Palomar

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

* I would like to thank Stephen Boyd (Stanford University) and Lieven Vanderberghe (UCLA) for their course material used in some of the 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 on 19-Sept-2016).

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: cvx, cvx examples.

Reading assignment: cvx user guide.

Homework: install cvx package and do HW#2 (due before class on 26-Sept-2016). You should be familiar with Matlab; if not, see the Matlab crash course by T. Driscoll or the Matlab official manual by The MathWorks.

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.

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

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#4 (due before class on 17-Oct-2016).

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#5 (due before class on 24-Oct-2016).

Lecture notes: l1-norm minimization.

Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.

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, financial monograph, ICASSP2016 tutorial slides.

Lecture notes: slides low-rank matrix optimization.

Lecture notes: slides.

Reading assignment: none.

Lecture notes: slides.

Reading assignment: alternative distributed algorithms for NUM 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.

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.

Lecture notes: whiteboard&slides.

**Lecture 1 - Introduction**(5-Sept-2016)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**(5-Sept-2016)Lecture notes: convex sets, convex functions.

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

**Lecture 3 - Theory: convex problems and classes of convex problems (LP, QP, SOCP, SDP, GP)**(12-Sept-2016)Lecture notes: convex problems.

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

Homework: HW#1 (due before next class on 19-Sept-2016).

**Lecture 4 - Application: norm minimiz. with applications to image processing**(12-Sept-2016)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 5 - Application: filter design**(19-Sept-2016)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**(19-Sept-2016)Lecture notes: cvx, cvx examples.

Reading assignment: cvx user guide.

Homework: install cvx package and do HW#2 (due before class on 26-Sept-2016). You should be familiar with Matlab; if not, see the Matlab crash course by T. Driscoll or the Matlab official manual by The MathWorks.

**Lecture 7 - Theory: Lagrange duality and KKT conditions**(26-Sept-2016)Lecture notes: duality.

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

**Lecture 8 - Application: waterfilling solutions**(26-Sept-2016)Lecture notes: whiteboard.

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

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

**Lecture 9 - Theory: numerical algorithms - interior point methods**(3-Oct-2016)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**(3-Oct-2016)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#4 (due before class on 17-Oct-2016).

**Lecture 11 - Theory: MM-based Algorithms**(17-Oct-2016)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)**(17-Oct-2016)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#5 (due before class on 24-Oct-2016).

**Lecture 13 - Application: l1-Norm Minimization for Convex-Cardinality Problems**(24-Oct-2016)Lecture notes: l1-norm minimization.

Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.

**Lecture 14 - Application: classification and SVM**(24-Oct-2016)Lecture notes: SVM.

Reading assignment: application paper by Vapnik'99.

**Lecture 15 - Application: ML decoding via SDP relaxation**(31-Oct-2016)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 16 - Application: multiuser downlink beamforming: rank-constrained SDP**(31-Oct-2016)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 17 - Application: portfolio optimization in financial engineering**(14-Nov-2016)Lecture notes: slides, financial monograph, ICASSP2016 tutorial slides.

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

**Lecture 19 - Theory: primal/dual decomposition techniques**(21-Nov-2016)Lecture notes: slides.

Reading assignment: none.

**Lecture 20 - Application: alternative decompositions for NUM in wired and wireless networks**(21-Nov-2016)Lecture notes: slides.

Reading assignment: alternative distributed algorithms for NUM by Palomar&Chiang.

**Lecture 21 - Application: the Internet as a convex optimization problem**(24-Nov-2016)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**(24-Nov-2016)Lecture notes: slides by Ken Ma (also this version).

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

**Lecture 23 - Application: single-user MIMO linear transceiver design based on Schur-convexity**(28-Nov-2016)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.

**Lecture 24 - Summary**(28-Nov-2016)Lecture notes: whiteboard&slides.

**Extra Lectures**- 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.