最优化理论与方法

最优化理论与方法是计算机科学与技术、人工智能及相关专业的主干课程之一。本书结合最优化理论与方法的基本原理和各种高效算法的实际应用，系统地介绍了很优化问题的数学建模方法，并融入了和最优化理论与方法课程密切相关的思政元素。 全书共9章，第1章为引言，第2～9章全面系统地介绍了相关数学知识、线性规划、单纯形方法、对偶理论和灵敏度分析、一维搜索、使用导数的很优化方法、惩罚函数法、动态规划法，同时部分章末引入了思政扩展阅读内容。 本书提供了较为丰富的实例、案例分析和几何演示，可以作为计算机科学与技术、人工智能、数学和运筹学等相关专业高年级本科生与研究生的教材，也可以作为从事该领域研究的工程技术人员的学习参考书。

第1章 引言 1 1.1 概述 1 1.2 线性规划与非线性规划问题 2 第2章 相关数学知识 6 2.1 向量与矩阵 6 2.1.1 基本定义 6 2.1.2 矩阵的秩 6 2.1.3 线性方程组 7 2.1.4 内积和范数 8 2.2 凸集与凸函数 10 2.2.1 凸集 10 2.2.2 凸集分离定理 11 2.2.3 凸函数 13 2.2.4 凸函数的判别 13 2.2.5 凸规划 14 2.3 微积分基础 15 2.3.1 序列与极限 15 2.3.2 可微性 16 2.3.3 导数矩阵 17 2.3.4 微分法则 19 2.3.5 水平集与梯度 19 2.3.6 泰勒级数 21 习题 22 第3章 线性规划 25 3.1 线性规划问题的标准形式 25 3.2 两变量线性规划问题的图解法 28 3.3 线性规划的基本概念与性质 31 3.3.1 线性规划的基本概念 31 3.3.2 线性规划的基本性质 35 3.4 用LINGO软件求解线性规划问题 35 3.5 用MATLAB求解线性规划问题 36 习题 37 第4章 单纯形方法 39 4.1 单纯形方法的原理 39 4.1.1 单纯形方法的基本思想 39 4.1.2 很优性条件 39 4.1.3 基本可行解的转换 41 4.1.4 单纯形方法的计算步骤 43 4.1.5 收敛性分析 46 4.2 使用表格形式的单纯形方法 46 4.3 案例分析和代码实现 51 习题 54 第5章 对偶理论和灵敏度分析 55 5.1 线性规划中的对偶理论 55 5.1.1 对偶问题的提出 55 5.1.2 对偶问题的定义 56 5.1.3 对偶定理 60 5.1.4 对偶问题的经济含义――影子价格 62 5.2 对偶单纯形方法 63 5.2.1 对偶单纯形方法的基本思想 63 5.2.2 计算步骤 65 5.2.3 对偶单纯形方法的MATLAB实现 67 5.3 灵敏度分析 69 5.3.1 改变系数向量c 69 5.3.2 改变右端向量b 71 5.3.3 改变约束矩阵A 73 5.3.4 增加新的约束条件 74 习题 77 第6章 一维搜索 78 6.1 一维搜索概述 78 6.1.1 基本概念 78 6.1.2 一维搜索算法的闭性 78 6.2 试探法 79 6.2.1 0.618试探法 79 6.2.2 Fibonacci试探法 81 6.2.3 0.618试探法和Fibonacci试探法的关系 84 6.3 案例分析 85 习题 92 第7章 使用导数的很优化方法 93 7.1 最速下降法 93 7.1.1 最速下降方向 93 7.1.2 最速下降法的迭代算法 94 7.1.3 最速下降法的收敛性 95 7.2 牛顿法 96 7.2.1 牛顿法的迭代算法 96 7.2.2 阻尼牛顿法 99 7.2.3 牛顿法的进一步修正 100 7.3 共轭梯度法 101 7.3.1 共轭方向 101 7.3.2 FR共轭梯度法 102 7.3.3 用于一般函数的共轭梯度法 105 7.3.4 PRP共轭梯度法的收敛性 107 习题 110 第8章 惩罚函数法 112 8.1 外点惩罚函数法 112 8.1.1 外点惩罚函数的基本思想 112 8.1.2 外点惩罚函数法的计算步骤 113 8.1.3 外点惩罚函数法的收敛性 114 8.2 内点惩罚函数法 116 8.2.1 内点惩罚函数法的基本思想 116 8.2.2 内点惩罚函数法的计算步骤 117 8.2.3 内点惩罚函数法的收敛性 117 8.2.4 案例分析 119 习题 121 第9章 动态规划法 123 9.1 动态规划的基本概念 123 9.1.1 动态规划的实例与定义 123 9.1.2 形式化术语 123 9.2 逆推解法及案例分析 125 9.2.1 逆推解法介绍 125 9.2.2 逆推解法案例分析 125 9.3 顺推解法及案例分析 128 9.3.1 顺推解法介绍 128 9.3.2 顺推解法案例分析 128 参考文献 133