数学建模第三章

数学建模第三章

第三章⾮线性最优化⽅法§3.1 最优化问题与建模

⼀. 基本概念：

因为⼈类所从事的⼀切⽣产或社会活动均是有⽬的的，其⾏为总是在特定的价值观念或审美取向的⽀配下进⾏的，经常⾯临求解⼀个可⾏的甚⾄是最优的⽅案的决策问题。可以说，最优化思想是数学建模的灵魂。⽽最优化⽅法作为⼀门特殊的数学学科分⽀有着⼴泛的实际应⽤背景。典型的最优化模型可以被描述为如下形式：

其中表⽰⼀组决策变量，通常在实数域内取值，称决策变量的函数为该最优化模型的⽬标函数；为维欧⽒空间的某个⼦集，通常由⼀组关于决策变量的等式或不等式刻画，形如：

这时，称模型中关于决策变量的等式或不等式、

为约束条件，⽽称满⾜全部约束条件的空间中的点

为该模型的可⾏解，称

，即由所有可⾏解构成的集合为该模型的可⾏域。

称为最优化模型的（全局）最优解，若满⾜：对均有，这时称处的⽬标函数值的为最优化模型的（全局）最优值；称为最优化模型

的局部最优解，若存在，对

，均有。（全局）最优解⼀定是局部最优解，但反之不然，其关系可由下图得到反映：

上图为函数在区间上的⼀段函数曲线（由Mathematica

绘制），如果考察最优化问题，从图中发现它有三

个局部最优解、、，其中是全局最优解，最优值为“”。

⼆. 最优化问题的⼀些典型的分类：

优化⽅法涉及的应⽤领域很⼴，问题种类与性质繁多，根据不同的原则可以给出不同的分类。从数学建模的⾓度，对最优化问题的⼀些典型分类及相关概念的了解是有益的。

根据决策变量的取值类型，可分为函数优化问题与组合优化问题，称决策变量均为连续变量的最优化问题为函数优化问题；若⼀个最优化问题的全部决策变量均离散取值，则称之为组合优化问题。⽐⽅⼀些最优化问题的决策变量被限定只能取整数值，即为组合最优化问题，这类优化问题通常被称为整数规划问题，另外⼤多⽹络规划问题属于组合最优化问题。当然，也有许多应⽤问题的数学模型表现为混合类型的，即模型的部分决策变量为连续型的，部分决策变量为离散型的；另外当谈论⼀个最优化问题是函数优化问题还是组合优化问题时，还需结合我们对这⼀问题的思考⽅式来进⾏确定，⽐⽅后⾯介绍的线性规划问题的求解，既有将其作为⼀个组合优化问题⽽开发的算法，也有将其作为⼀个函数优化问题⽽开发的算法；

另外的⼀种分类⽅式是根据问题中⽬标、约束条件函数的形式或性质来加以划分的：若⼀个最优化问题的⽬标、约束条件函数均为决策变量的线性函数，则称之为线性规划问题，否则称之为⾮线性最优化问题。线性规划问题的研究，理论和⽅法都已发展的相当成熟，⽅法被⼴泛应⽤于⽣产和管理等领域；⽽对⾮线性最优化问题，根据建模和算法设计的需要还有更进⼀步的分类；

在⽣产、经济与管理等领域中遇到的⼤量最优决策问题，对⼀个⽅案的评价是多⾓度多指标的，反映在数学模型中，优化的⽬标是关于决策变量的⼀个函数组，我们称之为多⽬标规划问题。⽐如导弹的设计，既要其射程远，⼜要消耗燃料少，还要命中率⾼等；⼜如选择新⼚的⼚址，除了要考虑地价、原料采购的运费等经济指标外，还需考虑对环境的污染等社会因素。

三. 最优化问题最优解的⼀阶必要条件：

这⾥对形如的最优化问题的⼀阶必要性条件作简单介绍，它⼀⽅⾯可以将最优化问题和⽅程组问题做某种形式的联系，另⼀⽅⾯它在最优化问题数值求解算法的设计有重要的意义。

定理：设为最优化问题的（局部）最优解，若满⾜：1）、在均可微；

2）、分别表⽰、在的梯度向量，向量组线性⽆关；

则，满⾜：1）；

2）对于，均有且。

例、求解如下⾮线性规划:。

解：⽬标函数的梯度向量（函数）为，⽽约束条件相当于有三个：、、，它们分别对应梯度向量（函数）、、；

令、、、并要求。解之得四组解：1）；；2）；；

3）；；

4）；；

计算每个点的⽬标函数值，发现为（全局）最优解，最优⽬标函数值为。

特别，对于⽆约束最优化问题，其⼀阶最优化条件如下：

定理：设为最优化问题的（局部）最优解，若在均

可微，则在的梯度向量为零向量，即。§3.2 ⽆约束最优化⽅法

在这⾥我们只是对⼀些典型的最优化算法作简单介绍，以期那些初次接触数值计算⽅法的学习者能对最优化算法的设计思想有概貌性了解，能编写⼀些简单的最优化算法以处理学习中遇到的问题。⽽希望对最优化⽅法有更深⼊的学习或者欲处理相对复杂的最优化问题，需要参考更为专门的书籍或借助有关数学软件。

⼀．⼀维搜索：1．0.618法（黄⾦分割法）：

设单变量函数在区间上有定义，若存在⼀点，使得在区间上严格单调减，在区间上严格单调增，则称

