第1页 / 共728页
第2页 / 共728页
第3页 / 共728页
第4页 / 共728页
第5页 / 共728页
第6页 / 共728页
第7页 / 共728页
第8页 / 共728页
斯塔福大学凸优化理论入门教材 Convex Optimization.pdf
Convex Optimization
Stephen Boyd
Department of Electrical Engineering
Stanford University
Lieven Vandenberghe
Electrical Engineering Department
University of California, Los Angeles
cambridge university press
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, S˜ao Paolo, Delhi
Cambridge University Press
The Edinburgh Building, Cambridge, CB2 8RU, UK
Published in the United States of America by Cambridge University Press, New York
http://www.cambridge.org
Information on this title: www.cambridge.org/9780521833783
c Cambridge University Press 2004
This publication is in copyright. Subject to statutory exception
and to the provisions of relevant collective licensing agreements,
no reproduction of any part may take place without
the written permission of Cambridge University Press.
First published 2004
Seventh printing with corrections 2009
Printed in the United Kingdom at the University Press, Cambridge
A catalogue record for this publication is available from the British Library
Library of Congress Cataloguing-in-Publication data
Boyd, Stephen P.
Convex Optimization / Stephen Boyd & Lieven Vandenberghe
p. cm.
Includes bibliographical references and index.
ISBN 0 521 83378 7
1. Mathematical optimization. 2. Convex functions. I. Vandenberghe, Lieven. II. Title.
QA402.5.B69 2004
519.6–dc22
2003063284
ISBN 978-0-521-83378-3 hardback
Cambridge University Press has no responsiblity for the persistency or accuracy of URLs
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
For
Anna, Nicholas, and Nora
Dani¨el and Margriet
Contents
Preface
xi
1 Introduction
1
1
1.1 Mathematical optimization . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2 Least-squares and linear programming . . . . . . . . . . . . . . . . . .
7
1.3 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.4 Nonlinear optimization . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
I Theory
19
2 Convex sets
21
2.1 Affine and convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Some important examples . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 35
2.4 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5 Separating and supporting hyperplanes . . . . . . . . . . . . . . . . . . 46
2.6 Dual cones and generalized inequalities . . . . . . . . . . . . . . . . . . 51
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3 Convex functions
67
. . . . . . . . . . . . . . . . . . . . . . 67
3.1 Basic properties and examples
3.2 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 79
3.3 The conjugate function . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.4 Quasiconvex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
. . . . . . . . . . . . . . . . . . 104
3.5 Log-concave and log-convex functions
. . . . . . . . . . . . 108
3.6 Convexity with respect to generalized inequalities
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
viii
Contents
4 Convex optimization problems
127
. . . . . . . . . . . . . . . . . . . . . . . . . . 127
4.1 Optimization problems
4.2 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.3 Linear optimization problems . . . . . . . . . . . . . . . . . . . . . . . 146
4.4 Quadratic optimization problems . . . . . . . . . . . . . . . . . . . . . 152
4.5 Geometric programming . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.6 Generalized inequality constraints . . . . . . . . . . . . . . . . . . . . . 167
4.7 Vector optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
5 Duality
215
5.1 The Lagrange dual function . . . . . . . . . . . . . . . . . . . . . . . . 215
5.2 The Lagrange dual problem . . . . . . . . . . . . . . . . . . . . . . . . 223
5.3 Geometric interpretation . . . . . . . . . . . . . . . . . . . . . . . . . 232
5.4 Saddle-point interpretation . . . . . . . . . . . . . . . . . . . . . . . . 237
5.5 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
. . . . . . . . . . . . . . . . . . . 249
5.6 Perturbation and sensitivity analysis
5.7 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
. . . . . . . . . . . . . . . . . . . . . . . . . 258
5.8 Theorems of alternatives
5.9 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 264
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
II Applications
289
6 Approximation and fitting
291
6.1 Norm approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
. . . . . . . . . . . . . . . . . . . . . . . . . . . 302
6.2 Least-norm problems
6.3 Regularized approximation . . . . . . . . . . . . . . . . . . . . . . . . 305
6.4 Robust approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
6.5 Function fitting and interpolation . . . . . . . . . . . . . . . . . . . . . 324
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
7 Statistical estimation
351
7.1 Parametric distribution estimation . . . . . . . . . . . . . . . . . . . . 351
7.2 Nonparametric distribution estimation . . . . . . . . . . . . . . . . . . 359
7.3 Optimal detector design and hypothesis testing . . . . . . . . . . . . . 364
. . . . . . . . . . . . . . . . . . . . . 374
7.4 Chebyshev and Chernoff bounds
7.5 Experiment design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393
Contents
ix
8 Geometric problems
397
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
8.1 Projection on a set
8.2 Distance between sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
8.3 Euclidean distance and angle problems . . . . . . . . . . . . . . . . . . 405
. . . . . . . . . . . . . . . . . . . . . . . . 410
8.4 Extremal volume ellipsoids
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416
8.5 Centering
8.6 Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422
8.7 Placement and location . . . . . . . . . . . . . . . . . . . . . . . . . . 432
8.8 Floor planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
III Algorithms
455
9 Unconstrained minimization
457
. . . . . . . . . . . . . . . . . . 457
9.1 Unconstrained minimization problems
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
9.2 Descent methods
9.3 Gradient descent method . . . . . . . . . . . . . . . . . . . . . . . . . 466
9.4 Steepest descent method . . . . . . . . . . . . . . . . . . . . . . . . . 475
9.5 Newton’s method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
9.6 Self-concordance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496
Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508
9.7
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
10 Equality constrained minimization
521
. . . . . . . . . . . . . . . 521
10.1 Equality constrained minimization problems
10.2 Newton’s method with equality constraints . . . . . . . . . . . . . . . . 525
10.3 Infeasible start Newton method . . . . . . . . . . . . . . . . . . . . . . 531
10.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
11 Interior-point methods
561
. . . . . . . . . . . . . . 561
11.1 Inequality constrained minimization problems
11.2 Logarithmic barrier function and central path . . . . . . . . . . . . . . 562
11.3 The barrier method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568
11.4 Feasibility and phase I methods . . . . . . . . . . . . . . . . . . . . . . 579
11.5 Complexity analysis via self-concordance . . . . . . . . . . . . . . . . . 585
. . . . . . . . . . . . . . . . . . 596
11.6 Problems with generalized inequalities
11.7 Primal-dual interior-point methods . . . . . . . . . . . . . . . . . . . . 609
11.8 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623
x
Appendices
Contents
631
A Mathematical background
633
A.1 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
A.2 Analysis
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
A.3 Functions
A.4 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
A.5 Linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652
B Problems involving two quadratic functions
653
B.1 Single constraint quadratic optimization . . . . . . . . . . . . . . . . . 653
B.2 The S-procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655
B.3 The field of values of two symmetric matrices . . . . . . . . . . . . . . 656
B.4 Proofs of the strong duality results . . . . . . . . . . . . . . . . . . . . 657
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659
C Numerical linear algebra background
661
C.1 Matrix structure and algorithm complexity . . . . . . . . . . . . . . . . 661
C.2 Solving linear equations with factored matrices . . . . . . . . . . . . . . 664
C.3 LU, Cholesky, and LDLT factorization . . . . . . . . . . . . . . . . . . 668
C.4 Block elimination and Schur complements . . . . . . . . . . . . . . . . 672
C.5 Solving underdetermined linear equations . . . . . . . . . . . . . . . . . 681
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684
References
Notation
Index
685
697
701
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
