最优化方法及其 MATLAB实现

第1章 概 论…………………………………………………………………………………… 1
1.1 最优化问题及其分类…………………………………………………………………… 1
1.1.1 最优化问题举例……………………………………………………………………… 1
1.1.2 函数优化问题………………………………………………………………………… 3
1.1.3 数学规划……………………………………………………………………………… 4
1.1.4 组合优化问题………………………………………………………………………… 5
1.2 邻域函数与局部搜索…………………………………………………………………… 6
1.3 优化问题的复杂性……………………………………………………………………… 6
1.4 优化算法发展状况……………………………………………………………………… 7
上 篇 经典优化方法
第2章 无约束优化方法……………………………………………………………………… 10
2.1 最优性条件……………………………………………………………………………… 10
2.2 迭代法…………………………………………………………………………………… 10
2.3 收敛速度………………………………………………………………………………… 11
2.4 终止准则………………………………………………………………………………… 12
2.5 一维搜索………………………………………………………………………………… 12
2.5.1 平分法……………………………………………………………………………… 12
2.5.2 牛顿法……………………………………………………………………………… 13
2.5.3 0.618法……………………………………………………………………………… 14
2.5.4 抛物线法……………………………………………………………………………… 15
2.5.5 二点三次插值法……………………………………………………………………… 16
2.5.6 “成功失败”法……………………………………………………………………… 17
2.5.7 非精确一维搜索……………………………………………………………………… 17
2.6 基本下降法……………………………………………………………………………… 19
2.6.1 最速下降法…………………………………………………………………………… 19
2.6.2 牛顿法……………………………………………………………………………… 20
2.6.3 阻尼牛顿法…………………………………………………………………………… 20
2.6.4 修正牛顿法…………………………………………………………………………… 20
2.7 共轭方向法和共轭梯度法……………………………………………………………… 21
2.7.1 共轭方向和共轭方向法……………………………………………………………… 22
2.7.2 共轭梯度法…………………………………………………………………………… 23
2.8 变尺度法(拟牛顿法)…………………………………………………………………… 24
2.8.1 对称秩1算法………………………………………………………………………… 24
2.8.2 DFP算法…………………………………………………………………………… 25
2.8.3 BFGS算法…………………………………………………………………………… 25
2.9 直接搜索法……………………………………………………………………………… 27
2.9.1 Hook-Jeeves方法…………………………………………………………………… 27
2.9.2 单纯形法……………………………………………………………………………… 29
2.9.3 Powell方法…………………………………………………………………………… 29
2.10 算法的MATLAB实现……………………………………………………………… 31
第3章 约束优化方法………………………………………………………………………… 36
3.1 最优性条件……………………………………………………………………………… 36
3.1.1 等式约束问题的最优性条件…………………………………………………………… 36
3.1.2 不等式约束问题的最优性条件………………………………………………………… 37
3.1.3 一般约束问题的最优性条件…………………………………………………………… 37
3.2 罚函数法………………………………………………………………………………… 38
3.2.1 外罚函数法…………………………………………………………………………… 38
3.2.2 内点法……………………………………………………………………………… 39
3.2.3 乘子法……………………………………………………………………………… 41
3.3 可行方向法……………………………………………………………………………… 43
3.3.1 Zoutendijk可行方向法………………………………………………………………… 43
3.3.2 梯度投影法…………………………………………………………………………… 45
3.3.3 简约梯度法…………………………………………………………………………… 47
3.3.4 广义简约梯度法……………………………………………………………………… 49
3.4 二次逼近法……………………………………………………………………………… 50
3.4.1 二次规划的概念……………………………………………………………………… 50
3.4.2 牛顿拉格朗日法……………………………………………………………………… 51
3.4.3 SQP算法…………………………………………………………………………… 52
3.5 极大熵方法……………………………………………………………………………… 56
3.6 算法的MATLAB实现………………………………………………………………… 57
第4章 最小二乘问题………………………………………………………………………… 63
4.1 线性最小二乘问题的数值解法………………………………………………………… 63
4.1.1 满秩线性最小二乘问题……………………………………………………………… 64
4.1.2 亏秩线性最小二乘问题……………………………………………………………… 64
4.2 非线性最小二乘问题的数值解法……………………………………………………… 65
4.2.1 Gauss-Newton法…………………………………………………………………… 65
4.2.2 Levenberg-Marquardt方法(L-M 方法)……………………………………………… 66
4.3 算法的MATLAB实现………………………………………………………………… 67
第5章 线性规划……………………………………………………………………………… 71
5.1 线性规划的标准形式…………………………………………………………………… 71
5.2 线性规划的基本定理…………………………………………………………………… 72
5.3 单纯形法………………………………………………………………………………… 73
5.3.1 基本单纯形法………………………………………………………………………… 73
5.3.2 单纯形法的改进……………………………………………………………………… 77
5.4 线性规划问题的对偶问题……………………………………………………………… 78
5.4.1 对偶单纯形法………………………………………………………………………… 79
5.4.2 对偶线性规划的应用………………………………………………………………… 81
5.5 算法的MATLAB实现………………………………………………………………… 84
第6章 动态规划……………………………………………………………………………… 91
6.1 理论基础………………………………………………………………………………… 91
6.2 最优化原理和基本方程………………………………………………………………… 94
6.3 动态规划的建模方法及步骤…………………………………………………………… 96
6.4 函数空间迭代法和策略空间迭代法…………………………………………………… 98
6.4.1 函数空间迭代法……………………………………………………………………… 99
6.4.2 策略空间迭代法…………………………………………………………………… 100
6.5 动态规划与静态规划的关系………………………………………………………… 103
6.6 算法的MATLAB实现……………………………………………………………… 104
第7章 整数规划……………………………………………………………………………… 112
7.1 理论基础……………………………………………………………………………… 112
7.1.1 整数线性规划的标准形式…………………………………………………………… 112
7.1.2 整数线性规划的求解………………………………………………………………… 112
7.1.3 松 驰……………………………………………………………………………… 113
7.1.4 分 解……………………………………………………………………………… 113
7.2 分支定界法…………………………………………………………………………… 114
7.3 割平面法……………………………………………………………………………… 115
7.4 隐枚举法……………………………………………………………………………… 118
7.4.1 0-1规划的标准形式………………………………………………………………… 118
7.4.2 隐枚举法的基本步骤………………………………………………………………… 119
7.5 匈牙利法……………………………………………………………………………… 120
7.5.1 指派问题的标准形式………………………………………………………………… 120
7.5.2 匈牙利法的基本步骤………………………………………………………………… 121
7.6 算法的MATLAB实现……………………………………………………………… 123
第8章 二次规划问题………………………………………………………………………… 128
8.1 等式约束二次规划的解法…………………………………………………………… 128
8.1.1 零空间方法………………………………………………………………………… 128
8.1.2 拉格朗日乘子法…………………………………………………………………… 129
8.2 一般凸二次规划的有效集方法……………………………………………………… 130
8.3 算法的MATLAB实现……………………………………………………………… 132
第9章 多目标规划…………………………………………………………………………… 134
9.1 多目标规划的概念…………………………………………………………………… 134
9.2 有效解、弱有效解和绝对有效解……………………………………………………… 135
9.3 处理多目标规划问题的一些方法…………………………………………………… 136
9.3.1 评价函数法………………………………………………………………………… 136
9.3.2 约束法……………………………………………………………………………… 140
9.3.3 逐步法……………………………………………………………………………… 140
9.3.4 分层求解法………………………………………………………………………… 141
9.3.5 图解法……………………………………………………………………………… 143
9.4 权系数的确定方法…………………………………………………………………… 144
9.4.1 α 方法……………………………………………………………………………… 144
9.4.2 老手法……………………………………………………………………………… 144
9.4.3 最小平方法………………………………………………………………………… 145
9.5 目标规划法…………………………………………………………………………… 145
9.5.1 目标规划模型……………………………………………………………………… 145
9.5.2 目标点法…………………………………………………………………………… 148
9.5.3 目标规划单纯形法…………………………………………………………………… 149
9.6 算法的MATLAB实现……………………………………………………………… 153
第10章 图 论……………………………………………………………………………… 161
10.1 图的理论基础………………………………………………………………………… 161
10.1.1 图的基本概念 ……………………………………………………………………… 161
10.1.2 图的矩阵表示……………………………………………………………………… 165
10.1.3 图论的基本性质和定理…………………………………………………………… 166
10.2 最短路………………………………………………………………………………… 166
10.2.1 Dijkstra算法……………………………………………………………………… 167
10.2.2 Warshall-Floyd算法……………………………………………………………… 167
10.2.3 求最大可靠路的算法……………………………………………………………… 168
10.2.4 求期望最大可靠容量路…………………………………………………………… 168
10.3 树……………………………………………………………………………………… 169
10.3.1 求最小树的Kruskal算法…………………………………………………………… 170
10.3.2 求最小树的Prim算法……………………………………………………………… 171
10.4 欧拉(Euler)图和Hamilton图……………………………………………………… 171
10.4.1 Euler图…………………………………………………………………………… 171
10.4.2 中国邮递员问题…………………………………………………………………… 172
10.4.3 Hamilton图………………………………………………………………………… 173
10.4.4 旅行售货员问题…………………………………………………………………… 173
10.5 匹配问题及其算法…………………………………………………………………… 174
10.5.1 匹配、完善匹配、最大匹配…………………………………………………………… 174
10.5.2 匹配的基本定理…………………………………………………………………… 174
10.5.3 人员分配问题……………………………………………………………………… 175
10.5.4 最优分派问题……………………………………………………………………… 176
10.6 网络流的算法………………………………………………………………………… 177
10.6.1 网络和流…………………………………………………………………………… 177
10.6.2 割………………………………………………………………………………… 178
10.6.3 网络的最大流问题及Ford-Fulkerson算法………………………………………… 178
10.7 最小费用流…………………………………………………………………………… 179
10.7.1 最小费用流问题…………………………………………………………………… 180
10.7.2 Busacker-Gowan迭代算法………………………………………………………… 181
10.8 图的染色……………………………………………………………………………… 182
10.8.1 顶点染色及其算法………………………………………………………………… 182
10.8.2 边染色及其算法…………………………………………………………………… 183
10.9 算法的MATLAB实现……………………………………………………………… 183
下 篇 现代智能优化算法
第11章 进化算法…………………………………………………………………………… 199
第12章 模拟退火算法……………………………………………………………………… 235
第13章 禁忌算法…………………………………………………………………………… 245
第14章 蚁群算法…………………………………………………………………………… 255
第15章 粒子群算法………………………………………………………………………… 269
第16章 人工鱼群算法……………………………………………………………………… 279
第17章 混合蛙跳算法……………………………………………………………………… 294
第18章 量子遗传算法……………………………………………………………………… 302
第19章 人工蜂群算法……………………………………………………………………… 314
第20章 混沌优化算法……………………………………………………………………… 325
第21章 人工免疫算法……………………………………………………………………… 333
第22章 细菌觅食算法……………………………………………………………………… 354
第23章 猫群算法…………………………………………………………………………… 366
第24章 神经网络与神经网络优化算法…………………………………………………… 373
第25章 其他群智能优化算法……………………………………………………………… 392
第26章 混合优化算法……………………………………………………………………… 433