第07章无约束问题

在科学管理和其他领域中，很多实际问题可以归结为线性规划问题，其目标函数和约束条件都是自变量的一次函数。但是，还有另外一些问题，其目标函数和(或)约束条件很难用线性函数来表达。如果目标函数或约束条件中含有非线性函数，就称这种规划问题为非线性规划问题。解这种问题要用非线性规划的方法以。由于很多实际问题要求进一步精确化以及电子计算机的发展，使非线性规划在近几十年来得以快速发展。目前，它已成为运筹学的重要分支之一，并在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。02二月2023非线性规划

一般来说，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也水像线性规划有单纯形法等通用方法，非线性规划目前没有适于各种问题的一般算法，各个方法都有自己特定的适用范围。这是需要人们更深入地进行研究的一个领域。

为了叙述方便，用大写字母代表n维欧氏空间中的向量(点)，而以相应的小字字母代表该向量的分量(点的坐标)。此外，所用到的向量，均规定为列向量。02二月2023非线性规划第七章无约束问题OperationalResearch(OR)东北农业大学工程学院王吉权7.1基本概念7.2一维搜索7.3无约束极值问题的解法02二月20234第七章非线性规划1.问题的提出

让我们先看两个例子。

例1某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均为0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。02二月202357.1基本概念7.1.1引言

设该公司计划经营第一种产品x1件，第二种产品x2件。根据题意，其营业额为f(X)=30x1+450x2

由于服务时间的限制，该计划必须满足0.5x1+(2+0.25x2)x2800此外，这个问题还应满足x10,x20

如此，得到这个瓿的数学模型如下：02二月202367.1基本概念7.1.1引言例2为了进行多属性问题(假设有n个属性)的综合评价，就需要确定每个属性的相对重性，即求它们的权重。为此将各属性的重要性(对评价者或决策者而言)进行两两比较从而得出如处判断矩阵02二月202377.1基本概念7.1.1引言其中，元素aij是第i个属性的重要性与第j个属性的重要性之比。

现需从判断矩阵求出各属性的权重wi(i=1,2,…,n)。为了使求出的权向量W=(w1,w2,…,wn)T在最小二乘意义上能最好的反映判断矩阵的估计，由aijwi/wj，可得02二月202387.1基本概念7.1.1引言

例1的目标函数为自变量的线性函数，但其第一个约束条件却是自变量的二次函数。因而它是非线性规划问题。例2的目标函数是自变量的非线性函数，所以它也是非线性规划问题。02二月202397.1基本概念7.1.1引言非线性规划数学模型的一般形式是：其中，X=(x1,x2,…,xn)T是n维欧氏空间En中的点(向量)，f(X)为目标函数，hi(X)0，gj(X)0为约束条件。02二月202310(7-1)2.非线性规划问题的数学模型(7-2)(7-3)7.1基本概念7.1.1引言

由于maxf(X)=-min[-f(X)]，当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标函数极小化，这无损于一般性。

若某约束条件是“”不等式时，仅需用“-1”乘该约束的两端，始可将这个约束变为“”的形式。

由于等式约束hi(X)=0等价于下述两个不等式约束：02二月2023117.1基本概念7.1.1引言因而，也可将非线性规划的数学模型写成以下形式02二月202312(7-4)(7-5)7.1基本概念7.1.1引言

图示法可以给人以直观概念，当只有两个自变量时，非线性规划问题也可像线性规划那样用图法来表示(如图7-1所示)。

考虑非线性规划问题02二月2023132.非线性规划问题的图示(7-6)(7-7)7.1基本概念7.1.1引言图7-102二月202314x1x26320236ABCDf(X)=2f(X)=47.1基本概念7.1.1引言若令其目标函数f(X)=c其中，c为某一常数，则(7-8)式代表目标函数值等于c的点的集合，它一般为一条曲线或一张曲面，通常称其为等值线或等值面。对于这个例子来说，若令目标函数(7-6)式分别等于2和4，就得到相应的两条圆形等值线(图7-1)。由图可见，等值线f(X)=2和约束条件直线AB相切，切点D即为此问题的最优解：x1*=x3*=3，其目标函数值f(X*)=2。02二月202315(7-8)7.1基本概念7.1.1引言

在这个例子中，约束条件(6-7)式对最优解是有影响的。

现若以h(X)=x1+x2-60代替约束条件(7-7)式，则非线性规划问题(7-6)式、(7-9)式的最优解是x1=x2=2，即图6-1中的C点(这时f(X)=0)。由于最优点位于可行域的内部，故对这个问题的最优解来说，约束(7-9)式事实上是不起作用的。在求这个问题的最优解时，可不考虑约束条件(7-9)式，就相汉于没有这个约束一样。02二月202316(7-9)7.1基本概念7.1.1引言

在高等数学课程中，已学过一元函数和多元函数的极值问题，现仅扼要说明如下。1.局部极值和全局极值

由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是在整个可行域的全局最优解。非线性规划则不然，有时求出的某个解虽是一部分可行域中的极值点，但却并不一定是整个可行域上的全局最优解。02二月2023177.1基本概念7.1.2极值问题

