最优化：理论、计算与应用

目 录 
第1章 最优化问题概述 1 
1.1 最优化问题的数学模型与分类 1 
1.2 最优化问题 2 
1.2.1 无约束最优化问题 2 
1.2.2 线性规划问题 3 
1.2.3 二次规划问题 4 
1.2.4 约束优化问题 6 
1.3 无约束问题的最优性条件 7 
1.3.1 无约束问题的最优解 7 
1.3.2 最优性条件 9 
1.4 约束问题的最优性条件 13 
1.4.1 约束问题的全局解与局部解 13 
1.4.2 约束问题最优解的最优性条件 14 
1.5 凸集与凸函数 21 
1.5.1 凸集 22 
1.5.2 凸函数 25 
1.6 约束问题最优性条件的证明 28 
1.6.1 一阶必要条件的证明 28 
1.6.2 二阶充分条件的证明 33 
1.7 MATLAB优化工具箱 35 
1.7.1 MATLAB概述 35 
1.7.2 MATLAB优化工具箱概述 35 
1.7.3 MATLAB优化工具箱中的函数 36 
习题1 37 
第2章 一维搜索与信赖域方法 42 
2.1 求解无约束问题的结构 42 
2.1.1 一维搜索策略的下降算法 42 
2.1.2 信赖域方法 42 
2.2 一维搜索 43
2.2.1 精确一维搜索算法 43 
2.2.2 非精确一维搜索算法 46 
2.2.3 正定二次函数的一维搜索方法 48 
2.3 下降算法的收敛性 49 
2.3.1 算法的收敛性 49 
2.3.2 算法的收敛速率 52 
2.3.3 算法的二次终止性 52 
2.4 信赖域方法 53 
2.4.1 信赖域方法的基本结构 53 
2.4.2 求解信赖域子问题的dogleg方法 54 
2.4.3 信赖域方法的全局收敛性 55 
2.5 自编的MATLAB程序 57 
2.5.1 一维搜索程序 57 
2.5.2 求解信赖域子问题折线方法 61 
2.6 MATLAB优化工具箱中的函数 63 
2.7 一维优化问题的应用 64 
2.7.1 路灯照明问题 65 
2.7.2 极大似然估计 66 
习题2 67 
第3章 无约束最优化方法 68 
3.1 算法 68 
3.1.1 最速下降法的收敛性质 68 
3.1.2 算法的收敛性质 70 
3.2 共轭梯度法 74 
3.2.1 线性共轭梯度法 74 
3.2.2 非线性共轭梯度法 79 
3.2.3 共轭梯度法的收敛性质 82 
3.3 Newton法 85 
3.3.1 精确Newton法 85 
3.3.2 Newton法的收敛性质 87 
3.3.3 非精确Newton法 88 
3.3.4 带有一维搜索的Newton法 89 
3.3.5 信赖域Newton法 91 
3.4 拟Newton法 94
3.4.1 秩1修正公式 95 
3.4.2 秩1修正公式的性质 98 
3.4.3 秩2修正公式 100 
3.4.4 秩2修正公式的性质 105 
3.4.5 信赖域算法 110 
3.5 自编的MATLAB程序 111 
3.5.1 最速下降法 111 
3.5.2 共轭梯度法 112 
3.5.3 Newton法 113 
3.5.4 拟Newton法 114 
3.5.5 信赖域方法 115 
3.6 MATLAB优化工具箱中的函数 118 
3.6.1 多变量极小化函数 118 
3.6.2 设置优化参数 121 
3.7 无约束最优化问题的应用 125 
3.7.1 选址问题 125 
3.7.2 曲线拟合问题 126 
3.7.3 药物浓度的测定 126 
习题3 129 
第4章 非线性方程与最小二乘问题 133 
4.1 求解非线性方程组 133 
4.1.1 非线性方程求根 133 
4.1.2 非线性方程组求解 136 
4.2 超定方程组求解与最小二乘问题 143 
4.2.1 线性最小二乘问题 144 
4.2.2 Gauss-Newton法 146 
4.2.3 Levenberg-Marquardt方法 149 
4.2.4 拟Newton法 152 
4.3 自编MATLAB程序 153 
4.3.1 求解非线性方程的方法 153 
4.3.2 求解非线性方程组的方法 156 
4.3.3 求解非线性最小二乘问题的算法 161 
4.4 MATLAB优化工具箱中的函数 167 
4.4.1 求解非线性方程 (组) 167
4.4.2 求解线性最小二乘问题 170 
4.4.3 求解非线性最小二乘问题 174 
4.5 非线性方程(组)的应用 177 
4.5.1 求极值问题 177 
4.5.2 GPS定位问题 179 
4.6 最小二乘问题的应用 182 
4.6.1 曲线拟合问题 182 
4.6.2 GPS定位问题(续) 182 
习题4 184 
第5章 线性规划 187 
5.1 线性规划的数学模型 187 
5.1.1 线性规划的实例 187 
5.1.2 线性规划的标准形式 190 
5.1.3 线性规划的图解法 191 
5.2 求解线性规划问题的单纯形法 194 
5.2.1 基本单纯形法 194 
5.2.2 单纯形表 197 
5.2.3 两阶段方法 199 
5.2.4 改进单纯形法 203 
5.3 线性规划的对偶问题 205 
5.3.1 对偶线性规划 205 
5.3.2 线性规划的对偶理论 208 
5.3.3 对偶单纯形法 211 
5.4 内点算法概述 215 
5.4.1 算法复杂性的基本概念 215 
5.4.2 单纯形法的复杂性 215 
5.4.3 内点算法简介 216 
5.5 自编MATLAB程序 217 
5.5.1 从基本可行解开始的单纯形法 217 
5.5.2 两阶段方法 218 
5.5.3 从正则解开始的对偶单纯形法 220 
5.6 MATLAB优化工具箱中的函数 222 
5.6.1 linprog函数 222 
5.6.2 Lagrange乘子的意义 224 
5.6.3 intlinprog函数 227 
5.7 线性规划问题的应用 230 
5.7.1 城市规划 230 
5.7.2 投资 233 
5.7.3 生产计划与库存控制 236 
5.7.4 人力规划 244 
5.7.5 最小覆盖 246 
5.8 用线性规划求解图论中的问题 248 
5.8.1 运输问题 248 
5.8.2 最优指派问题 250 
5.8.3 最短路问题 253 
5.8.4 最大流问题及应用 258 
习题5 264 
第6章 约束最优化方法 273 
6.1 二次规划问题 273 
6.1.1 二次规划的基本性质 273 
6.1.2 等式二次规划问题 274 
6.1.3 求解凸二次规划的有效集法 280 
6.2 罚函数方法 286 
6.2.1 二次罚函数方法 286 
6.2.2 l1 模罚函数方法 294 
6.2.3 乘子罚函数法 297 
6.2.4 一般等式约束问题的乘子罚函数法 302 
6.2.5 一般约束问题的乘子罚函数法 304 
6.3 序列二次规划方法 308 
6.3.1 Lagrange-Newton法 308 
6.3.2 一般约束问题的序列二次规划方法 310 
6.4 序列二次规划的信赖域方法 316 
6.4.1 求解等式约束问题的信赖域算法 316 
6.4.2 求解一般约束问题的信赖域算法 320 
6.5 MATLAB优化工具箱中的函数 323 
6.5.1 求解二次规划问题 323 
6.5.2 求解一般约束问题 327 
6.6 约束最优化问题的应用 331
6.6.1 投资组合问题 331 
6.6.2 选址问题 332 
习题6 334 
习题参考答案 339 
参考文献 347 
索引 348 
MATLAB函数索引 352 
MATLAB自编函数索引 353