凸优化理论/信息技术和电气工程学科国际知名教材中译本系列

本书力图以简洁的篇幅，介绍凸优化的一个完整理论分析框架。凸优化理论的基石在于对偶。作者选取了zui小公共点/zui大相交点的几何框架（简称MC/MC框架）作为凸优化问题的对偶性分析的基础框架。相比于基于函数共轭性的代数框架，MC/MC框架更适用于直观地分析和理解各种重要的优化问题，也更适合初学者学习和理解凸优化理论。本书可以作为高年级本科生、研究生运筹学优化类课程的教材或相关研究人员的参考书。

原著作者美国工程院院士Dimitri P.Bertsekas教授有极高的学术造诣和学术声誉，在学术专著和教材的写作方面取得了公认的成就。

三年多以前， 2000年 10月，为了系统地参考和借鉴国外知名相关大学教材，推进我国大学的课程改革和我国大学教学的国际化进程，清华大学出版社策划、出版了《国际知名大学原版教材 ——信息技术学科与电气工程学科系列》，至今已经出版了 30多种，深受高等院校信息技术与电气工程及相关学科师生和其他科技人员的欢迎和好评，在学术界和教育界产生了积极的影响 .现在这个系列中的大部分教材都已经重印，并曾获得《 2001年引进版youxiu畅销丛书奖》 .在此期间，我们曾收到来自各地高校师生的很多反映，期望我们选择这个系列中的一些较为基础性和较为前沿性的教材译成中译本出版，以为更广大的院校师生和科技人员所选用 .正是基于这种背景和考虑，清华大学出版社决定进一推出《信息技术和电气工程学科国际知名教材中译本系列》 .这套国际知名教材中译本系列所选书目的范围，限于信息技术和电气工程学科所各专业的技术基础课和主要专业课 .教材原版本除了选自《国际知名大学原版教材 ——信息技术学科与电气工程学科系列》外，还将精选其他具有较大影响的国外知名的相关领域教材或教学参考书 .教材内容适于作为我国普通高等院校相应课程的教材或主要教学参考书.

第 1章凸分析的基本概念 .................................................................1

1.1凸集与凸函数 .......................................................................1

1.1.1凸函数 .......................................................................3

1.1.2函数的闭性与半连续性 ...............................................8

1.1.3凸函数的运算 ........................................................... 10

1.1.4可微凸函数的性质 .................................................... 12

1.2凸包与仿射包 ..................................................................... 17

1.3相对内点集和闭包 .............................................................. 21

1.3.1相对内点集和闭包的演算 .......................................... 25

1.3.2凸函数的连续性 ....................................................... 33

1.3.3函数的闭包 .............................................................. 35

1.4回收锥 ............................................................................... 40

1.4.1凸函数的回收方向 .................................................... 48

1.4.2闭集交的非空性 ....................................................... 54

1.4.3线性变换下的闭性 .................................................... 61

1.5超平面 ............................................................................... 63

1.5.1分离超平面 .............................................................. 64

1.5.2超平面真分离 ........................................................... 69

1.5.3用非竖直超平面做分离 ............................................. 75

1.6共轭函数 ........................................................................... 78

1.7小结 .................................................................................. 85

第 2章多面体凸性的基本概念 ........................................................ 87

2.1顶点 .................................................................................. 87

2.2极锥 .................................................................................. 94

XIV凸优化理论

2.3多面体集和多面体函数 ....................................................... 96

2.3.1多面体锥和 Farkas引理 ........................................... 96

2.3.2多面体集的结构 ...................................................... 98

2.3.3多面体函数 ........................................................... 103

2.4优化的多面体方面 ............................................................ 105

第 3章凸优化的基本概念 ............................................................ 109

3.1约束优化 ......................................................................... 109

3.2最优解的存在性 ............................................................... 111

3.3凸函数的部分最小化 ......................................................... 115

3.4鞍点和最小最大理论 ......................................................... 119

第 4章对偶原理的几何框架 ......................................................... 123

4.1最小公共点/最大相交点问题的对偶性 ................................ 123

4.2几种特殊情况 ................................................................... 128

4.2.1对偶性与共轭凸函数的联系 .................................... 128

4.2.2一般优化问题中的对偶性 ....................................... 129

4.2.3不等式约束下的优化问题 ....................................... 130

4.2.4不等式约束问题的增广拉格朗日对偶性 ................... 132

4.2.5最小最大问题 ........................................................ 133

4.3强对偶定理 ...................................................................... 138

4.4对偶最优解的存在性 ......................................................... 142

4.5对偶性与凸多面体 ............................................................ 145

4.6小结 ................................................................................ 150

第 5章对偶性与优化 ................................................................... 151

5.1非线性 Farkas引理 .......................................................... 151

5.2线性规划的对偶性 ............................................................ 155

5.3凸规划的对偶性 ............................................................... 158

5.3.1强对偶定理 ——不等式约束 .................................. 159

5.3.2最优性条件 ........................................................... 160