设f(X)为定义在n维欧氏空间En的某一区域R上的n元实函数，其中X=(x1,x2,…,xn)T。对于X*R，如果存在某个>0，使所有与X*的距离小于的XR(即XR且||X-X*||<)均满足不等式f(X)f(X*)，则称X*为f(X)在R上的局部极小点(或相对极小点)，f(X*)为局部极小值。若对于所有XX*且与X*的距离小于的XR，f(X)>f(X*)，则称X*为f(X)在R上的严格局部极小点，f(X*)为严格局部极小值。02二月2023187.1基本概念7.1.2极值问题

若点X*R，而对于所有XR都有f(X)f(X*)，则称X*为f(X)在R上的全局极小点，f(X*)为全局极小值。若对于所有XR且XX*，都有f(X)>f(X*)，则称X*为f(X)在R上的严格全局极小点，f(X*)为严格全局极小值。

如将上述不等式反向，即可得到相应的极大点和极大值的定义。

下面仅就极小点及极小值加以说明，而且主要研究局部极小。02二月2023197.1基本概念7.1.2极值问题

2.极值点存在的条件

现说明极值点存在的必要条件和充分条件。

定理1(必要条件)：设R是n维欧氏空间En上的某一开集，f(X)在R上有一阶连续偏导数，且在点X*R取得局部极值，则必有或f(X*)=0上式中02二月202320(7-10)(7-11)(7-12)7.1基本概念7.1.2极值问题为函数f(X)在X*处的梯度。由数学分析知道，f(X)的方向为f(X)的等值面(等值线)的法线(在X处）方向，沿这个方向函数值增加最快。

满足式(7-10)或式(7-11)的点称为平稳点或驻点，在区域内部，极值点必为平稳点，但平稳点不一定是极值点。02二月2023217.1基本概念7.1.2极值问题

定理2(充分条件)设R是n维欧氏空间En上的某一开集，f(X)在R上有二阶连续偏导数，X*R，若f(X*)=0，且对任何非零向量ZEn有ZTH(X*)Z>0则X*为f(X)的严格局部极小点

此处H(X*)为f(X)在点X*处的海赛(Hesse)矩阵：

02二月202322(7-13)(7-14)7.1基本概念7.1.2极值问题

需要指出，定理2中的充分条件(7-13)式并不是必要的。可以举出这样的例子：X*是f(X)的极小点，但却不满足条件(7-13)式。例如f(X)=x*，它的极小点是x*=0，但f’’(x*)=0，这不满足(7-13)式。

二次型是X=(x1,x2,…,xn)T的二次齐次函数，它在研究非线性最优化中具有重要作用。现考虑二次型ZTHZ。若对于任意Z0(即Z的元素不全为0)，二次型ZTHZ的值总是正的，即ZTHZ>0，则称该二次型是正定的；若对于任意Z0总有ZTHZ0，则称其为半正定；若对于任意Z0总有ZTHZ<0，则称其为负定；若对于任意02二月2023237.1基本概念7.1.2极值问题Z0总有ZTHZ0，则称其为半负定。如果对某些Z0总有ZTHZ>0，而对另一些Z0总有ZTHZ<0，即它既非正定，也非负定，则称其为不定的。由线性代数知道，二次型ZTHZ为正定的充要条件，是它的矩阵H的左上角各阶主子式都大于0；而它为负定的充要条件，是它的矩阵H的左上角各阶主子式依次负正相同。

现以hij表示矩阵H的元素，上述条件为，当二次型正定时：02二月2023247.1基本概念7.1.2极值问题当二次型负定时：二次型ZTHZ为正定、负定或不定时，其对称矩阵H分别称为正的、负定的或不定的。定理2中的条件(7-13)式，就等于是说其海赛矩阵在X*处正定。02二月2023257.1基本概念7.1.2极值问题

凸集、凸函数以及凸函数的极值的性质，是研究非线性规划问题所不可缺少的内容。凸集的概念在讲线性规划时已作过说明，因而这里简要说明凸函数的有关问题。1.什么是凸函数和凹函数

设f(X)为定义在n维欧氏空间En中某个凸集R上的函数，若对任何实数(0<<1)以及R中的任意两点X(1)和X(2)，恒有f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))则称f(X)为定义在R上的凸函数。02二月2023267.1基本概念7.1.3凸函数和凹函数(7-15)若对任意实数(0<<1)和X(1)X(2)R恒有f(X(1)+(1-)X(2))<f(X(1))

+(1-)f(X(2))则称f(X)为定义在R上的严格凸函数。

将(6-15)式和(6-16)式中的不等号反向，即可得到凹函数和严格凹函数的定义。显然，若函数f(X)是凸函数(严格凸函数)，则-f(X)一定是凹函数(严格凹函数)。

凸函数和凹函数的几何意义十分明显，若函数图形上任两点的联线处处都不在这个函数图形的下方，它当然是下凸的(图7-2(a))。凹函数则是下凹的(上凸的)(图7-2(b)).线性函数即可看作凸函数，也可看作凹函数。02二月202327(7-16)7.1基本概念7.1.3凸函数和凹函数图7-202二月202328f(x)Ox(1)x(2)x(1)+(1-)x(2)xf(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))f(x)Ox(1)x(2)x(1)+(1-)x(2)xf(x(1)+(1-)x(2))f(x(1))+(1-)f(x(2))图7-2(a)凸函数

