Convex Optimization from Fundamentals to Applications
``Convex Optimization from Fundamentals to Applications”
Short Course at Xiamen University (2013/12/5-2013/12/18)
Instructor: Prof. Chong-Yun Chi (祁忠勇), NTHU, Hsinchu, Taiwan
;
Purpose: The short course participants can smoothlyand efficiently learn how to solve an optimizationproblem, from the fundamental theory, problem definition,reformation into a convex problem, analysis,algorithm implementation, to cutting edge researches(like an exploration journey rather than pure mathematics)in signal processing, communications, etc.
Coverage of the short course: Chapters 1-10 of the textbook below.
Day 1: 12/5 (Thu): Opening talk and Mathematical Background (Chapter 1)
Day 2: 12/6 (Fri): Convex Sets (Chapter 2)
Day 3: 12/9 (Mon): Convex Functions I (Chapter 3)
Day 4: 12/10 (Tue): Convex Functions II (Chapter 3)
Day 5: 12/12 (Thu): Convex Optimization Problems & Geometric Program (GP) (Chapters 4 & 5)
Day 6: 12/13 (Fri): Duality I (Chapter 9)
Day 7: 12/16 (Mon): Duality II & Applications of LP and QP (Chapters 9 & 6)
Day 8: 12/17 (Tue): Applications of SOCP and SDP (Chapters 7 & 8)
Day 9: 12/18 (Wed): Interior-Point Methods (Chapter 10)
(There will be four lecture hours for every lecture day)
Teaching& Learning:
˙A hard copy of the textbook is needed for every participant. It is suggested that
each participantpreviewsthe associated chapters to be covered prior to the next lecture.
˙Core knowledgeof Convex Optimization (Chapters 2,3,4,9,10) will be taught in detail with someheuristicinteractions with the participants.Some homework assignments will be given for checking if the core knowledge has been learned well.
˙Applications of Convex Optimization(Chapters 5,6,7,8) will be taught in a more Question &Answers fashion so that the participants can test if participants are able to solve somecutting edge research problems using fundamentals of Convex Optimizationthey have learned. Then aterm project will be given for hands-on experiencefor participants to practice how to solve a cutting edge research problem.
˙I’ll stay in the temporary office every day for answering questions and face-to-face discussions.
Textbook:
Chong-Yung Chi, Convex Optimization for Signal Processing and Communications, to be published.This book contains 10 chapters as follows:
Chapter 1: Mathematical Background
1.1 Mathematical prerequisites
1.2 Linear algebra revisited
Chapter 2: Convex Sets
2.1 Affine and Convex sets
2.2 Examples of convex sets
2.3 Convexity preserving operations
2.4 Generalized inequalities
2.5 Dual norm and Dual cones
2.6 Separating and Supportinghyperplanes
Chapter 3: Convex Functions
3.1 Basic properties and examples
3.2 Convexity preserving operations
3.3 Quasiconvex functions
3.4 Monotonicity on generalized inequality
3.5 Convexity on generalized inequality
Chapter 4: Convex Optimization Problems
4.1 Optimization problems in a standard form
4.2 Convex optimization problems
4.3 Equivalent representations and transforms
4.4 Convex problems with generalized inequalities
4.5 Quasiconvex optimization
Chapter 5: Geometric Program
5.1 Some basics
5.2 Geometric program
5.3 Geometric program in a convex form
5.4 Condensation method
Chapter 6: Linear and Quadratic Programs
6.1 Linear programming (LP)
6.2 Examples using LP
6.3 Applications in blind source separation using LP
6.4 Quadratic programming (QP)
6.5 Applications of QP in hyperspectral image analysis
6.6 Quadratically constrained QP (QCQP)
6.7 Applications of QP and QCQP in beamformer design
Chapter 7: Second-order Cone Program
7.1 Second-order cone program (SOCP)
7.2 Robust linear programming
7.3 Chance constrained linear programming
7.4 Robust least squares
7.5 Robust receive beamforming via SOCP
7.6 Transmit downlink beamforming via SOCP
Chapter 8: Semidefinite Programming
8.1 Semidefinite programming (SDP)
8.2 LP as SDP
8.3 Schur complement
8.4 QCQP and SOCP as SDP
8.5 S-Procedure
8.6 Applications in combinatorial optimization
8.7 Applications in transmit beamforming
Chapter 9: Duality
9.1 Lagrange dual function and Conjugate function
9.2 Dual problem
9.3 Strong duality
9.4 Implications of strong duality
9.5 Karush-Kuhn-Tucker (KKT) optimality conditions
9.6 Dual Optimization
9.7 Duality of problems with generalized inequalities
9.8 Theorems of alternatives
Chapter 10: Interior-point Methods
10.1 Inequality and equality constrained convex problems
10.2 Newton’s Method and Barrier function
10.3 Central path
10.4 Barrier method
10.5 Primal-dual interior-point methods
Expectation: Any comments and suggestions to the short course materials and teaching improvement in any form are welcome and greatly appreciated. Look forward to joint research exploration for double-win novel research breakthroughs.