本书主要介绍线性与非线性规划的理论与计算方法。预备知识部分包括变分分析的相关素材;理论部分包括对偶理论和非线性规划的最优性理论;计算方法包括无约束优化的线搜索方法、线性规划的单纯形方法和内点方法、非线性规划的增广Lagrange函数方法和序列三次规划方法。本书注重知识的准确性、系统性和算法论证的完整性,是学习最优化方法的一本入门书。
样章试读
目录
- 目录
前言
第1章 变分分析的相关素材 1
1.1 凸分析素材 1
1.1.1 凸集合 1
1.1.2 凸函数的闭包 3
1.1.3 共轭函数 5
1.1.4 次可微性 8
1.2 集值映射的极限 11
1.3 方向导数 18
1.4 集合的切锥与二阶切集 27
1.4.1 集合的切锥 27
1.4.2 二阶切集 35
1.4.3 凸函数水平集的切锥与二阶切集 39
1.4.4 负卦限锥的切锥与二阶切集 41
1.5 有限维系统的稳定性 42
1.5.1 线性系统 43
1.5.2 集合约束的线性系统 45
1.5.3 集合约束的非线性系统 47
第2章 无约束优化 54
2.1 引言 54
2.2 线搜索方法 56
2.2.1 线搜索原则 56
2.2.2 下降方法的收敛性 58
2.3 最速下降方法 61
2.3.1 最速下降方法的全局收敛性 61
2.3.2 最速下降方法的收敛速度 63
2.4 Newton法 68
2.4.1 经典Newton法 68
2.4.2 带线搜索的Newton法 70
2.4.3 自协调函数的Newton法 70
2.5 拟Newton法 72
2.5.1 拟Newton方程和著名的拟Newton公式 72
2.5.2 拟Newton法求解凸二次规划 74
2.5.3 Dixon定理 75
2.5.4 DFP方法的收敛性 77
2.5.5 BFGS方法的收敛性 83
2.5.6 限制Broyden类方法的收敛性 87
2.6 共轭梯度方法 94
2.6.1 共轭方向 94
2.6.2 共轭梯度方法求解二次规划 96
2.6.3 求解无约束优化问题的FR方法 101
2.7 信赖域方法 103
2.7.1 信赖域基本算法 104
2.7.2 Cauchy点与模型下降 105
2.7.3 信赖域算法的收敛性 107
第3章 线性规划 110
3.1 线性规划问题及其性质 110
3.2 单纯形法 114
3.3 Bland原则 120
3.4 绒性规划的对偶定理 122
3.5 对偶单纯形方法 124
3.6 线性规划的Karmarkar内点法 127
3.6.1 解析中心与势函数 127
3.6.2 线性规划的势函数 131
3.6.3 线性规划的中心路径 132
3.6.4 线性规划的Karmarkar算法 135
第4章 对偶理论 141
4.1 共轭对偶性 141
4.2 Lagrange对偶性 145
4.3 对偶理论的应用 147
第5章 最优性条件 155
5.1 一阶最优性条件 155
5.2 广义Lagrange乘子 157
5.3 二阶最优性条件 158
第6章 增广Lagrange函数方法 162
6.1 惩罚与障碍函数方法 162
6.1.1 惩罚函数方法 162
6.1.2 经典障碍函数方法 168
6.2 增广Lagrange函数方法 169
6.2.1 增广Lagrange函数 169
6.2.2 Bertsekas的经典结果 171
6.2.3 对偶收敛率 175
第7章 序列二次规划(SQP)方法 177
7.1 等式约束优化问题的局部方法 177
7.1.1 Newton法 177
7.1.2 KKT系统 180
7.1.3 既约Hesse阵方法 182
7.2 一般约束优化问题的局部方法 186
7.2.1 序列二次规划方法 186
7.2.2 原始一对偶二次收敛性 188
7.2.3 原始超线性收敛性 192
7.3 线搜索全局方法 195
7.3.1 不可微惩罚函数 195
7.3.2 线搜索SQP方法 199
7.3.3 Maratos效应 203
参考文献 209