图7-2(b)凹函数7.1基本概念7.1.3凸函数和凹函数图7-202二月202329第一节基本概念1.3凸函数和凹函数f(x)Ox(1)x(2)xf(x(2))f(x(1))图7-2(c)非凸、非凹函数

2.凸函数的性质

凸函数具有如下性质：性质1设f(X)为定义在R上的也是凸函数，则对任意实数0，函数也是f(X)定义在R上的凸函数。

性质2设f1(X)和f2(X)为定义的凸集R上的两个凸函数，则其和f(X)=f1(X)+f2(X)仍为定义在R上的凸函数。

因为f1(X)和f2(X)都是定义在R上的凸函数，故对R上的任两点X(1)和X(2)以及任意实数(0<<1)恒有f1(X(1)+(1-)X(2))f1(X(1))

+(1-)f1(X(2))f2(X(1)+(1-)X(2))f2(X(1))

+(1-)f2(X(2))02二月2023307.1基本概念7.1.3凸函数和凹函数将上述两端分别相加得f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))故f(X)也是R上的凸函数。

由以上两个性质立刻推得：有限个凸函数的非负线性组合1f1(X)+2f2(X)+…+mfm(X)i0,i=1,2,…,m仍为凸函数。02二月2023317.1基本概念7.1.3凸函数和凹函数

性质3设f(X)为定义在凸集R上的凸函数，则对任一实数，集合S={X|XR,f(X)}是凸集(S称为水平集)。

证明：

任取X(1)S和X(2)S，则有f(X(1))，f(X(2))。

由于R为凸集，帮对任意实数(0<<1)，X(1)+(1-)X(2)R，又因为f(X)为凸函数，故f(X(1)+(1-)X(2))f(X(1))

+(1-)f(X(2))这就表明点X(1)+(1-)X(2)S，于是，S为凸集。02二月202332(7-17)7.1基本概念7.1.3凸函数和凹函数

3.函数凸性的判定

现在来研究怎样判断一个函数是凸函数，当然可以直接依据定义去判断。对于可微凸函数，也可利用下述两个判别定理。

定理3(一阶条件)设R为n维欧氏空间En上的某一开集，f(X)在R上有一阶连续偏导数，则f(X)为R上的凸函数的充要条件是，对任意两个不同点X(1)R和X(2)R，恒有

f(X(2))f(X(1))

+f(X(1))(X(2)-X(1))02二月202333(7-18)7.1基本概念7.1.3凸函数和凹函数

证明必要性：

设f(X)为R上的凸函数，则对任何(0<<1)有f(X(2)+(1-)X(1))f(X(2))

+(1-)f(X(1))于是

令+0，上式左端的极限为f(X(1))T(X(2)-X(1))即

f(X(2))f(X(1))

+f(X(1))(X(2)-X(1))02二月2023347.1基本概念7.1.3凸函数和凹函数

充分性：任取X(1)R及X(2)R，现令X=X(1)+(1-)X(2)，0<<1分别以X(1)和X(2)为式(7-18)中的X(2)，以X为式(7-18)中的X(1)，则

f(X(1))f(X)

+f(X)(X(1)-X)f(X(2))f(X)

+f(X)(X(2)-X)用乘上面的第一式，用(1-)乘上面的第二式，然后两端相加02二月2023357.1基本概念7.1.3凸函数和凹函数f(X(1))+(1-)f(X(2))f(X)+f(X)T[X(1)-X+(1-)(X(2)-X)]=f(X)=f(X(1)+(1-)X(2))从而可知f(X)为R上的凸函数。

若式(7-18)为平桥不等式，它就是严格凸函数的充要条件。

凸函数的定义式(7-15)，本质上是说凸函数上两点间的线性插值不低于这个函数的值；而定理3则是说，基于某点导数的线性近似不高于这个函数的值(图7-3)。02二月2023367.1基本概念7.1.3凸函数和凹函数图7-302二月202337f(X)OX(1)Xf(X(1))+f(X(1))(X-X(1))7.1基本概念7.1.3凸函数和凹函数

定理4(二阶条件)设R为n维欧氏空间En上的某一开集，f(X)在R上有二阶连续偏导数，则f(X)为R上的凸函数的充要条件是，f(X)的海赛矩阵H(X)在R上处处半正定。

证明先证明必要性。

设f(X)为R上的凸函数。任取XR和ZEn，现证ZTH(X)Z0

因R为开集，故存在，使当时，有X+ZR。由定理3可得f(X+Z)f(X)+f(X)TZ02二月2023387.1基本概念7.1.3凸函数和凹函数再由泰勒公式f(X+Z)f(X)+f(X)TZ+0.52ZTH(X)Z+o(2)其中由以上两式得0.52ZTH(X)Z+o(2)0从而0.5ZTH(X)Z+o(2)/20令0，则得ZTH(X)Z0

02二月2023397.1基本概念7.1.3凸函数和凹函数即H(X)为半正定矩阵。下面证明充分性。设对任意XR，H(X)为半正定矩阵，任取，由泰勒公式，有其中(0,1)。

