Convex Optimization for Signal Processing and Communications : From Fundamentals to Applications

"Convex Optimization for Signal Processing and Communications: From Fundamentals to Applications provides fundamental background knowledge of convex optimization, while striking a balance between mathematical theory and applications in signal processing and communications. In addition to comprehensive proofs and perspective interpretations for core convex optimization theory, this book also provides many insightful figures, remarks, illustrative examples, and guided journeys from theory to cutting-edge research explorations, for efficient and in-depth learning, especially for engineering students and professionals. With the powerful convex optimization theory and tools, this book provides you with a new degree of freedom and the capability of solving challenging real-world scientific and engineering problems."-- Read more... Abstract: "Convex Optimization for Signal Processing and Communications: From Fundamentals to Applications provides fundamental background knowledge of convex optimization, while striking a balance between mathematical theory and applications in signal processing and communications. In addition to comprehensive proofs and perspective interpretations for core convex optimization theory, this book also provides many insightful figures, remarks, illustrative examples, and guided journeys from theory to cutting-edge research explorations, for efficient and in-depth learning, especially for engineering students and professionals. With the powerful convex optimization theory and tools, this book provides you with a new degree of freedom and the capability of solving challenging real-world scientific and engineering problems." Cover 1 Half Title 2 Title Page 4 Copyright Page 5 Table of Contents 6 Preface 12 1: Mathematical Background 16 1.1 Mathematical prerequisites 16 1.1.1 Vector norm 20 1.1.2 Matrix norm 22 1.1.3 Inner product 23 1.1.4 Norm ball 24 1.1.5 Interior point 26 1.1.6 Complement, scaled sets, and sum of sets 26 1.1.7 Closure and boundary 27 1.1.8 Supremum and infimum 28 1.1.9 Function 30 1.1.10 Continuity 30 1.1.11 Derivative and gradient 31 1.1.12 Hessian 34 1.1.13 Taylor series 35 1.2 Linear algebra revisited 37 1.2.1 Vector subspace 37 1.2.2 Range space, null space, and orthogonal projection 37 1.2.3 Matrix determinant and inverse 39 1.2.4 Positive definiteness and semidefiniteness 39 1.2.5 Eigenvalue decomposition 40 1.2.6 Square root factorization of PSD matrices 42 1.2.7 Singular value decomposition 43 1.2.8 Least-squares approximation 45 1.3 Summary and discussion 46 2: Convex Sets 50 2.1 Affine and convex sets 50 2.1.1 Lines and line segments 50 2.1.2 Affine sets and affine hulls 50 2.1.3 Relative interior and relative boundary 54 2.1.4 Convex sets and convex hulls 55 2.1.5 Cones and conic hulls 59 2.2 Examples of convex sets 61 2.2.1 Hyperplanes and halfspaces 61 2.2.2 Euclidean balls and ellipsoids 63 2.2.3 Polyhedra 65 2.2.4 Simplexes 66 2.2.5 Norm cones 69 2.2.6 Positive semidefinite cones 70 2.3 Convexity preserving operations 70 2.3.1 Intersection 71 2.3.2 Affine function 72 2.3.3 Perspective function and linear-fractional function 76 2.4 Generalized inequalities 78 2.4.1 Proper cones and generalized inequalities 78 2.4.2 Properties of generalized inequalities 79 2.4.3 Minimum and minimal elements 79 2.5 Dual norms and dual cones 81 2.5.1 Dual norms 81 2.5.2 Dual cones 88 2.6 Separating and supporting hyperplanes 93 2.6.1 Separating hyperplane theorem 93 2.6.2 Supporting hyperplanes 96 2.7 Summary and discussion 99 3: Convex Functions 100 3.1 Basic properties and examples of convex functions 100 3.1.1 Definition and fundamental properties 100 3.1.2 First-order condition 106 3.1.3 Second-order condition 110 3.1.4 Examples 111 3.1.5 Epigraph 116 3.1.6 Jensen’s inequality 120 3.2 Convexity preserving operations 123 3.2.1 Nonnegative weighted sum 123 3.2.2 Composition with affine mapping 123 3.2.3 Composition (scalar) 124 3.2.4 Pointwise maximum and supremum 125 3.2.5 Pointwise minimum and infimum 128 3.2.6 Perspective of a function 130 3.3 Quasiconvex functions 132 3.3.1 Definition and examples 132 3.3.2 Modified Jensen’s inequality 137 3.3.3 First-order condition 138 3.3.4 Second-order condition 140 3.4 Monotonicity on generalized inequalities 142 3.5 Convexity on generalized inequalities 144 3.6 Summary and discussion 148 4: Convex Optimization Problems 150 4.1 Optimization problems in a standard form 151 4.1.1 Some terminologies 151 4.1.2 Optimal value and solution 151 4.1.3 Equivalent problems and feasibility problem 153 4.2 Convex optimization problems 154 4.2.1 Global optimality 155 4.2.2 An optimality criterion 156 4.3 Equivalent representations and transforms 166 4.3.1 Equivalent problem: Epigraph form 166 4.3.2 Equivalent problem: Equality constraint elimination 167 4.3.3 Equivalent problem: Function transformation 167 4.3.4 Equivalent problem: Change of variables 171 4.3.5 Reformulation of complex-variable problems 173 4.4 Convex problems with generalized inequalities 178 4.4.1 Convex problems with generalized inequalitiy constraints 178 4.4.2 Vector optimization 179 4.5 Quasiconvex optimization 187 4.6 Block successive upper bound minimization 191 4.6.1 Stationary point 191 4.6.2 BSUM 193 4.7 Successive convex approximation 197 4.8 Summary and discussion 199 5: Geometric Programming 202 5.1 Some basics 202 5.2 Geometric program (GP) 203 5.3 GP in a convex form 203 5.4 Condensation method 205 5.4.1 Successive GP approximation 206 5.4.2 Physical-layer secret communications 208 5.5 Summary and discussion 208 6: Linear Programming and Quadratic Programming 220 6.1 Linear program (LP) 220 6.2 Examples using LP 220 6.2.1 Diet problem 220 6.2.2 Chebyshev center 222 6.2.3 l∞-norm approximation 223 6.2.4 l1-norm approximation 224 6.2.5 Maximization/minimization of matrix determinant 224 6.3 Applications in blind source separation using LP/convex geometry 225 6.3.1 nBSS of dependent sources using LP 225 6.3.2 Hyperspectral unmixing using LP 230 6.3.3 Hyperspectral unmixing by simplex geometry 235 6.4 Quadratic program (QP) 248 6.5 Applications of QP and convex geometry in hyperspectral image anal-ysis 250 6.5.1 GENE-CH algorithm for endmember number estimation 252 6.5.2 GENE-AH algorithm for endmember number estimation 254 6.6 Quadratically constrained QP (QCQP) 257 6.7 Applications of QP and QCQP in beamformer design 258 6.7.1 Receive beamforming: Average sidelobe energy minimization 258 6.7.2 Receive beamforming: Worst-case sidelobe energy minimization 260 6.7.3 Transmit beamforming in cognitive radio using QCQP 262 6.8 Summary and discussion 263 7: Second-order Cone Programming 266 7.1 Second-order cone program (SOCP) 266 7.2 Robust linear program 267 7.3 Chance constrained linear program 268 7.4 Robust least-squares approximation 269 7.5 Robust receive beamforming via SOCP 269 7.5.1 Minimum-variance beamformer 270 7.5.2 Robust beamforming via SOCP 271 7.6 Transmit downlink beamforming via SOCP 273 7.6.1 Power minimization beamforming 275 7.6.2 Max-Min-Fair beamforming 276 7.6.3 Multicell beamforming 277 7.6.4 Femtocell beamforming 279 7.7 Summary and discussion 281 8: Semidefinite Programming 282 8.1 Semidefinite program (SDP) 283 8.2 QCQP and SOCP as SDP via Schur complement 284 8.3 S-Procedure 285 8.4 Applications in combinatorial optimization 287 8.4.1 Boolean quadratic program (BQP) 287 8.4.2 Practical example I: MAXCUT 287 8.4.3 Practical example II: ML MIMO detection 289 8.4.4 BQP approximation by semidefinite relaxation 290 8.4.5 Practical example III: Linear fractional SDR (LFSDR) approach to noncoherent ML detection of higher-order QAM OSTBC 294 8.5 Applications in transmit beamforming 299 8.5.1 Downlink beamforming for broadcasting 299 8.5.2 Transmit beamforming in cognitive radio 301 8.5.3 Transmit beamforming in secrecy communication: Artificial noise (AN) aided approach 301 8.5.4 Worst-case robust transmit beamforming: Single-cell MISO sce-nario 306 8.5.5 Worst-case robust transmit beamforming: Multicell MISO sce-nario 310 8.5.6 Outage constrained coordinated beamforming for MISO interfer-ence channel: Part I (centralized algorithm) 315 8.5.7 Outage constrained coordinated beamforming for MISO interfer-ence channel: Part II (efficient algorithms using BSUM) 324 8.5.8 Outage constrained robust transmit beamforming: Single-cell MISO scenario 331 8.5.9 Outage constrained robust transmit beamforming: Multicell MISO scenario 338 8.6 Summary and discussion 345 9: Duality 350 9.1 Lagrange dual function and conjugate function 351 9.1.1 Lagrange dual function 351 9.1.2 Conjugate function 354 9.1.3 Relationship between Lagrange dual function and conjugate function 358 9.2 Lagrange dual problem 359 9.3 Strong duality 368 9.3.1 Slater’s condition 368 9.3.2 S-Lemma 375 9.4 Implications of strong duality 378 9.4.1 Max-min characterization of weak and strong duality 378 9.4.2 Certificate of suboptimality 379 9.4.3 Complementary slackness 379 9.5 Karush–Kuhn–Tucker (KKT) optimality conditions 380 9.6 Lagrange dual optimization 390 9.7 Alternating direction method of multipliers (ADMM) 395 9.8 Duality of problems with generalized inequalities 398 9.8.1 Lagrange dual and KKT conditions 398 9.8.2 Lagrange dual of cone program and KKT conditions 401 9.8.3 Lagrange dual of SDP and KKT conditions 403 9.9 Theorems of alternatives 409 9.9.1 Weak alternatives 410 9.9.2 Strong alternatives 412 9.9.3 Proof of S-procedure 416 9.10 Summary and discussion 418 10: Interior-point Methods 420 10.1 Inequality and equality constrained convex problems 420 10.2 Newton’s method and barrier function 422 10.2.1 Newton’s method for equality constrained problems 422 10.2.2 Barrier function 425 10.3 Central path 429 10.4 Barrier method 431 10.5 Primal-dual interior-point method 434 10.5.1 Primal-dual search direction 435 10.5.2 Surrogate duality gap 436 10.5.3 Primal-dual interior-point algorithm 436 10.5.4 Primal-dual interior-point method for solving SDP 439 10.6 Summary and discussion 444 A Appendix: Convex Optimization Solvers 446 A.1 SeDuMi 446 A.2 CVX 447 A.3 Finite impulse response (FIR) filter design 448 A.3.1 Problem formulation 449 A.3.2 Problem implementation using SeDuMi 450 A.3.3 Problem implementation using CVX 451 A.4 Conclusion 452 Index 454 Content: *Preface *Chapter 1: Mathematical Background *Chapter 2: Convex Sets *Chapter 3: Convex Functions *Chapter 4: Convex Optimization Problems *Chapter 5: Geometric Programming *Chapter 6: Linear Programming and Quadratic Programming *Chapter 7: Second-order Cone Programming *Chapter 8: Semidefinite Programming *Chapter 9: Duality *Chapter 10: Interior-point Methods *Appendix: Convex Optimization Solvers