第5章 非线性规划

1、第五章第五章 非线性规划非线性规划 Nonlinear Programming 5.1 非线性规划的基本概念和定理非线性规划的基本概念和定理 一、什么是非线性规划一、什么是非线性规划? 前面我们已经讨论过线性规划问题，其目标函数和前面我们已经讨论过线性规划问题，其目标函数和 约束条件都是自变量的线性函数。还有一类比线性约束条件都是自变量的线性函数。还有一类比线性 规划问题范围更广的数学规划，这就是非线性规划规划问题范围更广的数学规划，这就是非线性规划 问题。什么是非线性规划呢问题。什么是非线性规划呢?我们先来看一个例子：我们先来看一个例子： 例例1：已知立式圆柱型油罐的容积为已知立式圆柱型油罐

2、的容积为V，设油罐各层，设油罐各层 圈板厚度与底板和顶板厚度相同，确定油罐的高度圈板厚度与底板和顶板厚度相同，确定油罐的高度 与直径使耗钢量最少。与直径使耗钢量最少。 非线性规划的基本概念和定理非线性规划的基本概念和定理 解：因各圈壁板与顶板、底板厚度相等，故油罐的耗钢解：因各圈壁板与顶板、底板厚度相等，故油罐的耗钢 量与其总表面积成正比。量与其总表面积成正比。 设油罐的底半径为设油罐的底半径为x，高为，高为y，则，则V=x2y，如果近似，如果近似 把顶做为平板计算，则油罐的表面积为：把顶做为平板计算，则油罐的表面积为： S=2x2+2xy 该问题的数学模型为：该问题的数学模型为： 0, .