因R为凸集，。再由假设知为半正定，从而由定理3，f(X)为R上的凸函数。02二月2023407.1基本概念7.1.3凸函数和凹函数若对一切XR，f(X)的海赛矩阵都是正定的，则f(X)是R上的严格凸函数。

对于凹函数可以得到和上述类似的结果。

例3试证明f(X)=-x12-x22为凹函数。

证明首先由定义证明f1(x1)=-x12为凹函数。

任意指定两点a1和a2，看下述各式是否成立？-[a1+(1-)a2]2(-a12)+(1-)(-a22)或a12(-2)-2a1a2(-2)+a22(-2)0或(-2)(a1-a2)2002二月2023417.1基本概念7.1.3凸函数和凹函数由于0<<1，故-2>0。显然，不管a1和a2取什么值，总有(-2)(a1-a2)20成立，从而证明f1(x1)=-x12为凹函数。用同样的方法可以证明f2(x2)=-x22也是凹函数。根据性质2，f(X)=-x12-x22为凹函数。

再用定理3证明。任意选取一点X(1)=(a1,b1)T，第二点X(2)=(a2,b2)T。如此f(X(1))=-a12-b12

f(X(2))=-a22-b22

f(X)=(-2x1,-2x2)Tf(X(1))=(-2a1,-2b1)T现看下述各式是否成立？02二月2023427.1基本概念7.1.3凸函数和凹函数或-a22-b22-a12-b12-2a1(a2-a1)-2b1(b2-b1)或-(a22-2a1a2+a12)-(b22-2b1b2+b12)0或-(a2-a1)2-(b2-b1)20不管a1、a2、b1和b2取什么值，上式均成立，从而得证。02二月2023437.1基本概念7.1.3凸函数和凹函数

下面用定理4证明。由于其海赛矩阵处处负定，故f(X)为(严格)凹函数。02二月2023447.1基本概念7.1.3凸函数和凹函数

前已指出，函数的局部极值并不一定等于它的最小值，前者只不过反映了函数的局部性质。而最优化的目的，往往是要求函数在整个域中的最小值(或最大值)和最小点(或最大点)。为此，必须将所得的全部极小值进行比较(有时尚需考虑边界值)，以便从中选出最小者。然而，对于定义在凸集上的凸函数来说，则用不着进行这种麻烦的工作，它的极小值就等于其最小值。

定理5若f(X)为定义在凸集R上的凸函数，则它的任一极小点就是它在R上的最小点(全局极小点)，而且它的极小点形成一个凸集。02二月2023457.1基本概念7.1.3凸函数和凹函数

证明设X*是一个局部极小点，则对于充分小的邻域N(X*)中的一切X，均有f(X)f(X*)

令Y是R中的任一点，对于充分小的，0<<1，就有((1-)X*+Y)N(X*)从而f((1-)X*+Y)f(X*)由于f(X)为凸函数，故(1-)f(X*)+f(Y)f((1-)X*+Y)02二月2023467.1基本概念7.1.3凸函数和凹函数

将上述两个不等式相加，移项后除以，得到f(X)f(X*)这就是说，X*是全局极小点。

由性质3，所有极小点的集合形与一个凸集。

定理6

设是定义在凸集R上的可微凸函数，若存在点X*R，使得对于所有的XR有f(X*)T(X-X*)0则X*是f(X)在R上的最小点(全局极小点)。02二月2023477.1基本概念7.1.3凸函数和凹函数

证明：由定理3f(X)f(X*)+f(X*)T(X-X*)如此，对所有X*R有f(X)f(X*)

一种极为重要的情形是，当点X*是R的内点时，这时式(7-19)对任意X-X*都成立，这就意味着可将式(7-19)改为f(X*)=0

以上两个定理说明，定义在凸集上的凸函数的平稳点，就是其全局极小点。全局极小点并不一定是唯一的，02二月2023487.1基本概念7.1.3凸函数和凹函数但若为平桥凸函数，则其全局极小点就是唯物主义一的了。02二月2023497.1基本概念7.1.3凸函数和凹函数现在再回到非线性规划式(7-1)～(7-3)。和线性规划类似，把满足约束条件式(7-2)和式(7-3)的点称做可行点(可行解)，所有可行点的集合称做可行域。若某个可行解使目标函数式(7-1)为最小，就称它为最优解。

考虑非线性规划02二月2023507.1基本概念7.1.4凸规则假定其中f(X)为凸函数，gj(X)(j=1,2,…,l)为凹函数(或者说-gj(X)为凸函数)，就样的非线性规划称为凸规划。可以证明，上述凸规划的可行域为凸集，其局部最优解即为全局最优解，而且其最优解的集合形成一个凸集。当凸规划的目标函数f(X)为严格凸函数时，其最优解必定唯一(假定最优解存在)。由此可见，凸规划是一类比较简单而又具有重要理论意义的非线性规划。

由于线性函数即可视为凸函数，又可视为凹函数，故线性规划也属于凸规划。02二月2023517.1基本概念7.1.4凸规则

例4试分析非线性规划minf(X)=x12+x22-4x1+4

解：f(X)和g2(X)的海赛矩阵的行列式分别是02二月2023527.1基本概念7.1.4凸规则