是区间上的（下）单峰函数。显然是在区间上的唯

⼀的极⼩值点。

对（下）单峰函数，有如下基本性质：

性质1：设是区间上的（下）单峰函数，是在区间上的唯⼀的极⼩值点，对任意，若，则必有；

性质2：设是区间上的（下）单峰函数，是在区间上的唯⼀的极⼩值点，对任意，若，则必有；若，则必有。

根据（下）单峰函数所具有的性质，对在某区间上的（下）单峰函数

可采⽤法（黄⾦分割法）进⾏搜索其在区间内的极⼩值点。⽅法只需计算函数值，⽤途很⼴。0.618法：

这⾥设为区间上的单峰函数，（即黄⾦分割数，，算法由此得名），

步1：令，，，，，，以及精度要求；

步2：若，输出：为近似最优解，为近似最优⽬标函数值，停⽌；

步3：若，，，，，，转步2；

步4：，，，，，转步2；

易知，按照如上算法，每次迭代，只需计算⼀个点的函数值，均使解的存在区间以的⽐率缩⼩；⽽在所有固定分划⽐的区间分割法中，以上特点为黄

⾦分割法所独有，其余，每次迭代，需计算两个点的函数值。从计算相同的函数值数⽬⽽使最优解的存在区间长度所能达到的缩⼩⽐率考虑，黄⾦分割法在所有固定分划⽐的区间分割法中是最优的，这⾥将黄⾦分割法连续迭代两次，最优解

的存在区间长度所能达到的缩⼩⽐率为，⽽其它所有具有固定分划⽐的区间分割法每次迭代所达到的缩⼩⽐率⼩于。因此黄⾦分割法在所有固定分划⽐的区间分割法中是最优的。

例：⽤法求解，解的初始存在区间取，这⾥要求在近似解的

误差不超过。

解：⽤0.618法编程求解，经29步迭代，得该问题的近似解及其⽬标函数值为

。2．⽜顿法与抛物线法：

在所有函数中，讨论⼆次多项式函数的极⼩（⼤）值问题最为典型。对⼀元⼆次多项式，当时，易知是⽆约束最优化问

题的最优解。⽽对⼀般函数最优解的求解，可以利⽤对⼀些点处⽬标

函数的函数值、⼀阶或⼆阶导数值构造⽬标函数在⼀点局部或者在⼀定范围内的⼆次多项式逼近模型，以逼近模型的最优解作为求解原最优化问题的⼀个迭代点。称这类⽅法为（⼆次）插值法。

对⼀元函数，⼆次多项式逼近模型的建⽴通常有四种⽅式：其⼀是利⽤函数在⼀点处函数值、⼀阶及⼆阶导数值；其⼆是利⽤三个不同点的函数值；其三是利⽤两个不同点的函数值以及它们中⼀点的⼀阶导数值；其四是利⽤两个不同点的⼀阶导数值以及它们中⼀点的函数值。这⾥只介绍前两种，⽽称基于第⼀种⽅式构造的算法为⽜顿法，称基于第⼀种⽅式构造的算法为抛物线法。设为的某算法的迭代点列，在⽜顿法中，迭代公式采⽤：⽽在抛物线法中，迭代公式采⽤：

当函数具有⽐较好的解析性质时，⽜顿法与抛物线法通常⽐法的效果更好。

例：分别⽤⽜顿法、抛物线法求解，在选⽤⽜顿法时初始点取，在选⽤抛物线法时初始点取且服从均匀分布的⼀组随机数，这⾥要求在近似解处⼀阶导数的绝对值不超过。

解：⽤⽜顿法编程求解，经29步迭代，得该问题的近似解及其⽬标函数值为以下为整个迭代点列：

⽤抛物线法编程求解，经22步迭代，得该问题的近似解及其⽬标函数值为以下为整个迭代点列：

⼆．多元函数的⽆约束最优化⽅法：

对于多元函数的⽆约束最优化问题的数值求解，这⾥只

介绍“最速下降法”和“⽜顿法”。前者体现了“⼀维搜索”在多元函数的最优化问题数值求解中的应⽤，同时也是下降算法中最典型的代表；⽽后者，可以被视为⼀元函数最优化问题的⽜顿法求解的推⼴，其每⼀步基本迭代均采⽤在当前迭代点处的⼆阶Talor展式作为原⽬标函数的⼀个局部逼近模型进⾏求解。1．最速下降法：

设为的某算法的迭代点列，为⽬标函数在点处的负梯度⽅向，迭代公式采⽤：

这⾥，步长因⼦为（⼀元函数）最优化问题的（近似）解，可采⽤⼀维搜索进⾏求解。

例：⽤最速下降法求解，初始点取，这⾥要求在近似解处⽬标函数梯度的模不⼤于。

解：⽤最速下降法编程求解，经28步迭代，得该问题的近似解及其⽬标函数值为以下为整个迭代点列：

2．⽜顿法：

设为的某算法的迭代点列，

为⽬标函数在点处的梯度向量，

为⽬标函数在点处的Hessian矩阵，⽜顿法的迭代公式采⽤：

特别当正定时，为

的解。

例：⽤⽜顿法求解，初始点取，这⾥要求在近似解处⽬标函数梯度的模不⼤于。解：⽤⽜顿法编程求解，经12步迭代，得该问题的近似解及其⽬标函数值为以下为整个迭代点列：