凸优化

1 引言 1

1.1 数学优化 1

1.2 最小二乘和线性规划 3

1.3 凸优化 6

1.4 非线性优化 8

1.5 本书主要内容 10

1.6 符号 12

参考文献 13

Ⅰ 理论 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

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

Ⅱ 应用 283

6 逼近与拟合 285

6.1 范数逼近 285

6.2 最小范数问题 295

6.3 正则化逼近 297

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

Ⅲ 算法 435

9 无约束优化 437

9.1 无约束优化问题 437

9.2 下降方法 443

9.3 梯度下降方法 445

9.4 最速下降方法 454

9.5 Newton方法 461

9.6 自和谐 473

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

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和LDLT因式分解 637

C.4 分块消元和Schur补 642

C.5 求解不确定线性方程组 650

参考文献 653

参考文献 654

符号 670

索引 673