知f(X)为严格凸函数，g2(X)为凹函数。由于其他约束条件均为线性函数，所以这是一个凸规划问题(见图7-4)。C点为其最优点：X*=(0.58,1.34)T，目标函数的最优值为f(X*)=3.8。02二月2023537.1基本概念7.1.4凸规则图7-402二月2023547.1基本概念7.1.4凸规则1234-112.2546.25RCg1(X)=0g2(X)=0x2x10目标函数等值线

为了求某可微函数(假定无约束)的最优解，根据前面的叙述，可如下进行：令该函数的梯度等于0，由此求得平稳点；然后用充分条件进行判别，求出所要的解。对某些较简单的函数，这样做有时是可行的；但对一般n元函数f(X)来说，由条件f(X)=0得到的常是一个非线性方程组，解它相当困难。对于不可微函数，当然谈不上使用这样的方法。为此，常直接使用迭代法。02二月2023557.1基本概念7.1.5下降迭代算法

迭代法的基本思想是：为了求函数f(X)的最优解，首先给定一个初始估计X(0)，然后按某种规则(即算法)找出比X(0)更好的解X(1)(对极小化问题，f(X(1))<f(X(0))；对极大化问题f(X(1)>f(X(0)))，再按此种规则找出比X(1)更好的解X(2)……。如此即可得到一个解的序列{X(k)}。若这个解序列有极限X*，即则称它收敛于X*。02二月2023567.1基本概念7.1.5下降迭代算法

若这算法是有效的，那么它所产生的解的序列将收敛于该问题的最优解。不过，由于计算机只能进行有限次迭代，一般说很难得到准确解，而保能得到近似解。当满足所要求的精度时，即可停止迭代。

若由某算法所产生的解的序列{X(k)}使目标函数f(X(k))逐步减少，就称这算法为下降算法。“下降”的要求比较容易实现，它包含了很多种具体算法。显然，求解极小化问题应采用下降算法。

现假定已迭代到点X(k)，见图7-5。02二月2023577.1基本概念7.1.5下降迭代算法图7-502二月2023587.1基本概念7.1.5下降迭代算法X*101520P(k)X(k)kP(k)X(k+1)若从X(k)出发沿任何方向移动都不能使目标函数值下降，则X(k)是一局部极小点，迭代停止。若从X(k)出发至少存在一个方向可使目标函数值有所下降，则可选定能使目标函数值下降的某方向P(k)，沿这个方向迈进适当的一步，得到下一个迭代点X(k+1)，并使f(X(k))<f(X(k+1))。这相当于在射线

X=X(k)+P(k)

上选定新点X(k+1)=X(k)+kP(k)

其中，

P(k)称为搜索方向；k称为步长或步长因子。下降迭代算法的可总结如下：(1)选定某一初始点X(0)，并令k:=0；(2)确定搜索方向P(k)；(3)从X(k)出发，沿方向P(k)求步长k，以产生下一个迭代点X(k+1)；02二月2023597.1基本概念7.1.5下降迭代算法

(4)检查得到的新点X(k+1)是否为极小点或近似极小点。若是，则停止迭代。否则，令k:=k+1，转回(2)继续进行迭代。

在以上步骤中，选取搜索方向P(k)是最关键的一步，有关各种算法的区分，主要在于确定搜索方向的方法不同。

确定步长k可选用不同的方法。最简单的一种是令它等于某一常数(例如k=1)，这样做计算简便，但不能保证使目标函数值下降。第二种称为可接受点算法，只要能目标函数值下降，可任意选取步长k。第三种方法02二月2023607.1基本概念7.1.5下降迭代算法是基于沿搜索方向使目标函数值下降最多，即沿射线X=X(k)+P(k)求目标函数f(X)的极小(注意，这里是指无约束问题)k：minf(X(k)+P(k))由于这项工作是求以为变量的一元函数f(X(k)+P(k))的极小点k，故常称这一过程为(最优)一维搜索或线性搜索，这样确定的步长为最佳步长。

一维搜索有个十分重要的性质：在搜索方向上所得最优点处目标函数的梯度和该搜索方向正交。02二月2023617.1基本概念7.1.5下降迭代算法

定理7

设目标函数f(X)具有一阶连续偏导数，X(k+1)按下述规则产生k：minf(X(k)+P(k))X(k+1)=X(k)+kP(k)则有f(X(k+1))TP(k)=0

证明构造函数()=f(X(k)+P(k))，则得即k为()的极小点。此外’()=f(X(k)+P(k))TP(k)。02二月2023627.1基本概念7.1.5下降迭代算法(7-21)

由’()|

=

k=0，可得f(X(k)+kP(k))TP(k)=f(X(k+1))TP(k)定理得证。

式(7-21)的几何意义见下图。02二月2023637.1基本概念7.1.5下降迭代算法X(k)X(k+1)f(X)=f(X(k+1))P(k)f(X(k+1))3020

对一个好的算法，不仅要求它产生的点列能收敛到问题的最优解，还要求具有较快的收敛速度。设序列{X(k)}收敛于X*，若存在与迭代次数k无关的数0<<和1，使k从某个k0>0开始都有||X(k+1)-X(k)||||X(k)–X*||成立，就称{X(k)}收敛的阶为，或{X(k)}阶收敛。

当=2时，称为二阶收敛，也可说{X(k)}具有二阶敛速。

当1<<2时，称超线性收敛。

当=1，且0<<1时，称线性收敛或一阶收敛。02二月2023647.1基本概念7.1.5下降迭代算法(7-22)

一般来讲，线性收敛的敛速是比较悭慢的，二阶收敛是很快的，超级性收敛介于以上两者之间。若一个算法具有超线性或更高的收敛速度，就认为它是一个很好的算法。

因为真正的最优解事先并不知道，为决定什么暑假停止计算，只能根据相继两次迭代的结果。常用的终止计算准则有以下几种。(1)根据相继两次迭代的绝对误差||X(k+1)-X(k)||<1|f(X(k+1))-f(X(k))|<202二月2023657.1基本概念7.1.5下降迭代算法(7-23)(7-24)

(2)根据相继两次迭代的相对误差这时要求分母不等于和不接近于0.(3)根据目标函数梯度的模足够小||f(X(k))||<5其中，1,2,3,4,5为事先给定的足够小的正数。02二月2023667.1基本概念7.1.5下降迭代算法(7-27)(7-26)(7-25)

前已述及，当用上述迭代法求函数的极小点时，常常要用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：(1)试探法(“成功—失败”法，斐波那契法，0.618法等)；(2)插值法(抛物线插值法，三次插值法等)；(3)微积分中的求根法(切线法，二分法等)。

限于篇幅，以下仅介绍斐波那契法和0.618法。02二月2023677.2一维搜索

设y=f(t)是敬意[a,b]上的下单峰函数(图7-7)，在此敬意内它有唯一极小点t*。若在此敬意内任取两点a1和b1，a1<b1，并计算函数值f(a1)和f(b1)，可能出现以下两种情形：02二月2023687.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)f(t)f(t)f(t)f(t)ttOat*a1b1bOat*a1b1b(a)(b)图7-7

