Over the past two decades there have been significant advances in the field of optimization. In particular, convex optimization has emerged as a powerful signal processing tool, and the variety of applications continues to grow rapidly. This book, written by a team of leading experts, sets out the theoretical underpinnings of the subject and provides tutorials on a wide range of convex optimization applications. Emphasis throughout is on cutting-edge research and on formulating problems in convex form, making this an ideal textbook for advanced graduate courses and a useful self-study guide. Topics covered range from automatic code generation, graphical models, and gradient-based algorithms for signal recovery, to semidefinite programming (SDP) relaxation and radar waveform design via SDP. It also includes blind source separation for image processing, robust broadband beamforming, distributed multi-agent optimization for networked systems, cognitive radio systems via game theory, and the variational inequality approach for Nash equilibrium solutions.
Author(s): Daniel P. Palomar, Yonina C. Eldar
Edition: 1
Year: 2010
Language: English
Pages: 512
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
List of contributors......Page 11
Preface......Page 13
1.1.1 Advisory optimization......Page 17
1.1.2 Embedded optimization......Page 18
1.1.3 Convex optimization......Page 20
Signal processing, communications, and networking......Page 21
1.2.1 Problem families and instances......Page 22
1.2.3 Specification languages......Page 24
1.2.4 Parser-solvers......Page 25
1.2.5 Code generators......Page 26
1.2.6 Example from CVXMOD......Page 27
Feedback control......Page 28
1.3.1 Adaptive filtering and equalization......Page 29
1.3.2 Optimal order execution......Page 30
1.3.3 Sliding-window smoothing......Page 31
1.3.4 Sliding-window estimation......Page 32
1.3.6 Model predictive control......Page 33
1.3.7 Optimal network flow rates......Page 34
1.3.8 Optimal power generation and distribution......Page 35
1.3.9 Processor-speed scheduling......Page 37
Guaranteed-run time bounds......Page 38
Variable ranges can be determined......Page 39
1.4.4 Solving systems with KKT-like structure......Page 40
1.5.1 Custom KKT solver......Page 42
1.5.2 Additional optimizations......Page 43
1.6.1 Algorithm......Page 44
1.7 Numerical examples......Page 45
1.7.2 Optimal order execution......Page 46
1.7.4 Real-time actuator optimization......Page 48
1.8 Summary, conclusions, and implications......Page 49
References......Page 51
2.1 Introduction......Page 58
2.2.1 Generic problem formulation......Page 59
2.2.2 Signal recovery via nonsmooth regularization......Page 60
2.3.1 The quadratic-approximation model for (M)......Page 62
2.3.2 The fixed-point approach......Page 64
The MM method for the RLS problem......Page 65
2.3.4 Fermat–Weber location problem......Page 67
2.4 Convergence results for the proximal-gradient method......Page 69
2.4.1 The prox-grad map......Page 70
2.4.2 Fundamental inequalities......Page 71
Proximal-gradient method with constant stepsize......Page 73
Proximal-gradient method with backtracking......Page 74
2.4.4 The nonconvex case......Page 76
2.5.2 A fast proximal-gradient method using two past iterations......Page 78
Fast proximal-gradient method with backtracking......Page 79
Monotone fast proximal-gradient method......Page 82
2.6.1 Problem formulation......Page 83
2.6.3 FISTA: fast ISTA......Page 84
2.6.4 Numerical examples......Page 85
2.7.1 Problem formulation......Page 87
2.7.2 TV-based denoising......Page 88
2.7.3 TV-based deblurring......Page 90
2.7.4 Numerical example......Page 92
2.8.1 Problem formulation......Page 93
2.8.2 The simple fixed-point algorithm: definition and analysis......Page 94
2.8.3 The SWLS algorithm......Page 97
2.9 Bibliographic notes......Page 99
References......Page 101
3.1 Introduction......Page 105
Notation......Page 107
3.2 Autoregressive processes......Page 108
3.2.1 Least-squares linear prediction......Page 110
3.2.2 Maximum-likelihood estimation......Page 112
3.2.3 Maximum-entropy estimation......Page 113
3.3 Autoregressive graphical models......Page 114
3.3.2 Maximum-likelihood and maximum-entropy estimation......Page 115
Exactness of the relaxation......Page 118
3.3.4 Summary......Page 119
3.4.1 Randomly generated data......Page 120
3.4.2 Model selection......Page 121
3.4.3 Air pollution data......Page 125
3.4.4 stock marketsInternational......Page 127
3.5 Conclusion......Page 129
References......Page 130
4.1 Introduction......Page 133
4.2 Nonconvex QCQPs and SDP relaxation......Page 134
4.2.1 SDP relaxation......Page 135
4.2.2 Extracting a rank-1 solution: Gaussian sampling......Page 136
4.2.3 Approximation ratio......Page 138
4.3.1 Separable homogeneous QCQPs......Page 139
4.3.2 Downlink transmit beamforming......Page 141
4.3.3 SDP relaxation for unicast transmit beamforming......Page 143
4.3.4 SDP relaxation for far-field, multicast transmit beamforming......Page 145
4.3.5 SDP relaxation for single-group, multicast transmit beamforming......Page 146
Worst-case approximation bounds......Page 147
Numerical results......Page 151
4.4 SDP relaxation for maximization homogeneous QCQPs......Page 153
4.4.1 Worst-case approximation bounds......Page 155
4.4.2 Numerical results......Page 158
4.5.1 SDP relaxation for fractional QCQPs......Page 159
Worst-case approximation bounds......Page 162
4.5.2 SDP relaxation for generalized fractional QCQPs......Page 164
Worst-case approximation bounds......Page 165
Numerical results......Page 170
4.6.1 SDP relaxation for the magnitude least-squares (MLS) problem......Page 172
4.6.2 SDP relaxation for the magnitude-squared least-squares (MSLS) problem......Page 174
4.7 Summary and discussion......Page 177
References......Page 178
5.1 Introduction......Page 182
5.2 Problem formulation......Page 185
5.3.1 The…......Page 188
5.3.2 The M = 2 case......Page 193
5.4 Extension to the QAM constellations......Page 195
A5.1 Bounding the largest singular value of an arbitrary matrix......Page 198
A5.2 The largest singular value of a complex Gaussian random matrix......Page 200
A5.3 The largest singular value of a real Gaussian random matrix......Page 202
A5.4 The squared-norm of a complex Gaussian random vector......Page 203
References......Page 205
6.1 Introduction and notation......Page 208
6.2.1 Rank-1 matrix decomposition schemes......Page 210
6.2.2 Numerical performance......Page 213
6.3 Semidefinite programming......Page 216
6.4 Quadratically constrained quadratic programming and its SDP relaxation......Page 217
6.5.1 QCQP problem with two constraints......Page 219
6.5.2 QCQP problem with three constraints......Page 222
6.5.3 QCQP problem with homogeneous functions......Page 223
6.6.1 Background......Page 224
6.6.2 System model......Page 225
6.7.1 Detection probability......Page 227
6.7.2 Doppler frequency estimation accuracy......Page 228
6.7.3 The similarity constraint......Page 229
6.8 Optimal code design......Page 230
6.9 Performance analysis......Page 234
6.10 Conclusions......Page 239
A6.1 Proof of Proposition 6.1......Page 240
A6.2.2 Feasibility of (EQPR)......Page 241
References......Page 242
7.1 Introduction......Page 245
7.2 Problem statement......Page 247
7.2.1 Assumptions......Page 251
7.3.1 Affine hull......Page 252
7.3.2 Convex hull......Page 253
7.4.1 Convex analysis of the problem, and the CAMNS criterion......Page 254
7.4.2 An alternative form of the CAMNS criterion......Page 258
7.5 Systematic linear-programming method for CAMNS......Page 261
7.6 Alternating volume-maximization heuristics for CAMNS......Page 264
7.7.1 Example of 3-source case: cell separation......Page 268
7.7.2 Example of 4-source case: ghosting effect......Page 270
7.7.3 Example of 5-source case: human face separation......Page 271
7.8 Summary and discussion......Page 273
A7.2 Proof of Proposition 7.1......Page 275
A7.4 Proofof Lemma 7.6......Page 276
A7.5 Proof of Lemma 7.7......Page 277
A7.6 Proof of Theorem 7.3......Page 278
References......Page 279
8.1 Introduction......Page 282
8.2.1 Notation......Page 284
8.2.2 Projections......Page 285
8.3 Sampling and reconstruction setup......Page 286
Subspace priors......Page 288
8.3.2 Sampling process......Page 290
Unconstrained reconstruction......Page 292
Constrained reconstruction......Page 293
8.4 Optimization methods......Page 294
Least-squares recovery......Page 296
Minimax recovery......Page 300
Least-squares recovery......Page 302
Minimax recovery......Page 304
8.6 Smoothness priors......Page 306
Least-squares approximation......Page 307
Minimax recovery......Page 309
Least-squares approximation......Page 311
Minimax-regret recovery......Page 313
8.7 Comparison of the various scenarios......Page 316
8.8 Sampling with noise......Page 318
8.8.1 Quadratic-optimization problems......Page 320
8.8.2 Minimax recovery using SDP relaxation......Page 322
8.9 Conclusions......Page 326
References......Page 327
9.1 Introduction......Page 331
9.2 Background......Page 333
9.2.1 Linearly constrained minimum variance beamformer......Page 335
9.2.2 Diagonal loading......Page 336
9.3.1 Robust beamformer with separate magnitude and phase constraints......Page 337
9.3.2 Robust beamformer with combined magnitude and phase constraints......Page 339
9.3.3 Robust beamformer with Chebychev constraints......Page 340
9.3.4 Robust beamformer without frequency discretization......Page 342
9.4 Simulations......Page 346
References......Page 353
10.1 Introduction and motivation......Page 356
10.2.1 Basic notation and terminology......Page 359
10.2.2 Primal and dual problem......Page 360
Duality gap and dual solutions......Page 361
Dual-subgradient method......Page 363
10.2.3 Distributed methods for utility-based network-resource allocation......Page 364
Boundedness of dual iterates......Page 366
Convergence-rate estimates......Page 369
10.2.5 Numerical example......Page 372
10.3.1 Problem and algorithm......Page 374
Algorithm......Page 375
Representation using transition matrices......Page 376
10.3.2 Information-exchange model......Page 377
10.3.3 Convergence of transition matrices......Page 379
10.3.4 Convergence analysis of the subgradient method......Page 381
Disagreement estimate......Page 382
Estimate for the auxiliary sequence......Page 384
Performance bound for the algorithm......Page 386
10.4.1 Quantization effects on optimization......Page 388
Performance bound for the quantized method......Page 389
10.4.2 Consensus with local constraints......Page 390
Convergence and rate of convergence results......Page 393
10.5.1 Optimization with delays......Page 394
10.5.2 Optimization with constraints......Page 395
10.6 Conclusions......Page 396
10.7 Problems......Page 397
References......Page 400
11.1 Introduction and motivation......Page 403
11.1.1 Interference constraints: individual and conservative versus global and flexible......Page 405
11.1.2 System design: a game-theoretical approach......Page 407
11.1.4 Notation......Page 408
11.2 Strategic non-cooperative games: basic solution concepts and algorithms......Page 409
Existence of a Nash solution......Page 412
Uniqueness of a Nash solution......Page 413
11.2.2 Convergence to a fixed point......Page 414
11.3 Opportunistic communications over unlicensed bands......Page 416
11.3.2 MIMO waterfilling as a projector......Page 418
Intermediate definitions......Page 420
Case of full row-rank (fat/square) channel matrices......Page 421
Case of full column-rank (tall) channel matrices......Page 423
11.3.4 Existence and uniqueness of the Nash equilibrium......Page 426
11.3.5 Distributed algorithms......Page 429
11.4.1 Game with null constraints......Page 431
Nash equilibria: existence and uniqueness......Page 432
11.4.2 Game with null constraints via virtual noise shaping......Page 434
Nash equilibria: existence and uniqueness......Page 436
Distributed algorithms......Page 438
11.4.3 Game with null and soft constraints......Page 441
Nash equilibria: existence and uniqueness......Page 443
Distributed algorithms......Page 446
11.5 Opportunistic communications under global interference constraints......Page 447
11.5.1 Equilibrium solutions: existence and uniqueness......Page 449
11.5.2 Distributed algorithms......Page 451
11.6 Conclusions......Page 454
References......Page 455
12.1 Introduction......Page 459
12.2 The Nash-equilibrium problem......Page 460
12.2.1 Review of multifunctions......Page 462
12.2.2 Connection to variational inequalities......Page 464
12.2.3 The Karush–Kuhn–Tucker conditions......Page 467
12.2.4 Regularization and single-valued formulations......Page 469
12.3 Existence theory......Page 471
12.3.1 Special cases......Page 476
12.3.2 A game with prices......Page 478
12.3.3 Jointly convex constraints......Page 480
12.3.4 The NCP approach......Page 481
12.4 Uniqueness theory......Page 482
12.4.1 A matrix-theoretic criterion......Page 484
12.5 Sensitivity analysis......Page 488
12.5.1 Local uniqueness......Page 489
12.5.2 Stability of an equilibrium......Page 492
12.6.1 Non-expansiveness of the proximal responses......Page 494
12.6.2 Descent methods for variational equilibria......Page 497
12.7 A communication game......Page 499
12.7.1 A model with QoS constraints......Page 500
12.7.2 Exogenous prices......Page 501
12.7.3 Endogenous prices......Page 504
Acknowledgments......Page 506
References......Page 507
Afterword......Page 510
Index......Page 511
