凸优化_王书宁译

IsBN978-7-302-29756·7 清华大学出版社数字出版网站 WQBoyklER www.wqbook.com 978730229756% 定价:99.00元 信息技术和电气工程学科国际知名教材中译本系列 ConvexOptimization 凸优化 StephenBoydLievenVandenberghe 王书宁许鋆黄晓霖译 清华大学出版社 北京 北京市版杈局著怍杈合同登记号图字:01-20093869 AuthorizediranslationfromtheEnglishlanguageedition,entitledConvexOptimization,ISBN978-0-521 83378-3byStephenBoydandLievenVandenberghe,publishedbyCambridgeUniversityPress,copyright 2004 AllRightsReserved.Nopartofthisbookmaybereproducedortransmittedinanyformorbyanymeans, electronicormechanical,includingphotocopying,recordingorbyanyinformationstorageretrievalsystem, withoutpermissionfromCambridgeUniversityPress,In SimplifiedChineselanguageeditionpublishedbyTSINGHUAUNIVERSITYPRESSCopyright2012. 本书中文简体版由剑桥大学出版社授权给清华大学出版社出版发行。未经许可,不得以任何方式复制或 抄袭本书的任何部分 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:0106278298913701121933 图书在版编目(CIP)数据 凸优化八(美)鲍德(Boyd,S.)等著;王书宁等译.一北京:清华大学出版社,2013.1 信息技术和电气工程学科国际知名教材中译本系列 书名原文:ConvexOptimization ISBN978-7-302-29756-7 Ⅰ.①凸…Ⅱ.①鲍…②王…Ⅲ,①凸分析一教材Ⅳ.①O174.13 中国版本图书馆CIP数据核字(2012)第190148号 责任编辑;王一玲 封面设计:常雪影 责任校对:李建庄 责任印制:李红英 出版发行;清华大学出版社 wtih:http://www.tup.comch,http://www.wybook.corm 质量反馈:0106272015,zhiliang@up,tsinghua,edu.c%是 地址:北京清华大学学研大厦A座 邮蝙:1 0084 社总机:010-62770175 邮购 10-62786544 投稿与读者服务:010-62776969,ServiCe@tup.tsinghua 课件下载:htp://www.tup.com.cn,010-62795954 印装者:清华大学印刷厂 经销:全国新华书店 开本;185mm×260mm印张:44.75 字数:1115千字 版次:2013年1月第1版 印次:2013年1月第1次印刷 印数:1~3000 定价:99.00元 产品编号:03184901 译者序 本书由美国斯坦福大学StephenBoyd教授和加州大学洛杉矶分校LievenVanden berghe教授合著,从理论、应用和算法三个方面系统地介绍凸优化内容。 凸优化在数学规划领域具有非常重要的地位。从应用角度看,现有算法和常规计 算能力已足以可靠地求解大规模凸优化问题,一旦将一个实际问题表述为凸优化问题, 大体上意味蒼相应问题已经得到彻底解决,这是非凸的优化问题所不具有的性质。从 理论角度看,用凸优化模型对一般性非线性优化模型进行局部逼近,始终是研究非线性 规划问题的主要途径,因此,通过学习凸优化理论,可以直接或间接地掌握数学规划领 域几乎所有重要的理论结果。由于上述原因,对于涉足优化领域的人员,无论是理论研 究还是实际应用,都应该对凸优化理论和方法有一定程度的了解。 本书内容非常丰富。理论部分由4章构成,不仅涵盖了凸优化的所有基本概念和主 要结果,还详细介绍了几类基本的凸优化问题以及将特殊的优化问题表述为凸优化 问题的变换方法,这些内容对灵活运用凸优化知识解决实际问题非常有用。应用部分 由3章构成,分别介绍凸优化在解决逼近与拟合、统计估计和几何关系分析这三类实际 问题中的应用。算法部分也由3章构成,依次介绍求解无约束凸优化模型、等式约束凸 优化模型以及包含不等式约束的凸优化模型的经典数值方法,以及如何利用凸优化 理论分析这些方法的收敛性质。通过阅读本书,能够对凸优化理论和方法建立完整的 认识。 本书对每章内容都配备了大量习题,因此也非常适合用作教科书。实际上,该书多 年来已在美国多所大学用于课堂教学,近两年也在清华大学自动化系用作相关研究生 课程的主要教材。 本书前言及第1,3,5,7章由许鋆翻译;第2,4,6,8章由黄晓霖翻译;第9~11章及 附录部分由王书宁翻译。全书由王书宁定稿。 感谢StephenBoyd教授提供本书英文版本的电子文件,为翻译本书提供了极大的 便利。 译者 2012年10月 前言 本书研究优化问题的一个重要分支:凸优化。事实上,最小二乘以及线性规划问题 都属于凸优化问题。众所周知,关于最小二乘和线性规划问题的理论相当成熟,这两个 问题出现在很多应用领域,均能很快地进行数值求解。本书的基本观点是,除了这两个 问题以外,还有很多凸优化问题亦是如此。 尽管凸优化的研究已经持续了一个世纪左右,然而,最近一些相关的研究成果使得 这一问题重新引起人们的关注。这当中首推对内点法的重新认识。内点法于20世纪80 年代提出,本是用以求解线性规划问题,但是最近人们认识到,它亦可以被应用于求解 凸优化问题。这些新的方法使得我们可以如求解线性规划一样有效求解一些特殊的凸 优化问题,如半定规划以及二阶锥规划问题。 第二个相关的研究成果是人们发现凸优化问题(不仅仅是最小二乘和线性规划)在 实践中的应用远远超乎人们的想象。从20世纪90年代开始,凸优化即被用在自动控 制系统、估计和信号处理、通信网络、电路设计、数据分析及建模、统计和金融方面。此 外,在组合优化以及全局优化方面,凸优化经常被用来估计最优值的界以及给出近似 解。我们相信,还有很多其他凸优化的应用领域正在等待着人们去发现。 发现某个问题是凸优化问题或能将其描述为凸优化问题将会大有裨益。最本质的 好处就是对此问题可以用内点法或者其他凸优化方法进行可靠且迅速的求解。这些求 解方法可靠,足以嵌入于电脑辅助设计或分析工具,甚至用于实时响应系统或者自动控 制系统。此外,将某个问题描述为凸优化问题还具有理论或概念上的优越性。例如,相 应的对偶问题经常可以基于原问题给出有意义的解释,有时可导向有效的或分布式的 求解原问题的方法。 我们认为,凸优化非常重要,任何从事计算数学的人至少需要对其有一定的了解。 在我们看来,凸优化理所当然地是继近代线性代数(如最小二乘,奇异值)和线性规划 之后的又一重要领域。 本书目的 对于很多一般性的优化方法,通常人们用它直截了当地试解待解的问题。凸优化就 与此不同,只有我们知道待解的问题是凸的,它的优越性才可能完整地体现出来。 当 然,很多优化问题是非凸的,判断某个问题是否凸或者将某个问题表述为凸优化的形式 是比较困难的。 本书的主要目的是帮助读者掌握应用凸优化方法的相关知识,即判断、描述 刊 以及求解凸优化问题的技能和背景知识。 获取凸优化的相关应用知识对数学要求较高,对于主要关注应用的读者更是如此。 根据我们的经验,对于电气工程以及计算科学的研究生来说,在这方面的投入会获得 良好的、有时是丰厚的回报。 在此之前,有不少关于线性规划以及一般的非线性规划的书籍,这些书籍的侧重点 在于问题的描述,建模以及应用。另有一些书籍主要讨论凸优化的理论,内点法以及复 杂度分析。本书介于二者之间,介绍一般的凸优化理论,侧重于问题描述以及建模。 我们也要指出本书并不追求什么。它不是一本侧重于凸分析或者凸优化的数学知 识的教材,已经有一些别的书籍涵盖了这些内容。此外,本书也不是凸优化算法的一个 综述。我们只是挑选了一些较好的算法,介绍其简化了的或者是典型的形式(但是它们 在实践中确实能发挥作用)。本书也不试图涵盖求解凸问题的内点法(或其他方法)的 最新发展动态。虽然本书所提供的一些数值仿真实例经过了高度简化,但是我们认为, 它们能够适应一些潜在用户的应用要求。并且,对于一些凸优化算法,本书详细地探讨 了如何利用问题的结构使得求解更为迅速。对于所描述算法的复杂性理论,我们也只 是以一种简单方式进行了介绍。然而,对于内点法的自和谐和复杂度分析的重要思想我 们都有一定的介绍。 读者范围 对于在工作中需要用到数学优化,或者更一般地说,用到计算数学的科研人员、科 学家以及工程师,本书较为适合。这些人群包括直接从事优化或者运筹学的科技工作 者,亦包括一些工作在其他科学和工程领域但是需要借助数学优化工具的科技工作者, 这些领域包括计算科学、经济学、金融、统计学、数据挖掘等。本书主要针对后者,即 可能使用凸优化的科技工作者,而不是针对人数相对少很多的凸优化领域的专家。 在阅读本书之前,读者只需要掌握现代微积分和线性代数的相关知识。如果读者对 些基本的数学分析知识(如范数、收敛性、初等拓扑学)和基本的概率论有一定的了 解,应能较好地理解本书的所有论证和讨论。当然,我们希望即使没有学过数学分析和 概率论的读者也能够理解本书所有的基本思想和要点。此外,本书的正文以及附录部 分包含了数值计算和优化方法需要的所有辅助资料,因此,读者并不需要事先具备这些 知识。 使用本书作为教材 我们希望本书能够在不同的课程中作为基本教材或者是参考教材发挥它的作用 从1995年开始,我们即在Stanford和UCLA的一些研究生课程中使用本书的初稿, 这些课程包括线性优化、非线性优化和凸优化(偏工程应用)。我们的经验表明,用 个研究生课程的四分之一时间即可以粗略讲授完本书的大部分内容,如果用一个满学 前言 期的课程时间,讲课进度就可以比较从容,也可以增加更多的例子,并且可以更加详尽 地讨论有关理论。若能用两个四分之一的研究生课程时间,就可以对线性规划和二次规 划(对于以应用为目的的学生极为重要)这些基本内容进行较广泛的讨论,或者对学生 布置更多的大练习。 本书可以作为线性优化、非线性优化等基础课的参考读物。对于涉及凸优化的应用 领域如控制系统等课程,本书亦可以作为替换教材。此外,对于凸优化方面更关注理论 的课程,本书可以作为辅助教材,它提供了一些简单的实际例子。 致谢 本书的完成历时将近十年。这十年中,我们收到了不少关于本书的反馈以及建议, 这些建议来自我们的研究生、我们课程上的学生以及我们在Stanford和UCLA的同 事等。篇幅有限,我们无法一一表达我们的感谢,仅列出下述名单,表达我们诚挚的谢 RoA.Aggarwal,VBalakrishnan,A.Bernard,BBray,R.Cottle,Ad'Aspremont Dahl,Dattorro,D.Donoho,J.Doyle,L.ElGhaoui,P.Glynn,M.Grant,A Hansson,T.Hastie,ALewis,M.Lobo,Z.-Q.Luo,M.Mesbahi,W.Naylor,PParrilo, I.Pressman,R.Tibshirani,B.Vanroy,L.Xiao和Y.Ye,我们要感谢J.Alden以及 A.d'Aspremont在时间序列分析654中所提供的例子,655中的界定顾客喜好的 例子也由他们提供。此外,感谢P.Parrilo对习题44和习题4.56所提供的建议。 我们还要特别感谢两个人。Arkadinermirovsk引发了我们对凸优化的兴趣并且鼓 励我们撰写本书。而Kishanbahati对本书的完成也发挥了极大的作用。早在1994年 的时候,他就鼓励我们以凸优化在实际工程中的应用为题申请美国科学基金会的科研 课程基金,本书可以认为是当年的基金成果,虽然在时间上可能有所滞后。 Stephenboyd Stanford,California Lievenvandenberghe LosAngeles,California 9003年7月 目录 1引言 1.1数学优化 12最小二乘和线性规划 13凸优化 6 14非线性优化 15本书主要内容 16符号 12 参考文献 13 理论 17 2凸集 19 21仿射集合和凸集 19 22重要的例子 24 23保凸运算 ,,31 24广义不等式。.. 38 2.5分离与支撑超平面 42 2.6对偶锥与广义不等式 46 参考文献 52 习题 3凸函数 61 31基本性质和例子 El 32保凸运算 3.3共轭函数 85 34拟凸函数 90