## ELEC5470 - Convex Optimization

Hong Kong University of Science and Technology (HKUST), Fall 2017-18

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 18-Sept-2017).

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 before class on 25-Sept-2017). You can use different programming languages like Matab (cvx package), Python (cvx package), R (cvx package), Julia (cvx package), Octave, etc. (Matlab language tutorials: Matlab crash course by T. Driscoll and 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 9-Oct-2017).

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 16-Oct-2017).

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 23-Oct-2017).

**Lecture 1 - Introduction**(4-Sept-2017)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**(4-Sept-2017)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)**(11-Sept-2017)Lecture notes: convex problems.

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

Homework: HW#1 (due before next class on 18-Sept-2017).

**Lecture 4 - Application: norm minimiz. with applications to image processing**(11-Sept-2017)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**(18-Sept-2017)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**(18-Sept-2017)Lecture notes: slides1, slides2, slides3, slides4.

Reading assignment: cvx user guide.

Homework: install cvx package and do HW#2 (due before class on 25-Sept-2017). You can use different programming languages like Matab (cvx package), Python (cvx package), R (cvx package), Julia (cvx package), Octave, etc. (Matlab language tutorials: Matlab crash course by T. Driscoll and Matlab official manual by The MathWorks.)

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

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

**Lecture 8 - Application: waterfilling solutions**(25-Sept-2017)Lecture notes: whiteboard.

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

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

**Lecture 9 - Theory: numerical algorithms - interior point methods**(9-Oct-2017)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**(9-Oct-2017)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 16-Oct-2017).

**Lecture 11 - Theory: MM-based Algorithms**(16-Oct-2017)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)**(16-Oct-2017)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 23-Oct-2017).

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