5.3.3部分多面体约束 .................................................... 162

5.3.4对偶性与原问题最优解的存在性 ............................. 167

5.3.5 Fenchel对偶性 ...................................................... 169

目录 XV

5.3.6锥对偶性 .............................................................. 172

5.4次梯度与最优性条件 ......................................................... 173

5.4.1共轭函数的次梯度 ................................................. 177

5.4.2次微分运算 ........................................................... 182

5.4.3最优性条件 ........................................................... 185

5.4.4方向导数 .............................................................. 186

5.5最小最大理论 ................................................................... 190

5.5.1最小最大对偶定理 ................................................. 191

5.5.2鞍点定理 .............................................................. 194

5.6择一定理 ......................................................................... 200

5.7非凸问题 ......................................................................... 207

5.7.1可分问题中的对偶间隙 .......................................... 207

5.7.2最小最大问题中的对偶间隙 .................................... 216

附录 A数学背景 .......................................................................... 217

A.1线性代数 ........................................................................ 219

A.2拓扑性质 ........................................................................ 222

A.3导数 ............................................................................... 227

附录 B注释和文献来源 ................................................................ 229

本书的目标是给出以下两个主题的易懂、简洁和直观的展示 .

(a)凸分析，特别是与优化的联系 .

(b)优化与最小最大问题的对偶理论，特别是在凸性框架中的情形 .它们是在广泛的实际应用中相关的两个主题.

优化的重点在于推导出约束问题存在原始和对偶最优解的条件 .约束问题的例子是

minimize f(x)

subject to x ∈ X, gj(x) . 0,j =1, ··· , r.

其他类型的优化问题，包括从 Fenchel对偶性产生的问题，也属于我们考虑的范围.最小最大问题的重点是推导保证等式

inf sup φ(x, z) = sup inf φ(x, z)

x∈Xz∈Zz∈Zx∈X

成立，以及下确界 “inf”和上确界 “sup”可取到的条件.

凸性的理论内容介绍得比较详细 .囊括了这个领域几乎所有重要的方面，对于凸优化中核心的分析问题的展开是足够了 .数学预备知识是线性代数和实分析的入门知识 .附录中包含了用到的有关知识的总结 .除了这些少量背景外，本书的内容是自足的，严格的证明会贯穿全书 .线性和非线性优化理论的先修知识不是必需的，尽管作为背景知识无疑它们是有帮助的 .

我们的目标是尽量发挥凸性理论在以一种统一的方式建立最强的对偶性方面的作用 .为此，我们的分析常会偏离 Rockafellar 1970年的经典著作的思路，而是遵从 Fenchel/Rockafellar的框架 .例如，我们采用不同的方式来处理闭集相交理论和线性变换下闭包的保持 (1.4.2和 1.4.3节)；我们用约束优化情形下的对偶性来发展次微分运算 (5.4.2节)；此外，我们没有

凸优化理论

使用下确界卷积 (in.mal convolution)、函数图像 (image)、极性集合和函数 (polar sets and functions)、双函数 (bifunctions)和共轭鞍点函数 (conjugate saddle functions)等概念 .类似于 Fenchel/Rockafellar，我们的理论体系是基于 Legendre/Fenchel共轭的思想，不过相比之下，在几何和可视化方面要来得直观得多.

我们的对偶框架是基于两个简单的几何问题：最小公共点问题 (min common point problem)和最大相交点问题 (max crossing point problem).最小公共点 /最大相交点 (MC/MC)框架的突出优点在于其几何上的直观性.借助这个框架，对偶性理论的核心问题都变得显然，并且可以采用统一的方法处理 .我们的方法是先在 MC/MC框架里得到许多广泛可用的定理，然后把它们用于解决特定问题 (约束优化、 Fenchel对偶性、最小最大问题等)上.我们处理所有对偶性问题 (对偶间隙的存在性、对偶最优解的存在性、对偶最优解集合的结构 )和其他问题 (次微分理论、择一定理、对偶间隙估计)都按照这样的思路.

从根本上说， MC/MC框架与共轭性框架存在着密切的联系 .也正因为如此， MC/MC框架在理论上很有用也有一般性 .不过，这两个框架在分析对偶性和提供几何解释上扮演者互补的角色：共轭性强调函数 /代数描述，而 MC/MC强调集合 /上图描述 . MC/MC框架更简单，而且看起来更适合可视化和研究强对偶性和对偶最优解的存在性问题 .共轭性框架，由于强调函数的描述，更适合凸函数的数学运算比较复杂，而且共轭函数的计算可以用于分析和计算.

本书源自作者早期的著作 [BNO03](与 A. Nedi′c和 A. Ozdaglar合著 )，但具有不同的特点 . 2003年的书内容很多，从结构上更像是学术专著，目标是利用非光滑分析的概念建立凸的和非凸的优化问题之间的联系 .本书的组织与此不同，本书集中于介绍凸优化问题 .尽管有这些区别，两本书在写作风格、数学基础和某些内容上还是有共同之处 .