(1)f(a1)<f(b1)(图7-7(a))，这时极小点t*必在区间[a,b1]内。(2)f(a1)f(b1)(图7-7(b))，这时极小点t*必在区间[a1,b]内。02二月2023697.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)02二月2023f(t)f(t)f(t)f(t)ttOat*a1b1bOat*a1b1b(a)(b)图7-7

这说明，只要在区间[a,b]内取两个不同点，并算出它们的函数值加以比较，就可以把搜索区间[a,b]缩小成[a,b1]或[a1,b](缩小后的区间仍需包含极小点)。现在如果要继续缩小搜索区间[a,b1](或[a1,b])，就只需在上述区间内再取一点算出其函数值，并与f(a1)或f(b1)加以比较即可。只要缩小后的区间包含极小点t*，则区间缩小得越小，就越接近于函数的极小点，但计算函数值的次数也就越多。这就说明区间的缩短率和函数值的计算次数有关。现在要问，计算函数值n次，能氢包含有极小点的区间缩小到什么程度呢?02二月2023707.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)

或者用Fn表示计算n个函数值能缩短为单位区间的最大原区间长度，显然F0=F1=1其原因是，只有当原区间长度本来就是一个单位长度时才不必计算函数值；此外，只计算一次函数值无法将区间缩短，故只有区间长度本来就是单位区间时才行。

现考虑计算函数值两次的情形，今后我们把计算函数值的点称做试算点或试点。02二月2023717.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-28)

在区间[a,b]内取两个不同点a1和b1(图7-8(a))，计算其函数值以缩短区间，缩短后的区间为[a,b1]或[a1,b]。显然，这两个区间长度之和必大于[a,b]的长度，也就是说，计算两次函数值一般无法把长度大于两个单位的区间缩成单位区间。但是，对于长度为两个单位的区间，可以如图7-8(b)那样选取试点a1和b1，图中为任意小的正数，缩短后的区间长度为1+。由于可任意选取，故缩短后的区间长度接近于一个单位长度。由此可得F2=2。02二月2023727.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)

根据同样的分析(见图7-9)可得02二月2023737.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)a1b1aaa1b1bb1201-1+(a)(b)图7-802二月2023747.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)2/3图7-91/3①②③n=33/52/5①②③n=41/5④5/83/8①②③n=52/8④1/8⑤F3=3,F4=5,F3=8,┅序列{Fn}可写成一个递推公式Fn=Fn-1

+Fn-2

n2利用式(7-29)，可依次算出各Fn的值，见表7-1。这些Fn就是通常所说的斐波那切契数。表7-102二月2023757.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)n0123456789101112Fn

1123581321345589144233(7-29)

由以上讨论可知，计算n次函数值所能获得的最大缩短率(缩短后的区间长度与原区间长度之比)为1/Fn。例如F10=10946，所以计算20个函数值即可把原长度为L的区间缩短为L/10496=0.00009L的区间。现在，要想计算n个函数值，而把区间[a0,b0]的长度缩短为原来长度的倍，即缩短后的区间长度为bn-1-an-1(b0-a0)则只要n足够大，能使下式成立即可Fn1/02二月2023767.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-30)其中，为一个正小数，称为区间缩短的相对精度。有时给出区间缩短的绝对精度，即要求bn-1-an-1显然，上述相对精度和绝对精度之间有如下关系=(b0-a0)

