Archive ELEC5470 - Convex Optimization
Hong Kong University of Science and Technology (HKUST), Fall 2015-16
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 communication systems and signal processing such as filter/beamforming design, circuit design, robust designs under uncertainty, cognitive radio systems, image processing, portfolio optimization in financial systems, transceiver design for MIMO channels, multiuser detection, duality in information theory, network optimization, distributed algorithms, wireless network power control, 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 communication systems and signal processing such as filter/beamforming design, circuit design, robust designs under uncertainty, cognitive radio systems, image processing, portfolio optimization in financial systems, transceiver design for MIMO channels, multiuser detection, duality in information theory, network optimization, distributed algorithms, wireless network power control, 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 1 - Introduction (7-Sept-2015)
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 (7-Sept-2015)
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) (14-Sept-2015)
Lecture notes: convex problems.
Reading assignment: (optional: Chapter 4 of B&V textbook).
Homework: HW#1 (due before next class on 21-Sept-2015).
Lecture 4 - Application: norm minimiz. with applications to image processing (14-Sept-2015)
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 (21-Sept-2015)
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 (21-Sept-2015)
Lecture notes: cvx, cvx examples.
Reading assignment: cvx user guide.
Homework: install cvx package and do HW#2 (due before class on 5-Oct-2015). 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 (5-Oct-2015)
Lecture notes: duality.
Reading assignment: (optional: Chapter 5 of B&V textbook and historical note by Kuhn).
Lecture 8 - Application: waterfilling solutions (5-Oct-2015)
Lecture notes: whiteboard.
Reading assignment: paper on iterative waterfilling by Yu,Rhee,Boyd&Cioffi.
Homework: do HW#3 (due before class on 12-Oct-2015).
Lecture 9 - Theory: numerical algorithms - interior point methods (12-Oct-2015)
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 (12-Oct-2015)
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 19-Oct-2015).
Lecture 11 - Theory: MM-based Algorithms (19-Oct-2015)
Lecture notes: MM-algorithms.
Optional reading assignment: decomposition by partial linearization framework 2014 paper by Scutari et al.
Lecture 12 - Application: l1-Norm Minimization for Convex-Cardinality Problems (19-Oct-2015)
Lecture notes: l1-norm minimization.
Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.
Lecture 13 - Application: classification and SVM (26-Oct-2015)
Lecture notes: SVM.
Reading assignment: application paper by Vapnik'99.
Lecture 14 - Application: segmentation and multiview 3D reconstruction in image processing (26-Oct-2015)
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.
Homework: do HW#5 (due before class on 13-Oct-2014).
Lecture 15 - Application: ML decoding via SDP relaxation (2-Nov-2015)
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 (2-Nov-2015)
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: low-rank optimization problems (e.g., Netflix, video security) (9-Nov-2015)
Lecture notes: slides low-rank matrix optimization.
Lecture 18 - Application: blind deconvolution via convex optimization for image processing (9-Nov-2015)
Lecture notes: slides by Ken Ma (also this version).
Reading assignment: paper by Chan, Ma, Chi, and Wang.
Lecture 19 - Theory: primal/dual decomposition techniques (16-Nov-2015)
Lecture notes: slides.
Reading assignment: none.
Lecture 20 - Application: alternative decompositions for NUM in wired and wireless networks (16-Nov-2015)
Lecture notes: slides.
Reading assignment: alternative distributed algorithms for NUM by Palomar&Chiang.
Lecture 21 - Application: single-user MIMO linear transceiver design based on Schur-convexity (23-Nov-2015)
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.
Lecture 22 - Application: the Internet as a convex optimization problem (23-Nov-2015)
Lecture notes: slides.
Reading assignment: understanding Vegas by Low,Peterson&Wang (additional: internet congestion control by Low,Paganini&Doyleand optimization flow control by Low&Lapsley).
Lecture 23 - Application: portfolio optimization in financial engineering (30-Nov-2015)
Lecture notes: slides.
Lecture 24 - Summary (30-Nov-2015)
Lecture notes: whiteboard&slides.
Extra Lectures
Lecture 1 - Introduction (7-Sept-2015)
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 (7-Sept-2015)
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) (14-Sept-2015)
Lecture notes: convex problems.
Reading assignment: (optional: Chapter 4 of B&V textbook).
Homework: HW#1 (due before next class on 21-Sept-2015).
Lecture 4 - Application: norm minimiz. with applications to image processing (14-Sept-2015)
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 (21-Sept-2015)
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 (21-Sept-2015)
Lecture notes: cvx, cvx examples.
Reading assignment: cvx user guide.
Homework: install cvx package and do HW#2 (due before class on 5-Oct-2015). 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 (5-Oct-2015)
Lecture notes: duality.
Reading assignment: (optional: Chapter 5 of B&V textbook and historical note by Kuhn).
Lecture 8 - Application: waterfilling solutions (5-Oct-2015)
Lecture notes: whiteboard.
Reading assignment: paper on iterative waterfilling by Yu,Rhee,Boyd&Cioffi.
Homework: do HW#3 (due before class on 12-Oct-2015).
Lecture 9 - Theory: numerical algorithms - interior point methods (12-Oct-2015)
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 (12-Oct-2015)
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 19-Oct-2015).
Lecture 11 - Theory: MM-based Algorithms (19-Oct-2015)
Lecture notes: MM-algorithms.
Optional reading assignment: decomposition by partial linearization framework 2014 paper by Scutari et al.
Lecture 12 - Application: l1-Norm Minimization for Convex-Cardinality Problems (19-Oct-2015)
Lecture notes: l1-norm minimization.
Reading assignment: SPM 2010 tutorial by Zibulevsky&Elad.
Lecture 13 - Application: classification and SVM (26-Oct-2015)
Lecture notes: SVM.
Reading assignment: application paper by Vapnik'99.
Lecture 14 - Application: segmentation and multiview 3D reconstruction in image processing (26-Oct-2015)
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.
Homework: do HW#5 (due before class on 13-Oct-2014).
Lecture 15 - Application: ML decoding via SDP relaxation (2-Nov-2015)
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 (2-Nov-2015)
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: low-rank optimization problems (e.g., Netflix, video security) (9-Nov-2015)
Lecture notes: slides low-rank matrix optimization.
Lecture 18 - Application: blind deconvolution via convex optimization for image processing (9-Nov-2015)
Lecture notes: slides by Ken Ma (also this version).
Reading assignment: paper by Chan, Ma, Chi, and Wang.
Lecture 19 - Theory: primal/dual decomposition techniques (16-Nov-2015)
Lecture notes: slides.
Reading assignment: none.
Lecture 20 - Application: alternative decompositions for NUM in wired and wireless networks (16-Nov-2015)
Lecture notes: slides.
Reading assignment: alternative distributed algorithms for NUM by Palomar&Chiang.
Lecture 21 - Application: single-user MIMO linear transceiver design based on Schur-convexity (23-Nov-2015)
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.
Lecture 22 - Application: the Internet as a convex optimization problem (23-Nov-2015)
Lecture notes: slides.
Reading assignment: understanding Vegas by Low,Peterson&Wang (additional: internet congestion control by Low,Paganini&Doyleand optimization flow control by Low&Lapsley).
Lecture 23 - Application: portfolio optimization in financial engineering (30-Nov-2015)
Lecture notes: slides.
Lecture 24 - Summary (30-Nov-2015)
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.