本书各章的内容如下:

第 1章:本章给出后续各章描述对偶性理论所需要的全部凸分析工具 .会介绍基本的代数概念，如凸锥、超平面、拓扑概念，如相对内点、闭包、线性变换下闭性的保持，超平面分离 .另外，本章还会给出与对偶和优化相关的特定概念，如回收锥和共轭函数 .

第 2章:本章介绍多面体凸性概念:顶点、 Farkas和 Minkowski-Weyl定理及其在线性规划中的应用 .在后续章节中不会用到，首次阅读时可以跳过 .

前言 XI

第 3章:本章集中在优化的基本概念上：极小值的类型、解的存在性和对偶理论专题，如部分最小化和最小最大理论 .

第 4章:本章介绍 MC/MC对偶框架 .我们会讨论它和共轭理论之间的联系，及在约束优化和最小最大问题上的应用 .本章最后给出与强对偶性和对偶最优解存在性有关的应用广泛的定理.

第 5章:本章把第 4章的对偶定理应用到线性规划、凸规划和最小最大理论等专题上 .我们还应用这些定理作为进一步发展凸分析工具的辅助 .这些工具包括强有力的 Farkas引理的非线性版本、次微分理论、择一定理 .最后一节主要侧重于可分问题，给出非凸问题和对偶间隙的估计 .

为了简洁起见，我们略去了教师们可能会感兴趣的一些话题 .例如把理论应用到特定结构的问题 ; Boyd和 Vanderbergue的著作 [BoV04]，以及我和 John Tsitsiklis合著的关于并行与分布式计算的著作 [BeT89]包含了这方面的许多材料 (这两本书都可在线访问).

另外一个忽略的重要部分是计算方法 .不过，我补充了一个很长的第 6章 (超过 100页)，其中有最常见的凸优化算法 (和一些新算法)，并且可以从本书的网站下载 (https://www.athenasc.com/convexduality.html).

本章和更全面的凸分析、优化、对偶性以及算法等内容一起，将成为作者正在编著的教材的一部分 .到那时，本章将在对偶性之外，为教师们提供凸优化算法内容 (如作者在麻省理工学院所做的 ).本章是一个定期更新的 “活”的章节 .它的当前内容是 :算法方面的第 6章: 6.1.问题结构与计算方法; 6.2.算法中的递减性 ; 6.3.次梯度法 ; 6.4.多面体近似方法 ; 6.5.邻近性和 Bundle方法 ; 6.6.对偶邻近点算法 ; 6.7.内点法 ; 6.8.近似次梯度法 ; 6.9.最优算法和复杂性.

虽然作者没有在书中提供习题，但是在本书的网站上提供了大量的习题 (并附有详细的解答 ).读者 /教师也可以使用 [BNO03]中给出的章节后习题 (共 175道).这些习题的风格和符号与本书类似 .习题解答在本书的网站可以下载，也可以在线获取 (https://www.athenasc.com/convexity.html).

本书可以作为凸优化理论课程的教材，作者在过去十年在麻省理工学院和其他场所教授过类似课程 .本书也可以作为非线性规划课程的补充材料，或者作为凸优化模型 (而不是理论)方面课程的理论基础.

本书的组织使得读者 /教师可以选择性地使用其中的内容 .例如，第 2章多面体凸性的材料完全可以略去，因为第 3～5章完全不涉及这部分内容.类似地，最小最大理论 (3.4，4.2.5和 5.5节)可以被略去；并且如果是

XII凸优化理论

这样，那么 3.3和 5.3.4节这些使用部分最小化工具的内容也可以略去 .另外，5.4～5.7节处在 “末端 ”，都可以略去而不会影响其他章节 .如作者在麻省理工学院的“非线性规划”课程 (加上网站上补充的关于算法的第 6章)上所做的，一种 “最小的”选项包含以下内容：

.第 1章，除去 1.3.3和 1.4.1节.

.第 3.1节.

.第 4章，除去 4.2.5节.

.第 5章，除去 5.2，5.3.4和 5.5～5.7节.这种组合侧重于非线性凸优化，而完全不涉及多面体凸性和最小最大理论.

作者感谢同事们对本书的贡献 .作者与 Angelia Nedi′c和 Asuman Ozdaglar在他们的 2003年的著作上的合作为本书打下了基础 . Huizhen (Janey) Yu仔细阅读了本书部分内容的早期书稿，并给出了一些很有启发的建议 . Paul Tseng通过与作者在集合相交理论方面的合作研究，对本书做出了实质性的贡献 .部分体现在 1.4.2节 (这项研究受到与 Angelia Nedi′c的早期合作的启发 ).非常感谢 Dimitris Bisias，Vivek Borkar，John Tsitsiklis，Mengdi Wang和 Yunjian Xu等学生和同事提供的反馈信息 .最后，作者希望感谢课堂上的许多优秀学生所不断提供的动力和灵感 .