用这个方法缩短区间的步骤如下：(1)确定试点的个数n。根据相对精度，即可用式(7-30)算出Fn，然后由表7-1确定最小的n。(2)选取前两个试点的位置。02二月2023777.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-31)(7-32)

由式(7-29)可知第一次缩短时的两个试点位置分别是(见图7-10)：02二月2023787.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)a0b0t1t1'Fn-2Fn-1Fn-2Fn-1Fn-3Fn图7-10

它们在区间内的位置是对称的。(3)计算函数值f(t1)和f(t1’)，并比较它们的大小。

若f(t1)<f(t1’)，则取a1=a0

b1=t1’

t2’=t1并令02二月2023797.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-33)

否则，取a1=t1

b1=b0

t2=t1’并令(4)计算f(t2)和f(t2’)(其中的一个已经算出)，如第3步那样一步步迭代。计算试点的一般公式为02二月2023807.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)其中，k=1,2,…,n-1。

(5)当进行至k=n-1时tn-1=t’n-1=0.5(an-2+bn-2)这就无法借比较函数值f(tn-1)和f(t’n-1)的大小来确定最终区间，为此，取02二月2023817.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-34)其中为任意小的数。在tn-1和t’n-1这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值，并得最终区间[an-2,t’n-1]或[tn-1,bn-2]。

由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以昼少的函数求值次数，达到预定的某一缩短率。02二月2023827.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)(7-35)

例5试用斐波那契法求函数f(t)=t2-t+2的近似极小点和极小值，要求缩短后的区间长度不大于区间[-1,3]的0.08倍。

解：容易验证，在此区间上函数f(t)=t2-t+2为严格凸函数。为了进行比较，我们给出其精确解是：t*=0.5，f(t*)=1.75。

已知=0.08，Fn1/=1/0.08=12.5

查表7-1，n=6，a0=-1,b0=3t1=b0+F5(a0-b0)/F6=3+8(-1-3)/13=0.538t1’=a0+F5(b0-a0)/F6=-1+8(3-(-1))/13=1.46202二月2023837.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)f(t1)=0.5382-0.538+2=1.751f(t1’)=1.4622-1.462+2=2.675由于f(t1)<f(t1’)，故取a1=-1,b1=1.462,t2’=0.538t2=b1+F4(a1-b1)/F5=1.462+5(-1-1.462)/8=-0.077f(t2)=(-0.077)2-(-0.077)+2=2.083由于f(t2)>f(t2’)=1.751，故取a2=-0.077,b2=1.462,t3=0.538t3’=a2+F3(b2-a2)/F4=-0.077+3(1.462+0.077)/5=0.846f(t3’)=0.8462-0.846+2=1.870由于f(t3’)>f(t3)=1.751，故取a3=-0.077,b3=0.846,t4’=0.53802二月2023847.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)t4=b3+F2(a3-b3)/F3=0.846+2(-0.077-0.846)/3=0.231f(t4)=0.2312-0.231+2=1.822由于f(t4)>f(t4’)=1.751，故取a4=0.231,b4=0.846,t5=0.538。现令=0.01，则t5’=a4+(0.5+)(b4-a4)=0.231+(0.5+0.01)(0.846-0.231)=0.545f(t5’)=0.5452-0.545+2=1.752>f(t5)=1.751故取a5=0.231,b5=0.545。由于f(t5)=1.751<f(t5’)=1.752，所以以t5为近似极小点，近似极小值为1.751。02二月2023857.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)

缩短后的区间长度为0.545-0.231=0.314，0.314/4=0.0785<0.08，其整个计算过程示于图7-11中。02二月2023867.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)图7-1102二月2023877.2一维搜索7.2.1斐波那契(Fibonacci)法(分数法)a0b0a4b4t5t5'a3b3t4t4'a2b2t3t3'a1b1t2t2'a0b0-10123t1't1①②③⑤⑥④

由上节的论述可知，当用斐波那契法以n个试点来缩短某一缩短某一区间时，区间长度的第一次缩短率为Fn-1/Fn，其后各次分别为Fn-2/Fn-1,Fn-3/Fn-2,…,F1/F2现将以上数列分为奇数项F2k-1/F2k和偶数项F2k/F2k+1，可以证明，这两个数列收敛于同一个极限。

设当k时F2k-1/F2k

F2k/F2k+1由于02二月2023887.2一维搜索7.2.20.618法(黄金分割法)

故当k时同理可证将式(7-35)代入式(7-37)得即02二月2023897.2一维搜索7.2.20.618法(黄金分割法)(7-36)(7-37)

从而可得

若把式(7-37)代入式(7-36)，则得将式(7-35)代入式(7-37)得2++1=0故有02二月2023907.2一维搜索7.2.20.618法(黄金分割法)(7-38)

现用不变的区间缩短率0.618，代替斐波那契法每次不同的缩短率，就得到了黄金分割法(0.618法)。这个方法可以看成是斐波那契法的近似，实现起来比较容易，效果也相当好，因而易于为人们所接受。

