凸优化理论

第 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

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

本书力图以简洁的篇幅，介绍凸优化的一个完整理论分析框架。凸优化理论的基石在于对偶。作者选取了zui小公共点/zui大相交点的几何框架（简称MC/MC框架）作为凸优化问题的对偶性分析的基础框架。相比于基于函数共轭性的代数框架，MC/MC框架更适用于直观地分析和理解各种重要的优化问题，也更适合初学者学习和理解凸优化理论。本书可以作为高年级本科生、研究生运筹学优化类课程的教材或相关研究人员的参考书。
原著作者美国工程院院士Dimitri P.Bertsekas教授有极高的学术造诣和学术声誉，在学术专著和教材的写作方面取得了公认的成就。