凸优化_Boyd&Vandenberghe_中文完整版

”凸优化“ 是指一种比较特殊的优化，是指求取最小值的目标函数为凸函数的一类优化问题。其中，目标函数为凸函数且定义域为凸集的优化问题称为无约束凸优化问题。而目标函数和不等式约束函数均为凸函数，等式约束函数为仿射函数，并且定义域为凸集的优化问题为约束优化问题IsBN978-7-302-29756·7清华大学出版社数字出版网站WQBoyklERwww.wqbook.com978730229756%定价:99.00元信息技术和电气工程学科国际知名教材中译本系列Convex Optimization凸优化Stephen Boyd Lieven Vandenberghe王书宁许鋆黄晓霖译清华大学出版社北京北京市版杈局著怍杈合同登记号图字:01-20093869Authorized iranslation from the English language edition, entitled Convex Optimization, ISBN 978-0-52183378-3 by Stephen Boyd and Lieven Vandenberghe, published by Cambridge University Press, copyright2004All 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, InSimplified Chinese language edition published by TSINGHUA UNIVERSITY PRESS Copyright 2012.本书中文简体版由剑桥大学出版社授权给清华大学出版社出版发行。未经许可,不得以任何方式复制或抄袭本书的任何部分本书封面贴有清华大学出版社防伪标签,无标签者不得销售。版权所有,侵权必究。侵权举报电话:0106278298913701121933图书在版编目(CIP)数据凸优化八(美)鲍德(Boyd,S.)等著;王书宁等译.一北京:清华大学出版社,2013.1信息技术和电气工程学科国际知名教材中译本系列书名原文: Convex OptimizationISBN978-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座邮蝙:10084社总机: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译者序本书由美国斯坦福大学 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年代开始,凸优化即被用在自动控制系统、估计和信号处理、通信网络、电路设计、数据分析及建模、统计和金融方面。此外,在组合优化以及全局优化方面,凸优化经常被用来估计最优值的界以及给出近似解。我们相信,还有很多其他凸优化的应用领域正在等待着人们去发现。发现某个问题是凸优化问题或能将其描述为凸优化问题将会大有裨益。最本质的好处就是对此问题可以用内点法或者其他凸优化方法进行可靠且迅速的求解。这些求解方法可靠,足以嵌入于电脑辅助设计或分析工具,甚至用于实时响应系统或者自动控制系统。此外,将某个问题描述为凸优化问题还具有理论或概念上的优越性。例如,相应的对偶问题经常可以基于原问题给出有意义的解释,有时可导向有效的或分布式的求解原问题的方法。我们认为,凸优化非常重要,任何从事计算数学的人至少需要对其有一定的了解。在我们看来,凸优化理所当然地是继近代线性代数(如最小二乘,奇异值)和线性规划之后的又一重要领域。本书目的对于很多一般性的优化方法,通常人们用它直截了当地试解待解的问题。凸优化就与此不同,只有我们知道待解的问题是凸的,它的优越性才可能完整地体现出来。当然,很多优化问题是非凸的,判断某个问题是否凸或者将某个问题表述为凸优化的形式是比较困难的。本书的主要目的是帮助读者掌握应用凸优化方法的相关知识,即判断、描述刊以及求解凸优化问题的技能和背景知识。获取凸优化的相关应用知识对数学要求较高,对于主要关注应用的读者更是如此。根据我们的经验,对于电气工程以及计算科学的研究生来说,在这方面的投入会获得良好的、有时是丰厚的回报。在此之前,有不少关于线性规划以及一般的非线性规划的书籍,这些书籍的侧重点在于问题的描述,建模以及应用。另有一些书籍主要讨论凸优化的理论,内点法以及复杂度分析。本书介于二者之间,介绍一般的凸优化理论,侧重于问题描述以及建模。我们也要指出本书并不追求什么。它不是一本侧重于凸分析或者凸优化的数学知识的教材,已经有一些别的书籍涵盖了这些内容。此外,本书也不是凸优化算法的一个综述。我们只是挑选了一些较好的算法,介绍其简化了的或者是典型的形式(但是它们在实践中确实能发挥作用)。本书也不试图涵盖求解凸问题的内点法(或其他方法)的最新发展动态。虽然本书所提供的一些数值仿真实例经过了高度简化,但是我们认为,它们能够适应一些潜在用户的应用要求。并且,对于一些凸优化算法,本书详细地探讨了如何利用问题的结构使得求解更为迅速。对于所描述算法的复杂性理论,我们也只是以一种简单方式进行了介绍。然而,对于内点法的自和谐和复杂度分析的重要思想我们都有一定的介绍。读者范围对于在工作中需要用到数学优化,或者更一般地说,用到计算数学的科研人员、科学家以及工程师,本书较为适合。这些人群包括直接从事优化或者运筹学的科技工作者,亦包括一些工作在其他科学和工程领域但是需要借助数学优化工具的科技工作者,这些领域包括计算科学、经济学、金融、统计学、数据挖掘等。本书主要针对后者,即可能使用凸优化的科技工作者,而不是针对人数相对少很多的凸优化领域的专家。在阅读本书之前,读者只需要掌握现代微积分和线性代数的相关知识。如果读者对些基本的数学分析知识(如范数、收敛性、初等拓扑学)和基本的概率论有一定的了解,应能较好地理解本书的所有论证和讨论。当然,我们希望即使没有学过数学分析和概率论的读者也能够理解本书所有的基本思想和要点。此外,本书的正文以及附录部分包含了数值计算和优化方法需要的所有辅助资料,因此,读者并不需要事先具备这些知识。使用本书作为教材我们希望本书能够在不同的课程中作为基本教材或者是参考教材发挥它的作用从1995年开始,我们即在 Stanford和UCLA的一些研究生课程中使用本书的初稿,这些课程包括线性优化、非线性优化和凸优化(偏工程应用)。我们的经验表明,用个研究生课程的四分之一时间即可以粗略讲授完本书的大部分内容,如果用一个满学前言期的课程时间,讲课进度就可以比较从容,也可以增加更多的例子,并且可以更加详尽地讨论有关理论。若能用两个四分之一的研究生课程时间,就可以对线性规划和二次规划(对于以应用为目的的学生极为重要)这些基本内容进行较广泛的讨论,或者对学生布置更多的大练习。本书可以作为线性优化、非线性优化等基础课的参考读物。对于涉及凸优化的应用领域如控制系统等课程,本书亦可以作为替换教材。此外,对于凸优化方面更关注理论的课程,本书可以作为辅助教材,它提供了一些简单的实际例子。致谢本书的完成历时将近十年。这十年中,我们收到了不少关于本书的反馈以及建议,这些建议来自我们的研究生、我们课程上的学生以及我们在 Stanford和UCLA的同事等。篇幅有限,我们无法一一表达我们的感谢,仅列出下述名单,表达我们诚挚的谢Ro A. Aggarwal, V Balakrishnan, A. Bernard, B Bray, R. Cottle, A d'AspremontDahl, Dattorro, D. Donoho, J. Doyle, L. El Ghaoui, P. Glynn, M. Grant, AHansson, 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. Alden以及A. d'Aspremont在时间序列分析654中所提供的例子,655中的界定顾客喜好的例子也由他们提供。此外,感谢P. Parrilo对习题44和习题4.56所提供的建议。我们还要特别感谢两个人。 Arkadi nermirovsk引发了我们对凸优化的兴趣并且鼓励我们撰写本书。而 Kishan bahati对本书的完成也发挥了极大的作用。早在1994年的时候,他就鼓励我们以凸优化在实际工程中的应用为题申请美国科学基金会的科研课程基金,本书可以认为是当年的基金成果,虽然在时间上可能有所滞后。Stephen boydStanford, CaliforniaLieven vandenbergheLos Angeles, California9003年7月目录1引言1.1数学优化12最小二乘和线性规划13凸优化614非线性优化15本书主要内容16符号12参考文献13理论172凸集1921仿射集合和凸集1922重要的例子2423保凸运算,,3124广义不等式。..382.5分离与支撑超平面422.6对偶锥与广义不等式46参考文献52习题3凸函数6131基本性质和例子El32保凸运算3.3共轭函数8534拟凸函数90