信息技术和电气工程学科国际知名教材中译本系列 凸优化 Stephen Boyd Lieven Vandenberghe 著 王书宁许鋆黄晓霖译 清华大学出版社 北京
北京市版权局著作权合同登记号图字 :01-2009-3869 Authorized translation from the English language edition, entitled Convex Optimization, ISBN 978-0521-83378-3 by Stephen Boyd and Lieven Vandenberghe, published by Cambridge University Press, copyright 2004. All Rights Reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Cambridge University Press, Inc. Simplified Chinese language edition published by TSINGHUA UNIVERSITY PRESS Copyright 2012. 本书中文简体版由剑桥大学出版社授权给清华大学出版社出版发行 未经许可, 不得以任何方式复制或抄袭本书的任何部分 本书封面贴有清华大学出版社防伪标签, 无标签者不得销售 版权所有, 侵权必究 侵权举报电话 :010-62782989 13701121933 图书在版编目 (CIP) 数据 凸优化 /( 美 ) 鲍德 (Boyd, S.) 等著 ; 王书宁等译. 北京 : 清华大学出版社, 2013.1 ( 信息技术和电气工程学科国际知名教材中译本系列 ) 书名原文 : Convex Optimization ISBN 978-7-302-29756-7 Ⅰ. 1 凸 Ⅱ. 1 鲍 2 王 Ⅲ. 1 凸分析 - 教材 Ⅳ. 1 O174.13 中国版本图书馆 CIP 数据核字 (2012) 第 190148 号 责任编辑 : 王一玲责任校对 : 责任印制 : 出版发行 : 清华大学出版社地址 : 北京清华大学学研大厦 A 座 http://www.tup.com.cn 邮编 :100084 社总机 :010 62770175 邮购 :010 62786544 投稿与读者服务 :010 62776969, c-service@tup. tsinghua. edu. cn 质量反馈 :010 62772015, zhiliang@tup tsinghua. edu. cn 印刷者 : 装订者 : 经 销 : 全国新华书店 开 本 :185 260 印张 :44.75 插页 : 字数 :1115 千字 版 次 :2013 年 1 月第 1 版 印次 :2013 年 1 月第 1 次印刷 印 数 :000 赵 定 价 :0.00 元 本书如存在文字不清 漏印 缺页 倒页 脱页等印装质量问题, 请与清华大学出版社出版部联系调换 联系电话 :010 62770177 转 3103 产品编号 :031849-01
Stephen Boyd Lieven Vandenberghe 4 3 3 1 3 5 7 2 4 6 8 9 11 Stephen Boyd 2012 10
20 80 20 90
iv 1995 Stanford UCLA
v Stanford UCLA A. Aggarwal, V. Balakrishnan, A. Bernard, B. Bray, R. Cottle, A. d Aspremont, J. Dahl, J. Dattorro, D. Donoho, J. Doyle, L. El Ghaoui, P. Glynn, M. Grant, A. Hansson, T. Hastie, A. Lewis, M. Lobo, Z.-Q. Luo, M. Mesbahi, W. Naylor, P. Parrilo, I. Pressman, R. Tibshirani, B. Van Roy, L. Xiao Y. Ye. J. Jalden A. d Aspremont 6.5.4 6.5.5 P. Parrilo 4.4 4.56 Arkadi Nemirovski Kishan Baheti 1994 Stephen Boyd Lieven Vandenberghe Stanford, California Los Angeles, California 2003 7
1 1 1.1................................... 1 1.2............................. 3 1.3..................................... 6 1.4.................................. 8 1.5................................. 10 1.6...................................... 12...................................... 13 I 17 2 19 2.1................................ 19 2.2.................................. 24 2.3................................... 31 2.4.................................. 38 2.5.............................. 42 2.6............................. 46...................................... 52......................................... 53 3 61 3.1................................ 61 3.2................................... 73 3.3................................... 85 3.4................................... 90
viii 3.5 - -.......................... 98 3.6............................ 102...................................... 106......................................... 106 4 121 4.1................................... 121 4.2..................................... 130 4.3................................. 139 4.4................................. 145 4.5................................... 153 4.6................................ 160 4.7................................... 167...................................... 179......................................... 180 5 207 5.1 Lagrange.............................. 207 5.2 Lagrange.............................. 215 5.3................................... 224 5.4................................... 229 5.5.................................. 233 5.6.............................. 241 5.7...................................... 245 5.8................................... 250 5.9.................................. 256...................................... 264......................................... 265 II 283 6 285 6.1................................... 285 6.2................................. 295 6.3.................................. 297
ix 6.4................................... 307 6.5................................ 314...................................... 329......................................... 329 7 337 7.1................................. 337 7.2................................ 345 7.3......................... 350 7.4 Chebyshev Chernoff......................... 360 7.5................................... 370...................................... 376......................................... 377 8 381 8.1.................................. 381 8.2................................. 386 8.3 Euclid............................ 389 8.4................................. 394 8.5...................................... 400 8.6...................................... 406 8.7.................................. 414 8.8................................... 420...................................... 426......................................... 427 III 435 9 437 9.1................................ 437 9.2................................... 443 9.3................................. 445 9.4................................. 454 9.5 Newton................................. 461 9.6..................................... 473
x 9.7...................................... 484...................................... 489......................................... 489 10 497 10.1.............................. 497 10.2 Newton.......................... 501 10.3 Newton....................... 507 10.4..................................... 520...................................... 531......................................... 531 11 535 11.1.......................... 535 11.2.......................... 536 11.3................................... 542 11.4 1............................ 552 11.5......................... 558 11.6............................... 568 11.7................................ 580 11.8..................................... 587...................................... 592......................................... 593 603 A 605 A.1...................................... 605 A.2...................................... 609 A.3...................................... 610 A.4...................................... 612 A.5................................... 617...................................... 623
xi B 624 B.1................................ 624 B.2 S-..................................... 626 B.3............................. 627 B.4.............................. 629...................................... 630 C 631 C.1............................ 631 C.2................... 634 C.3 LU Cholesky LDL T....................... 637 C.4 Schur............................. 642 C.5............................ 650...................................... 653 654 670 673
1 1.1 minimize f 0 (x) subject to f i (x) b i, i = 1,, m. (1.1) x = (x 1,, x n ) f 0 : R n R f i : R n R i = 1,, m b 1,, b m x f 1 (z) b 1,, f m (z) b m z f 0 (z) f 0 (x ) x (1.1) (1.1) f 0,, f m x, y R n α, β R f i (αx + βy) = αf i (x) + βf i (y), (1.2) x, y R n α, β R α + β = 1 α 0 β 0 f i (αx + βy) αf i (x) + βf i (y). (1.3) (1.3) (1.2) α β
2 1 1.1.1 (1.1) R n x f i (x) b i x f 0 (x) x f 0 (x) x (1.1) n x i i x R n (1.1) (1.1) (1.1)
1.2 3 1.1.2 20 40 (1.1) (1.1) 1.4 1.2 4 1.2 4 1.2.1 m = 0 a T i x b i k minimize f 0 (x) = Ax b 2 2 = (a T i x b i ) 2. (1.4) A R k n k n a T i A x R n (1.4) i=1
4 1 (A T A)x = A T b, x = (A T A) 1 A T b n 2 k A A A kn n 2 k x k w i (a T i x b i ) 2, i=1 w 1,, w k w i a T i x b i x
1.2 5 k n (a T i x b i ) 2 + ρ x 2 i, i=1 i=1 ρ > 0 x ρ n x 2 i x 6 7 1.2.2 minimize c T x subject to a T i x b (1.5) i, i = 1,, m. c, a 1,, a m R n b 1,, b m R Dantzig n 2 m m n i=1
6 1 (1.5) 4 Chebyshev minimize max i=1,,k a T i x b i. (1.6) x R n a 1,, a k R n b 1,, b k R (1.4) a T i x b i a T i x b i Chebyshev a T i x b i Chebyshev (1.6) (1.4) Chebyshev (1.6) minimize t subject to a T i x t b i, i = 1,, k (1.7) a T i x t b i, i = 1,, k, x R n t R 6 Chebyshev Chebyshev (1.6) Chebyshev (1.6) 1.3 minimize f 0 (x) (1.8) subject to f i (x) b i, i = 1,, m, f 0,, f m : R n R x, y R n α, β R α + β = 1 α 0 β 0
1.3 7 f i (αx + βy) αf i (x) + βf i (y). (1.4) (1.5) (1.8) 1.3.1 11 10 100 (1.8) max{n 3, n 2 m, F }, F f 0,, f m 4 1.3.2
8 1 1.4 (1.1) 10 1.4.1
1.4 9 1.4.2 (1.1) n m (1.1) 1.4.3
10 1 6 11.23 Lagrange Lagrange 5 1.5 1.5.1 I I 2 3 4