3、22 min 2 2 yx Vyx ts xyxS 非线性规划的基本概念和定理非线性规划的基本概念和定理 分析该数学模型，可以发现，目标函数不是线性函数，分析该数学模型，可以发现，目标函数不是线性函数， 而是决策变量的二次函数，约束条件也不是线性的，而而是决策变量的二次函数，约束条件也不是线性的，而 是三次函数。这是一个非线性规划问题。是三次函数。这是一个非线性规划问题。 miXgts XfS i 1 0)( . )( min 非线性规划的定义：非线性规划的定义：只要目标函数或约束条件中含有一只要目标函数或约束条件中含有一 个非线性函数，则称这种规划为非线性规划问题。非线个非线性函数，则称这种

4、规划为非线性规划问题。非线 性规划问题的一般形式为：性规划问题的一般形式为： 非线性规划的基本概念和定理非线性规划的基本概念和定理* 其中其中X=(xl,x2,xn)T为为n维欧式空间中的向量，维欧式空间中的向量，f(X)、gi(X) 为向量函数。为向量函数。 gi(X)0为由为由m个非线性等式或不等式组成的约束条件。个非线性等式或不等式组成的约束条件。 “”有三层含义：有三层含义： “=”；“或或”；“或或0，函数，函数f(X)为定义在为定义在D上的凸函数。上的凸函数。 性质性质2：有限个凸函数的非负组合仍为凸函数。即：有限个凸函数的非负组合仍为凸函数。即 为凸函数为凸函数 1 0 )()(

5、)( 2211 ni XfXfXf i nn 是凸集。是凸集。 )X(f ,DX XS 性质性质3：设：设f(X)是定义在凸集是定义在凸集D上的凸函数，则对于任意上的凸函数，则对于任意 实数实数，集合，集合 非线性规划的基本概念和定理非线性规划的基本概念和定理 3、凸函数的判定、凸函数的判定 定理定理1：(一阶条件，即用一阶导数判断一阶条件，即用一阶导数判断)设设f(X) 在开凸在开凸 集集D上可微，则上可微，则f(X)为为D上凸函数的充要条件是：上凸函数的充要条件是： 对于任意对于任意X(1)、X(2)，恒有，恒有 )1()2( )1()1()2( )()()(XXXfXfXf T (即每一

6、点的切线在图形的下方即每一点的切线在图形的下方) 列列向向量量，处处的的一一阶阶偏偏导导数数构构成成的的在在为为其其中中 )1()1( )()(XXfXf 即梯度向量：即梯度向量： T n x Xf x Xf x Xf Xf )( , )( , )( )( )1( 2 )1( 1 )1( )1( 开凸集是指不包括边界的凸集。开凸集是指不包括边界的凸集。 非线性规划的基本概念和定理非线性规划的基本概念和定理 DX 定理定理2：(二阶条件，用二阶导数判断二阶条件，用二阶导数判断)设设f(X)在开凸集在开凸集D上上 二阶可微，则二阶可微，则f(X)为为D上凸函数的充要条件是：对上凸函数的充要条件是：

7、对 于所有于所有 ，其海森矩阵为半正定。若为正定，其海森矩阵为半正定。若为正定， 则为严格凸函数。则为严格凸函数。 4、凸函数的极值、凸函数的极值 对于凸函数的极值，有以下两个重要的结论：对于凸函数的极值，有以下两个重要的结论： 凸函数的任一局部极小值等于全局极小值；若是严格凸凸函数的任一局部极小值等于全局极小值；若是严格凸 函数，则局部极小点是唯一的。函数，则局部极小点是唯一的。 凸函数的极小点形成一个凸集。凸函数的极小点形成一个凸集。 非线性规划的基本概念和定理非线性规划的基本概念和定理 根据凸函数极值的性质，如果我们能预先证明目标函数根据凸函数极值的性质，如果我们能预先证明目标函数 f(

8、X)在可行域在可行域D内是凸函数，则可以肯定所求得的局部极内是凸函数，则可以肯定所求得的局部极 小点就是全局极小点，而不用求出其所有的极小点并进小点就是全局极小点，而不用求出其所有的极小点并进 行比较。行比较。 5、凸规划、凸规划 在非线性规划模型在非线性规划模型 miXgts XfS i 1 0)( . )( min 中，如果中，如果f(X)和和-gi(X)都是凸函数，或者说都是凸函数，或者说f(X)为凸函数，为凸函数， gi(X)为凹函数，则称这种规划为凸规划。为凹函数，则称这种规划为凸规划。 非线性规划的基本概念和定理非线性规划的基本概念和定理 凸规划具有如下性质：凸规划具有如下性质：

9、可行解集为凸集；可行解集为凸集； 最优解集为凸集最优解集为凸集(若最优解存在的话若最优解存在的话)； 任何局部最优解均为其全局最优解；任何局部最优解均为其全局最优解； 若目标函数为严格凸函数，且最优解存在，则最优解必唯一。若目标函数为严格凸函数，且最优解存在，则最优解必唯一。 根据凸规划的定义，线性规划是一种凸规划。根据凸规划的定义，线性规划是一种凸规划。 非线性规划的基本概念和定理非线性规划的基本概念和定理 例：判断下列非线性规划是否为凸规划例：判断下列非线性规划是否为凸规划? ? 0)( 0)( 01)( 02)( . 44)(min 24 13 2 2 12 211 1 2 2 2 1

10、xXg xXg xxXg xxXg ts xxxXf 非线性规划的基本概念和定理非线性规划的基本概念和定理 解：先验证约束条件解：先验证约束条件gi(X)为凹函数。为凹函数。g1(X)、g3(X) 、 g4(X)均为自变量的线性函数，为凹函数；均为自变量的线性函数，为凹函数；g2(X)的的 海森阵为：海森阵为： 为半负定，故为半负定，故g2(X)为凹函数；为凹函数； f(X)的海森阵为：的海森阵为： 00 02 )( 2 2 Xg 为正定，故为正定，故f(X)为凸函数，上述规划为凸规划，有为凸函数，上述规划为凸规划，有 唯一极小点唯一极小点X*=(0.58，1.34)T，f(X*)3.8。 2

11、0 02 )( 2 Xf 5.2 无约束非线性规划寻优方法概述无约束非线性规划寻优方法概述 无约束非线性规划问题的寻优方法大致可分为两类：无约束非线性规划问题的寻优方法大致可分为两类： 一、间接寻优方法一、间接寻优方法(也称为解析法也称为解析法) 利用求导数寻求函数极值的方法即古典的微分法就属于利用求导数寻求函数极值的方法即古典的微分法就属于 这一类。这类方法要求把一个非线性规划问题用数学方这一类。这类方法要求把一个非线性规划问题用数学方 程式描述出来。然后按照函数极值的必要条件用数学分程式描述出来。然后按照函数极值的必要条件用数学分 析的方法求出其解析解，再按照充分条件或者问题的实析的方法求

12、出其解析解，再按照充分条件或者问题的实 际物理意义间接地确定是否最优解，因此称为间接法。际物理意义间接地确定是否最优解，因此称为间接法。 这类间接寻优方法适用于目标函数具有简单而明确的数这类间接寻优方法适用于目标函数具有简单而明确的数 学形式的非线性规划问题，而对于目标函数比较复杂，学形式的非线性规划问题，而对于目标函数比较复杂， 或甚至无明确的数学表达式的情况，间接法就无能为力或甚至无明确的数学表达式的情况，间接法就无能为力 了，这时需要采用直接寻优方法。了，这时需要采用直接寻优方法。 非线性规划寻优方法概述非线性规划寻优方法概述 二、直接寻优方法二、直接寻优方法(也称搜索法也称搜索法) 这

13、是一种数值方法，利用函数在某一局部区域的性质这是一种数值方法，利用函数在某一局部区域的性质 或一些已知的数值，来确定下一步计算的点，这样一或一些已知的数值，来确定下一步计算的点，这样一 步步搜索逼近，最后达到最优点。这种方法一般称为步步搜索逼近，最后达到最优点。这种方法一般称为 下降迭代算法（对于最小化问题）。下降迭代算法（对于最小化问题）。 下降迭代算法的基本思想是：从某一初始点分下降迭代算法的基本思想是：从某一初始点分X(0)出出 发，按照一定规则发，按照一定规则(即算法即算法)转换到某一个比转换到某一个比X(0)更好的更好的 点点X(1)(对极小化问题，要求对极小化问题，要求f(X(1)

14、f(X(0) ，故称为下，故称为下 降迭代算法降迭代算法)，再转换到，再转换到X(2) ，如此继续下去就产，如此继续下去就产 生了一个点列生了一个点列X(k)：X(0), X(1), X(k),；相应的目标；相应的目标 函数值满足：函数值满足： 非线性规划寻优方法概述非线性规划寻优方法概述 f(X(0)f(X(1)f(X(2)f(X(k) 若该点列收敛于若该点列收敛于f(X)的最优点的最优点X*，即，即 0lim *)( XX k k 则称算法是收敛的。对于某一算法来说，我们要求其产则称算法是收敛的。对于某一算法来说，我们要求其产 生的点列生的点列X(k)中的某一点本身就是问题的精确最优点，中

15、的某一点本身就是问题的精确最优点， 或者该点列的极限点是问题的精确最优点，但该极限点或者该点列的极限点是问题的精确最优点，但该极限点 是不能达到的，在这种情况下，经过有限次迭代不可能是不能达到的，在这种情况下，经过有限次迭代不可能 得到问题的精确最优解，而只能得到一个近似最优解。得到问题的精确最优解，而只能得到一个近似最优解。 对于一般的非线性函数，大多数迭代算法都只能求得近对于一般的非线性函数，大多数迭代算法都只能求得近 似最优点。似最优点。 非线性规划寻优方法概述非线性规划寻优方法概述 下降迭代算法的迭代过程可分为下降迭代算法的迭代过程可分为4步步 选择初始点选择初始点X(0) ，令令k=

16、0； 确定搜索方向。确定搜索方向。从迭代点从迭代点X(k)出发，确定一个搜索方向出发，确定一个搜索方向 P(k)，要求沿这个方向能找到使目标函数下降的点；，要求沿这个方向能找到使目标函数下降的点； 确定步长。确定步长。沿沿P(k)方向前进一步，得到新的迭代点方向前进一步，得到新的迭代点X(k+1)： 检验检验X(k+1)是否满足计算终止准则，是否满足计算终止准则，如满足则迭代结束，如满足则迭代结束， 此时此时X(k+1)就是要求的极小点或近似极小点；否则，令就是要求的极小点或近似极小点；否则，令 k=k+1，转。，转。 0 )()()1( k k k kk PXX 在以上步骤中，选定搜索方向是

17、最关键的一步，它是区在以上步骤中，选定搜索方向是最关键的一步，它是区 分各种算法的主要标志。分各种算法的主要标志。 非线性规划寻优方法概述非线性规划寻优方法概述 在许多算法中，搜索方向在许多算法中，搜索方向P(k)确定之后，步长是按使目标确定之后，步长是按使目标 函数值下降最大的原则选定的，即求函数值下降最大的原则选定的，即求k，使得，使得 )( min)( )()()()(kkk k k PXfPXf k 这实际上是求这实际上是求的一元函数的一元函数f(X(k)+P(k)的极小点的极小点k。故常。故常 把按上述原则确定把按上述原则确定k的过程称为一维搜索。由此确定的的过程称为一维搜索。由此确

18、定的 步长称为最佳步长。步长称为最佳步长。 非线性规划寻优方法概述非线性规划寻优方法概述 对于线性规划问题，我们可以利用检验数方便地判断一个对于线性规划问题，我们可以利用检验数方便地判断一个 基本可行解是否为最优解。但对于非线性规划问题则要复基本可行解是否为最优解。但对于非线性规划问题则要复 杂得多。由于精确极值点杂得多。由于精确极值点X*在求出之前并不知道，因此，在求出之前并不知道，因此， 在实用上只能根据所得到的迭代点的信息来判断是否应该在实用上只能根据所得到的迭代点的信息来判断是否应该 终止迭代过程。常用的计算终止准则有以下几种：终止迭代过程。常用的计算终止准则有以下几种： 根据相邻两个

19、迭代点的绝对误差判断根据相邻两个迭代点的绝对误差判断 2 )()1( 1 )()1( )()( kk kk XfXf XX 非线性规划寻优方法概述非线性规划寻优方法概述 根据相邻两个迭代点的相对误差判断：根据相邻两个迭代点的相对误差判断： 4 )( )()1( 3 )( )()1( )( )()( k kk k kk Xf XfXf X XX 根据函数梯度的模判断：根据函数梯度的模判断： 5 )( )( k Xf 非线性规划寻优方法概述非线性规划寻优方法概述 式中：式中：15是事先给定的足够小的正数，视问题的精度是事先给定的足够小的正数，视问题的精度 要求确定。要求确定。 需要指出的是，上述判

20、敛准则需要指出的是，上述判敛准则 没有一种是对任意函数都普遍没有一种是对任意函数都普遍 有效的。例如有效的。例如当函数值随当函数值随X变变 化不剧烈时化不剧烈时，只用函数值的差，只用函数值的差 值判敛可能会出现错误，虽然值判敛可能会出现错误，虽然 满足了满足了 ，但离，但离 最优解最优解X*可能还很远。可能还很远。 2 )() 1( )()( kk XfXf x* x(k+1) f(x) x x* x(k+1) f(x) x 同样对于同样对于函数值随函数值随X变化剧烈变化剧烈 的情况的情况，只用，只用 判判 断也是不可靠的。最好的办法断也是不可靠的。最好的办法 是将上述判敛准则联合使用。是将上

21、述判敛准则联合使用。 1 )()1( kk XX 非线性规划寻优方法概述非线性规划寻优方法概述 几乎所有的非线性规划寻优方法求得的结果都是局部最几乎所有的非线性规划寻优方法求得的结果都是局部最 优解。但若非线性规划的目标函数是凸函数，则局部最优解。但若非线性规划的目标函数是凸函数，则局部最 优解就是全局最优解。优解就是全局最优解。 在实际工作中，当我们处理一个具体的非线性规划问题在实际工作中，当我们处理一个具体的非线性规划问题 时，目标函数是否为凸函数，有时可以验证，有时并不时，目标函数是否为凸函数，有时可以验证，有时并不 容易验证。而一般求出的极小值往往是局部极小值，这容易验证。而一般求出的

22、极小值往往是局部极小值，这 种情况下，对于很多具有迭代性的方法，为了求出全局种情况下，对于很多具有迭代性的方法，为了求出全局 极小值，可从多个初始点出发进行迭代，求出多个局部极小值，可从多个初始点出发进行迭代，求出多个局部 极小值，比较确定全局极小值。极小值，比较确定全局极小值。 5.3 几种常用的一维搜索算法几种常用的一维搜索算法 一维搜索算法用于求单变量函数极值。单变量极值问题是一维搜索算法用于求单变量函数极值。单变量极值问题是 最简单的极值问题，它不但存在于实际问题中，而且是某最简单的极值问题，它不但存在于实际问题中，而且是某 些多变量函数最优化算法的基础。许多多元函数无约束最些多变量函

23、数最优化算法的基础。许多多元函数无约束最 优化搜索算法实质上是由一系列一维搜索构成的，而一维优化搜索算法实质上是由一系列一维搜索构成的，而一维 搜索的成功与否对整个算法的效率影响很大。如上节提到搜索的成功与否对整个算法的效率影响很大。如上节提到 的求的求X(k+1)=X(k)+P(k) 中的步长因子中的步长因子k的单变量极值问的单变量极值问 题题 。因此一维搜索算法是最优化理论中。因此一维搜索算法是最优化理论中 很重要的一种算法。很重要的一种算法。 )( min )()(kk PXf k 几种常用的一维搜索算法几种常用的一维搜索算法 在所讨论的算法中，大多数属于序列搜索法。所谓序列在所讨论的算

24、法中，大多数属于序列搜索法。所谓序列 搜索法就是利用过去的信息来生成以后的搜索点的方法，搜索法就是利用过去的信息来生成以后的搜索点的方法， 它是一类直接利用目标函数值信息的一维搜索方法，它它是一类直接利用目标函数值信息的一维搜索方法，它 通过比较一系列试点的目标函数值而逐渐缩小搜索区间，通过比较一系列试点的目标函数值而逐渐缩小搜索区间， 其基本原理是：在搜索区间其基本原理是：在搜索区间a,b内任取两点内任取两点xl、x2且且xlx2， 计算函数值计算函数值f(xl)、f(x2)，将，将f(xl)与与f(x2)比较，有三种可能比较，有三种可能 情况：情况： f(xl)f(x2)： 去掉去掉a,x

25、1，最小点，最小点x*必在必在 x1, b内，内，x2为保留点；为保留点； 几种常用的一维搜索算法几种常用的一维搜索算法 f(xl)=f(x2)： 同时去掉同时去掉a,x1和和x2,b， 最小点最小点x*必在必在x1,x2内。内。 这种情况很少遇到，而这种情况很少遇到，而 且在计算机中，浮点数且在计算机中，浮点数 是不存在相等关系的。是不存在相等关系的。 几种常用的一维搜索算法几种常用的一维搜索算法 然后在缩小的区间内只取一个新点，并将该点的函数值然后在缩小的区间内只取一个新点，并将该点的函数值 与保留点的函数值比较，按上述原则缩小区间，这样继与保留点的函数值比较，按上述原则缩小区间，这样继

26、续下去，当区间缩短到足够小时，即得到了满足给定精续下去，当区间缩短到足够小时，即得到了满足给定精 度要求的近似解。度要求的近似解。 一、穷举搜索法一、穷举搜索法 我们先讨论一种最简单的搜索方法我们先讨论一种最简单的搜索方法穷举搜索法，它是穷举搜索法，它是 通过将搜索区间划分成若干份，然后计算各个点的函数值通过将搜索区间划分成若干份，然后计算各个点的函数值 并比较而求得最优解。其计算方法和搜索步骤如下：并比较而求得最优解。其计算方法和搜索步骤如下： 1、确定区间缩短的精度或允许误差、确定区间缩短的精度或允许误差，即令要考察的试，即令要考察的试 点点xi之间的间隔为之间的间隔为； 几种常用的一维搜

27、索算法几种常用的一维搜索算法 2、将搜索区间、将搜索区间a,b划分成宽为划分成宽为 的的k个区间，个区间，k=(b-a)/，得，得 k+1个试点。个试点。 3、计算、计算k+1个试点的函数值个试点的函数值f(xi)； 4、取、取k+1个函数值中最小者所对个函数值中最小者所对 应的应的xi作为最优解作为最优解x*，则最大，则最大 误差为误差为。 几种常用的一维搜索算法几种常用的一维搜索算法 二、对分搜索法二、对分搜索法 对分法的搜索步骤为：对分法的搜索步骤为： 1、在区间、在区间a,b的中点的中点x=(a+b)/2两侧各两侧各/2处取两个点：处取两个点： 对分搜索法属于序列搜索法，它要对分搜索法

28、属于序列搜索法，它要 求求f(x)是单峰的，否则只能求得局部是单峰的，否则只能求得局部 最优解。对于最优解。对于min问题，要求问题，要求f(x)是是 下单峰的，即在下单峰的，即在x*的左侧的左侧f(x)严格下严格下 降，在降，在x*的右侧的右侧f(x)严格上升。严格上升。 )( )( 2 1 22 1 1 baxbax 几种常用的一维搜索算法几种常用的一维搜索算法 并计算其函数值并计算其函数值f(x1)、f(x2)。其中。其中为为x*的最大允许的最大允许 误差。误差。 若若f(x1)f(x2) ，则删除区间，则删除区间a,x1，并令，并令ax1。 f(x1)f(x2) 2、比较、比较f(x1

29、)和和f(x2) 几种常用的一维搜索算法几种常用的一维搜索算法 3、若、若b-a0； 1、在区间、在区间a,b中选两个点中选两个点x1和和x2，使，使 121 )(618. 0 )(618. 0 xbaabaxabbx )( )( 2211 xfyxfy 步步。否否则则继继续续第第 ，计计算算结结束束；或或，（或或，则则、若若 3 2 2121 )y(yy)xxxab * 几种常用的一维搜索算法几种常用的一维搜索算法 3、若、若y1y2，则删去，则删去a,x1，并令，并令 a=x1，x1=x2，x2=a+b-x1，y1=y2，y2=f(x2)，转，转2； 若若y17 时，分时，分 数法的区间缩

30、短率已接近数法的区间缩短率已接近0.618。因此。因此0.618法是分数法法是分数法 的一个很好的近似，但其计算步骤比分数法简单得多，的一个很好的近似，但其计算步骤比分数法简单得多， 便于上机计算，因此一般多用便于上机计算，因此一般多用0.618法，而不采用分数法。法，而不采用分数法。 但分数法也有一个优点，就是对于给定的计算精度，可但分数法也有一个优点，就是对于给定的计算精度，可 以预先知道迭代的次数，避免出现死循环。以预先知道迭代的次数，避免出现死循环。 几种常用的一维搜索算法几种常用的一维搜索算法 1、确定试点的个数、确定试点的个数n。设原区间为。设原区间为a,b，将其缩短为原来，将其缩

31、短为原来 的的倍，即倍，即 ， ，查表由，查表由Fn确定确定n。 n F 1 1 n F 2、令、令k=1，在，在a,b内取两个试点内取两个试点x1和和x2，满足，满足 ab F F bx n n 1 1 1 1 2 xbaab F F ax n n 11 xfy 22 xfy 3、若、若k=n，转，转4；否则，令；否则，令k=k+1，继续下面的计算：，继续下面的计算： 如果如果y1y2，则删去，则删去a,x1，令，令 22 1 2 21211 xfyab F F ax yyxxxa kn kn ， ， ，计算结束。，计算结束。)y(yy)x(xx * 2121 4或或，或或、 几种常用的一维

32、搜索算法几种常用的一维搜索算法 五、抛物线插值法五、抛物线插值法 1、外推法求极值存在的区间、外推法求极值存在的区间 在前面讨论的方法中，都假设最优解存在的区间是已在前面讨论的方法中，都假设最优解存在的区间是已 知的，但对于许多实际问题，并不知道最优解存在的知的，但对于许多实际问题，并不知道最优解存在的 区间，这时，无论用前面讨论的方法还是插值法都必区间，这时，无论用前面讨论的方法还是插值法都必 须首先确定最优解存在的范围。通常采用的方法是外须首先确定最优解存在的范围。通常采用的方法是外 推法。为了加快寻找区间的速度，通常采用成倍加大推法。为了加快寻找区间的速度，通常采用成倍加大 步长的措施。

33、步长的措施。 几种常用的一维搜索算法几种常用的一维搜索算法 计算步骤：计算步骤： 设从某点设从某点x1出发，原始步长为出发，原始步长为h0，令，令 x2=x1+h0，计算，计算f(x1)、f(x2)，令，令k=2； 如果如果f(x1)f(x2)，转，否则转；，转，否则转； k=k+1，xk=xk-1+2k-2h0，计算，计算f(xk)。 若若f(xk)f(xk-1)，转，否则转（本步，转，否则转（本步 开始处）；开始处）； (将步长加倍，求将步长加倍，求x3=x2+2h0，x4=x3+4h0等点的函数值，直到函数值增等点的函数值，直到函数值增 加为止加为止)； 几种常用的一维搜索算法几种常用的

34、一维搜索算法 k=k+1，xk=xk-1-2k-3h0， 若若k=3，xk=xk-2-2k-3h0，计算，计算f(xk)； 若若f(xk)f(xk-1)，转，否则转，转，否则转 (本步开始处本步开始处)； (将步长加倍，求将步长加倍，求x3=x1-h0， x4=x3-2h0， ， x5=x4-4h0 ，等点 等点 的函数值，直到函数值增加为的函数值，直到函数值增加为 止止)； 几种常用的一维搜索算法几种常用的一维搜索算法 令令xk+1=(xk-1+xk)/2，计算，计算f(xk+1) 若若f(x1)f(x2)，则，则d=2k-3h0；否则；否则d=2k-4h0； 令令f(xb)=minf(xk

35、-2), f(xk-1), f(xk), f(xk+1) xa=xb-d， xc=xb+d，则则xa,xc为最优解存在的区间。为最优解存在的区间。 (该步的含义是：在该步的含义是：在xk-1和和xk中点取点中点取点xk+1，得，得4个等间距的点个等间距的点xk-2、xk-1、 xk+1、xk，其间距为，其间距为d。比较这。比较这4个点的函数值，将其中最小者命名为个点的函数值，将其中最小者命名为 xb ，该点两侧各为，该点两侧各为d的范围即为最优点存在的区间的范围即为最优点存在的区间) 几种常用的一维搜索算法几种常用的一维搜索算法 2、抛物线插值法、抛物线插值法 用外推法求出最优解存在的区间后，

36、可以采用前面讨用外推法求出最优解存在的区间后，可以采用前面讨 论的任何一种方法求得最优解。为了能充分利用外推论的任何一种方法求得最优解。为了能充分利用外推 法的计算结果，加速寻优过程，可采用抛物线插值法法的计算结果，加速寻优过程，可采用抛物线插值法 求最优解。求最优解。 外推法确定的最优解存在区间为外推法确定的最优解存在区间为xa,xc，且，且xb为该区间为该区间 内的一点，其函数值满足：内的一点，其函数值满足： f(xa)f(xb) ， f(xc)f(xb)。 可通过三点可通过三点(xa, f(xa)、(xb, f(xb)、(xc, f(xc)作一条二次作一条二次 抛物线抛物线P(x)来逼近

37、函数来逼近函数f(x) 。设。设 P(x)=a0+a1x+a2x2 几种常用的一维搜索算法几种常用的一维搜索算法 将三点的坐标代入可得三个线性方程，联立求解可得：将三点的坐标代入可得三个线性方程，联立求解可得： accbba cbabacacb xxxxxx xfxxxfxxxfxx a )()()( 222222 1 accbba cbabacacb xxxxxx xfxxxfxxxfxx a )()()( 2 P(x)的极小点即为抛物线的顶点：的极小点即为抛物线的顶点： ) 1 ( )()()( )()()( 2 1 2 222222 2 1 cbabacacb cbabacacb m x

38、fxxxfxxxfxx xfxxxfxxxfxx a a x 几种常用的一维搜索算法几种常用的一维搜索算法 若若xa、xc、xb三点等间距，上式简化为：三点等间距，上式简化为： 迭代步骤：迭代步骤： 设最优解存在区间为设最优解存在区间为xa,xc,在在xa,xc中取一点中取一点xb,计算计算f(xa)、 f(xb)、f(xc)(如果最优解存在区间是由外推法求得的如果最优解存在区间是由外推法求得的,可直可直 接利用其接利用其xa 、xb 、xc、 f(xa)、f(xb)、 f(xc)值值)。 按式按式(1)计算近似最优解计算近似最优解xm,若三点等间距若三点等间距,可按式可按式(2)计算。计算。

39、 )2( )()()(2 )()( cba ca bm xfxfxf xfxfh xx 几种常用的一维搜索算法几种常用的一维搜索算法 若若|xb-xm|(为给定的允许误差，为给定的允许误差， 0)，则，则x*=xm，停止计算；，停止计算； 否则转；否则转； 若若f(xm)f(xb)，转；否则转；，转；否则转； 若若xmxb，令，令xc=xm，f(xc)=f(xm)， 即保留即保留xa、 xb不变，删掉不变，删掉xm,xc (见图见图2)，转。，转。 几种常用的一维搜索算法几种常用的一维搜索算法 若若xmxb，令，令xa=xb，f(xa)=f(xb)， xb=xm，f(xb)=f(xm)，即保留

40、，即保留xc不不 变，删掉变，删掉xa,xb (见图见图3)，转。，转。 几种常用的一维搜索算法几种常用的一维搜索算法 若若xmxb，令，令xc=xb，f(xc)=f(xb)， xb=xm，f(xb)=f(xm)，即保留，即保留xa不不 变，删掉变，删掉xb,xc (见图见图4)，转。，转。 xc 几种常用的一维搜索算法几种常用的一维搜索算法 抛物线插值法的收敛速度在很大程度上取决于目标函抛物线插值法的收敛速度在很大程度上取决于目标函 数的性质，当目标函数比较接近二次抛物线时，这种数的性质，当目标函数比较接近二次抛物线时，这种 方法可能比分数法或方法可能比分数法或0.618法收敛快，然而，当相

41、差法收敛快，然而，当相差 较大时，该方法的收敛速度可能很慢，甚至不收敛或较大时，该方法的收敛速度可能很慢，甚至不收敛或 收敛点与收敛点与f(x)的极值点相差很远。因此，在对函数性的极值点相差很远。因此，在对函数性 质缺乏了解时，采用质缺乏了解时，采用0.618法更可靠。法更可靠。 几种常用的一维搜索算法几种常用的一维搜索算法 3、外推内插法的、外推内插法的FORTRAN语言程序语言程序 程序中目标函数采用语句函数定义，欲求解其它目标程序中目标函数采用语句函数定义，欲求解其它目标 函数时，可修改程序第一句中的目标函数定义，亦可函数时，可修改程序第一句中的目标函数定义，亦可 采用子程序进行定义。采

42、用子程序进行定义。 使用本程序时，应输入下列数据：使用本程序时，应输入下列数据： x0初始点，初始点，E精度。精度。 另外，本程序中，给定的初始步长另外，本程序中，给定的初始步长h0取值为取值为1.0(由由 H0=1.0赋值赋值)，迭代时步长缩短倍数，迭代时步长缩短倍数P取值为取值为0.1(由由 P=0.1赋值赋值)。如果这两个量选择其它数值，修改上述。如果这两个量选择其它数值，修改上述 两个赋值语句即可。两个赋值语句即可。 几种常用的一维搜索算法几种常用的一维搜索算法 CCCC 外推内插法求解一元函数的最小值外推内插法求解一元函数的最小值 F(X)=X*3-10*X*X+36 H0=1.0

43、P=0.1 WRITE(*,*) 请输入初始点请输入初始点X0、精度、精度E READ(*,*) X0,E X1=X0 F1=F(X1) 40N=0 H=H0 X2=X1+H F2=F(X2) IF(F1.GT.F2)GOTO 105 H=-H X3=X1 F3=F1 80X1=X2 几种常用的一维搜索算法几种常用的一维搜索算法 F1=F2 X2=X3 F2=F3 GOTO 115 105H=H+H N=N+1 115X3=X2+H F3=F(X3) IF(F2.GT.F3)GOTO 150 IF(N.GT.0)GOTO 165 135C1=(F3-F1)/(X3-X1) C2=(F2-F1)

44、/(X2-X1)-C1)/(X2-X3) GOTO 220 150H=H+H N=N+1 GOTO 80 165X4=0.5*(X2+X3) F4=F(X4) IF(F4.GT.F2)GOTO 205 几种常用的一维搜索算法几种常用的一维搜索算法 X1=X2 F1=F2 X2=X4 F2=F4 GOTO 135 205 X3=X4 F3=F4 GOTO 135 220 IF(ABS(C2).LT.E) GOTO 285 X4=0.5*(X1+X3-C1/C2) F4=F(X4) IF(F2.LT.1.0)GOTO 250 F5=F2 GOTO 255 250F5=1.0 几种常用的一维搜索算法

45、几种常用的一维搜索算法 255IF(ABS(F4-F2)/F5).LT.E) GOTO 300 IF(F4.GT.F2)GOTO 285 X1=X4 F1=F4 275H0=P*H0 GOTO 40 285X1=X2 F1=F2 GOTO 275 300WRITE(*,305) F4,X4 305 FORMAT(1X,最优目标函数值最优目标函数值=,G15.6/1X,最优解最优解X=,G15.6) STOP END 多元函数无约束最优化问题的直接搜索法多元函数无约束最优化问题的直接搜索法 多元函数无约束最优化问题一般采用直接搜索法。工程上许多问题多元函数无约束最优化问题一般采用直接搜索法。工程

46、上许多问题 的数学模型往往难以用解析法求出目标函数的极值，只能采用逐步的数学模型往往难以用解析法求出目标函数的极值，只能采用逐步 逼近的直接法。在最优化方法中有许多直接搜索法，可以分成两大逼近的直接法。在最优化方法中有许多直接搜索法，可以分成两大 类，即：类，即： 1、不求导的算法。不必计算目标函数的导数，只靠计算目标函数值、不求导的算法。不必计算目标函数的导数，只靠计算目标函数值 来搜索，这种方法发展较早，其中有的算法收敛较慢。主要有坐来搜索，这种方法发展较早，其中有的算法收敛较慢。主要有坐 标轮换法、步长加速法标轮换法、步长加速法(模矢搜索法模矢搜索法)、方向加速法、方向加速法(共扼方向法

47、、共扼方向法、 Powell法法)、单纯形法和随机搜索法等。、单纯形法和随机搜索法等。 2、以求目标函数的导数为基础的算法。这种方法提出较晚但发展较、以求目标函数的导数为基础的算法。这种方法提出较晚但发展较 快，也较为有效。主要有最速下降法快，也较为有效。主要有最速下降法(一阶梯度法一阶梯度法)、共扼梯度法、共扼梯度法、 拟牛顿法、变尺度法等。拟牛顿法、变尺度法等。 本章主要给大家介绍坐标轮换法、步长加速法、方向加速法单纯形加本章主要给大家介绍坐标轮换法、步长加速法、方向加速法单纯形加 速法和变尺度法等。速法和变尺度法等。 5.4 坐标轮换法坐标轮换法 坐标轮换法也叫变量轮换法，这是一种最古老

48、的直接优坐标轮换法也叫变量轮换法，这是一种最古老的直接优 化方法，它的思路非常简单，即依次在各个坐标方向上化方法，它的思路非常简单，即依次在各个坐标方向上 作一维搜索，且每次搜索都以前一次搜索的最好点作为作一维搜索，且每次搜索都以前一次搜索的最好点作为 起点。下面先以二元函数为例来进行分析，然后给出起点。下面先以二元函数为例来进行分析，然后给出n 元函数的一般算法。元函数的一般算法。 设某二元函数设某二元函数S=f(X)=f(x1,x2),其等高线见下图。设极值其等高线见下图。设极值 存在的区间为存在的区间为a1x1b1, a2x2b2, 用用 分别表示分别表示x1、x2坐标方向。坐标方向。

49、TT ee) 1 , 0 () 0 , 1 ( 21 、 一、坐标轮换法的算法一、坐标轮换法的算法 坐标轮换法坐标轮换法 搜索过程如下：搜索过程如下： 1、设从、设从X(0)(x1(0), x2(0)出发，先出发，先 固定固定x1=x1(0)不变，求以不变，求以x2为单为单 变量的目标函数变量的目标函数 f(x2)=f(x2(0) + )f( ) 的极值，可利用上一节介绍的的极值，可利用上一节介绍的 一维搜索方法求以一维搜索方法求以 为单变量为单变量 的目标函数的极值，从而可定的目标函数的极值，从而可定 出最佳步长因子出最佳步长因子 ，得：，得： 2 1 2 2 2 )( , )1()1(1

50、2 )0( 2 )0( 1 )1( XfSxxX 坐标轮换法坐标轮换法 )( , )2()2(1 2 )0( 2 1 1 )0( 1 )2( XfSxxX 2、然后固定、然后固定x2=x2(1)= x2(0)+ 不变，变动不变，变动x1，求以，求以x1为单变量的目标函为单变量的目标函 数数 f(x1)=f(x1(0) + )f( )的极值，亦即求以的极值，亦即求以 为单变量的目标函数为单变量的目标函数 的极值，从而可定出最佳步长因子的极值，从而可定出最佳步长因子 ，得：，得： 1 2 1 1 1 1 1 3、因为、因为S(2)优于优于S(1) ，因此在进行了一轮坐标轮换后进一步搜索时，搜，因此

51、在进行了一轮坐标轮换后进一步搜索时，搜 索区间已缩短为：索区间已缩短为：x1(1) x1b1, x2(1) x2b2。在新的区间中重复以。在新的区间中重复以 上步骤，每次搜索不仅可使目标函数值得到改善，而且可以把搜索上步骤，每次搜索不仅可使目标函数值得到改善，而且可以把搜索 区间进一步缩小，直到达到给定得精度为止。区间进一步缩小，直到达到给定得精度为止。 坐标轮换法坐标轮换法 对对n元函数，坐标轮换法的一般步骤为：元函数，坐标轮换法的一般步骤为： 记记n个坐标方向为：个坐标方向为： T n T T e e e )1 , 0 , 0 , 0( )0 , 0 , 1 , 0( )0 , 0 , 0

52、 , 1( 2 1 则在第则在第j个坐标方向个坐标方向 上搜索即为单变量极值问题：上搜索即为单变量极值问题： j e j j eXf )1( min 坐标轮换法坐标轮换法 其中其中X(j-1)为在为在 方向上搜索得到的最好点。所谓在方向上搜索得到的最好点。所谓在 方方 向上搜索是指固定其它向上搜索是指固定其它n-1个变量不变，求以个变量不变，求以xj为单变量为单变量 的目标函数的极值。算法如下：的目标函数的极值。算法如下： 1 j e j e ；，令令，给给定定允允许许误误差差取取10 )0( jEX n 作一维搜索，确定作一维搜索，确定 ： j jj j j j eXfeXf )1()1(

53、min jj )j()j( eXX 1 令令 若若j=n(已完成一轮坐标轮换已完成一轮坐标轮换)，转；若，转；若jf(B1)，即无改善，转，即无改善，转8；否则，在；否则，在R1点进行局部点进行局部 探测。方法同步骤探测。方法同步骤3；对；对n个变量进行局部探测后，得个变量进行局部探测后，得 到第三个基点到第三个基点B2=R1,n。 步长加速法步长加速法 6、像前述那样，建立新的模矢，得新的参考点、像前述那样，建立新的模矢，得新的参考点R2= 2B2-B1， 一般情况为：一般情况为：Ri= Bi-1+2(Bi-Bi-1)= 2Bi-Bi-1； 7、如果对第、如果对第i个参考点个参考点Ri进行所

54、有的局部探测均不能改善结进行所有的局部探测均不能改善结 果，但果，但f(Ri)f(Bi)，则退至，则退至Bi(即令即令Bi+1=Bi=Ri+1)，依此作为参，依此作为参 考点进行新的局部探测。如果得到一个好点，则进行模考点进行新的局部探测。如果得到一个好点，则进行模 矢移动，否则缩短步长，即令矢移动，否则缩短步长，即令i=i/2； 9、计算终止准则：、计算终止准则：i缩小到缩小到i时计算终止时计算终止(为要求的计算为要求的计算 精度精度)。 步长加速法步长加速法 该方法求得的是局部极小点，当目标函数的交互作用很该方法求得的是局部极小点，当目标函数的交互作用很 强时，搜索容易失败。模矢图如下：强

55、时，搜索容易失败。模矢图如下： 步长加速法可用于油库、计量站、转油站和联合站等的步长加速法可用于油库、计量站、转油站和联合站等的 最佳位置的确定。最佳位置的确定。 步长加速法步长加速法 例：例：拟在下图所示的场地上建一小型油库，铁路岔道、拟在下图所示的场地上建一小型油库，铁路岔道、 公路、上下水管道、煤气管道及电力线均需由图示公路、上下水管道、煤气管道及电力线均需由图示 的枢纽点接入，要求铁路支线由垂直方向引进。单的枢纽点接入，要求铁路支线由垂直方向引进。单 位长度道路、铁路及管道等的修建费见下表。工程位长度道路、铁路及管道等的修建费见下表。工程 地质勘察表明，距铁路以下地质勘察表明，距铁路以

56、下5米的硬粘土层是由铁路米的硬粘土层是由铁路 向公路方向倾斜的，坡度为向公路方向倾斜的，坡度为1/100，其上被一层软沉，其上被一层软沉 积土所覆盖，故建造油罐和泵房时需打支撑桩积土所覆盖，故建造油罐和泵房时需打支撑桩150根，根， 试确定最佳的库址。试确定最佳的库址。 项目项目铁路铁路公路公路电力线电力线 上水管和上水管和 煤气管煤气管 下水管下水管支撑桩支撑桩 造价，元造价，元/米米15012030504015 解：如上图所示，取横向为解：如上图所示，取横向为xl轴，纵向为轴，纵向为x2轴，油库中心位轴，油库中心位 置可表示为置可表示为(xl, x2)。上述问题实际上是一个二元目标。上述问

57、题实际上是一个二元目标 函数求极小值的问题。各种管道、道路、铁路岔道和函数求极小值的问题。各种管道、道路、铁路岔道和 电力线的长度分别为：电力线的长度分别为： 铁路岔道长度为：铁路岔道长度为：x2千米，千米，cl=150元元/米米=15万元万元/千米千米 上水管和煤气管长度为：上水管和煤气管长度为：x12+(x2-2)21/2千米，千米，c2=5万元万元/千米千米 下水管长度为：下水管长度为：(x1-0.2)2+(5.6-x2)21/2千米，千米，c3=4万元万元/千米千米 电力线长度为：电力线长度为：(5-x1)2+x221/2千米，千米，c4=3万元万元/千米千米 道路长度为道路长度为:

58、(3-x1)2+(4.8-x2)21/2千米千米, c5=12万元万元/千米千米 随库址不同，每根支撑桩需增加的长度为：随库址不同，每根支撑桩需增加的长度为：0.01x2千米，千米， c6=1.5万元万元/千米。千米。 步长加速法步长加速法 设总的建造费用设总的建造费用(只考虑随库址而变的费用，相同部分不只考虑随库址而变的费用，相同部分不 考虑考虑), S=f(x1, x2)，则问题的数学模型为：，则问题的数学模型为： 12 1 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 1221 5 2 60 50 . 5 . 101. 0150)8 . 4()3(12)5(3 )6 . 5

59、()2(4)2( 515),( min 2 1 2 1 1 2 1 2 1 xx x ts xxxxx xxxxxxxf 步长加速法步长加速法 求解过程如下：求解过程如下： 1、将初始参考点取在接近场地中心的位置，即、将初始参考点取在接近场地中心的位置，即 )5 . 2 , 5 . 2(km5 . 2km5 . 2 00 0 2 0 1 RBxx，则，则， ).,(),.(.100010km10 21 ，即即取取初初始始步步长长为为 f(R0)=f(2.5, 2.5)=110.164万元万元 2、先沿、先沿xl轴作探测性移动：轴作探测性移动： )(932.109)5 . 2 , 4 . 2()

60、( )(456.110)5 . 2 , 6 . 2()( 010 010 RffRf RffRf 9321095242 011001 .)R(f).,.(RR ，故故 步长加速法步长加速法 3、再沿、再沿x2轴作探测性移动：轴作探测性移动： )(400.109)4 . 2 , 4 . 2()( )(450.110)6 . 2 , 4 . 2()( 01201 01201 RffRf RffRf ).,.(RR4242 20102 故故 4、得第一次探测性移动的基点、得第一次探测性移动的基点B1=R02=(2.4,2.4)，f(B1)=109.400 进行模矢移动：进行模矢移动：R1= 2B1-