当用0.618法时，计算n个试点的函数值可以把原区间[a0,b0]连续缩短n-1次，因为每次的缩短率均为，故最后的区间长度为(a0-b0)

n-1这就是说，当已知缩短的相对精度为时，可用下式计算试点个数n02二月2023917.2一维搜索7.2.20.618法(黄金分割法)

n-1

当然，也可以不预先计算试点的数目n，而在计算过程中逐次加以判断，看是否已满足了提出的精度要求。0.618法是一种等速对称进行的试探的方法，每次的试点均取在区间长度的0.618倍和0.382倍处。02二月2023927.2一维搜索7.2.20.618法(黄金分割法)(7-39)对于无约束极值问题的解法，这种问题可表述为minf(X),XEn前面曾指出，在求解上述问题时常使用迭代法，迭代法可大体分为两大类。一类要用到函数的一阶层数和(或)二阶层数，由于用到了函数的解析性质，故称为解法法；另一类在迭代过程中仅用到函数值，而不要求函数的解析性质，这类方法称为直接法。一般来说，直接法的收敛速度较慢，只是在变量较少时才适用。但是直接法的迭代简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体表达式时，它们的导数很难求得，或者根本不存在。这时解析法就无能为力了。02二月2023937.3无约束极值问题的解法(7-40)在求解无约束极值问题的解析法中，梯度法是最为古老但又十分基本的一种数值方法。它的迭代过程简单，使用方便宜，而且又是理解某些其他最优化方法的基础，所以我们先来说明这一方法。1.梯度法的基本原理

假定无约束极值问题式(7-40)中的目标函数f(X)有一阶连续偏导数，具有极小点X*。以X(k)表示极小点的第k次近似，为了求其第k+1次近似点X(k+1)，我们在X(k)点沿方向P(k)作射线X=X(k)+P(k)(0)02二月2023947.3无约束极值问题的解法7.3.1梯度法(最速下降法)现将f(X)在X(k)点处展成泰勒级数f(X)=f(X(k)+P(k))=f(X(k))+f(X(k))TP(k)+o()其中对于充分小的，只要f(X(k))TP(k)<0即可保证f(X(k)+P(k))<f(X(k))。这时若取X(k+1)=X(k)+P(k)就能使目标函数值得到改善。02二月2023957.3无约束极值问题的解法7.3.1梯度法(最速下降法)(7-41)现考查不同方向P(k)。假定P(k)的模一定(且不为0)，并设f(X(k))0(否则，X(k)是平稳点)，使式(7-41)成立的P(k)有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使f(X(k))TP(k)取最小值的P(k)。由线性代数学知道f(X(k))TP(k)=||f(X(k))||||P(k)||cos式中为向量f(X(k))与P(k)的夹角。当P(k)与f(X(k))反向时，=1800，cos=-1。这时式(7-41)成立，而且其左端取最小值。我们称方向P(k)=-f(X(k))02二月2023967.3无约束极值问题的解法7.3.1梯度法(最速下降法)(7-42)为负梯度方向，它是使函数值下降最快的方向(在X(k)的某一小范围内)。

为了得到下一个近似极小点，在选定了搜索方向之后，还要确定步长。当采用可接受点算法时，就是取某一进行试算，看是否满足不等式f(X(k)-P(k))<f(X(k))若上述不等式成立，就可以迭代下去。否则，缩小使满足不等式式(7-43)。由于采用负梯度方向，满足式(7-43)的总是存在的。02二月2023977.3无约束极值问题的解法7.3.1梯度法(最速下降法)(7-43)另一种方法是通过在负梯度方向的一维搜索，来确定使f(X)最小的k，这种梯度法就是所谓最速下降法。2.计算步骤

现将用梯度法解无约束极值问题的步骤简要总结如下：(1)给定初始近似点X(0)及精度>0，若||f(X(0))||2，则X(0)即为近似极小点。(2)若||f(X(0))||2>，求步长0

，并计算X(1)=X(0)-0f(X(0))02二月2023987.3无约束极值问题的解法7.3.1梯度法(最速下降法)求步长可用一维搜索法、微分法或计划处法。若求最佳步长，则应使用前两种方法。(3)一般地，设已迭代到点X(k)，若||f(X(0))||2，则X(k)即为所求的近似解；若||f(X(0))||2>，则求步长k，并确定下一个近似点X(k+1)=X(k)-kf(X(k))如此继续，直至达到要求的精度为止。

若f(X)具有二阶连续偏导数，在X(k)作f(X(k)-f(X(k)))的泰勒展开02二月2023997.3无约束极值问题的解法7.3.1梯度法(最速下降法)(7-44)f(X(k)-f(X(k)))f(X(k))-f(X(k))Tf(X(k))+0.5f(X(k))TH(X(k))f(X(k))则对求导并令其层数等于零，则得近似最佳步长

可见近似最佳步长不仅与梯度有关，而且与海赛矩阵H也有关系，计算起来比较麻烦。

确定步长k也可不用式(7-45)，而采用任一种一维搜索法(例如0.618法等)。

若将搜索方向P(k)的模规格化为1，在这种情况下02二月20231007.3无约束极值问题的解法7.3.1梯度法(最速下降法)(7-45)同时，式(7-45)变为

例6式用梯度法求f(X)=(x1-1