非线性最优化.pptx

非线性最优化 非线性最优化的基本概念非线性最优化的基本概念 一维搜索一维搜索 无约束极值问题的解法无约束极值问题的解法 最优性条件最优性条件 有约束极值问题的解法有约束极值问题的解法 二次规划二次规划 可行方向法可行方向法 制约函数法制约函数法 第一节 基本概念1.1 非线性问题的提出非线性问题的提出 例例1 某公司经营两种设备，第一种设备售价某公司经营两种设备，第一种设备售价30元，第二种设备售价元，第二种设备售价450元。根据统计，售出一件第元。根据统计，售出一件第一种设备所需要的营业时间平均是一种设备所需要的营业时间平均是0.5小时，第二种小时，第二种设备是设备是(2+0.25 x2 )小时小时,其中其中x2是第二种设备的售出是第二种设备的售出数量。已知该公司在这段时间内的总营业时间为数量。已知该公司在这段时间内的总营业时间为800小时，试决定使其营业额最大的营业计划小时，试决定使其营业额最大的营业计划.分析：设该公司经营第一种设备分析：设该公司经营第一种设备x1件件,第二种设备第二种设备 x2 件，其营业额为件，其营业额为f(X)，依题意列出问题的数学模型：，依题意列出问题的数学模型：maxf(X)=30 x1+450 x2 s.t.0.5 x1+(2+0.25 x2)x2 800 x1 0,0,x2 0 0 例例1 1的目标函数为自变量的线性函数，但的目标函数为自变量的线性函数，但其第一个约束条件却是自变量的二次函数，其第一个约束条件却是自变量的二次函数，因而它是非线性规划问题。因而它是非线性规划问题。若规划问题的若规划问题的目标函数目标函数及及约束函数约束函数中中至少至少有一个有一个是非线性函数是非线性函数,则称这种规划为非线性则称这种规划为非线性规划。规划。非线性规划的数学模型非线性规划的数学模型 非线性规划的数学模非线性规划的数学模型常表示成以下形式型常表示成以下形式 Minf(X)hi(X)=0 i=1,2,m gj(X)0 j=1,2,l非线性规划的数学模型非线性规划的数学模型可以写成以下形式可以写成以下形式 Minf(X)gj(X)0 j=1,2,ln注注1.min-f(X)=-maxf(x);n注注2.gj(X)0-gj(X)0;n注注3.hi(X)=0hi(X)0,-hi(X)0.1.2 极值问题极值问题 设设f(X)为定义在为定义在n维欧氏空间维欧氏空间 En 的某一区的某一区域域S上的上的n元实函数，其中元实函数，其中X=(x1,x2 xn)T T .局部极小点局部极小点(值值)：对于对于 X*S S，如果存在，如果存在某某0,0,使所有与使所有与X*的距离小于的距离小于的的X XS,S,均均满足不等式满足不等式f(X)f(f(X)f(X*),),则称则称X*为为f(X)在在S上的局部极小点上的局部极小点,f(f(X*)为局部极小值。为局部极小值。严格局部极小点严格局部极小点(值值)：对于所有对于所有XX*且且与与X*的距离小于的距离小于的的X XS,f(X)f(S,f(X)f(X*),),则称则称X*为为f(X)在在S上的严格局部极小点，上的严格局部极小点，f(f(X*)为为严格严格局部极小值。局部极小值。全局极小点全局极小点(值值)：对于所有的对于所有的X X S S，都，都有有f(X)f(f(X)f(X*),),则称则称X*为为f(X)在在S上的全局上的全局极小点，极小点，f(f(X*)为全局极小值。为全局极小值。严格全局极小点严格全局极小点(值值)：对于所有对于所有X XS且且XX*，都有都有f(X)f(f(X)f(X*),),则称则称X*为为f(X)在在R上的严格全局极小点，上的严格全局极小点，f(f(X*)为严格全局极为严格全局极小值。小值。将上述不等式反向，即可以得到相应的将上述不等式反向，即可以得到相应的极大点和极大值的定义。极大点和极大值的定义。极值点存在的必要条件和充分条件极值点存在的必要条件和充分条件 定理定理1(必要条件必要条件)设设S是是n维欧氏空间维欧氏空间E En n 上上的某一开集，的某一开集，f(X)在在S上有一阶连续偏导数，上有一阶连续偏导数，且在点且在点X*S取得局部极值，则必有取得局部极值，则必有 或或 其中其中 为函数为函数f(X)在点在点X*处的梯度处的梯度。定理定理2(充分条件充分条件)设设S是是n维欧氏空间维欧氏空间E En n 上上的某一开集，的某一开集，f(X)在在S上具有二阶连续偏导数，上具有二阶连续偏导数，X*S S，若，若f(X*)=0,且对任何非零向量且对任何非零向量ZEn有有 ZTH(X*)Z0 （1.4）则则X*为为f(X)的严格局部极小点的严格局部极小点.此处此处H(X*)为为f(X)在点在点X*处的海赛处的海赛(Hesse)矩阵矩阵.1.3 凸函数和凹函数凸函数和凹函数 凸函数凸函数:设设f(X)是定义在是定义在n维欧氏空间维欧氏空间E En n 中某个中某个凸集凸集S上的函数上的函数,若对任何实数若对任何实数a(0a 1)以及以及S中的中的任意两点任意两点X(1)和和X(2),恒有恒有 f(aX(1)+(1-a)X(2)af(X(1)+(1-a)f(X(2)(1.5)则称则称f(X)为定义在为定义在S上的凸函数上的凸函数.严格凸函数严格凸函数:若对每一个若对每一个a(0a1)以及以及S中的中的任意两点任意两点X(1)和和X(2),X(1)X(2)，恒有，恒有 f(aX(1)+(1-a)X(2)0,0,使得对任意使得对任意XXN N N N(X X X X*),),),),恒有恒有恒有恒有f(X)f(X)f(X)f(X)f(f(f(f(X X X X*).).).).令令令令y y y y是是是是S中中任一点，则对充分小的任一点，则对充分小的(0,1)(0,1)，有有 y+(1-y+(1-y+(1-y+(1-)X X X X*N N N N(X X X X*),),),),从而从而 f(f(y+(1-y+(1-y+(1-y+(1-)X X X X*)f(f(f(f(X X X X*)(1)(1)(1)(1)由于由于f f为凸函数为凸函数,有有 f(f(y)+(1-y)+(1-)f(X)f(X*)f(f(y+(1-y+(1-)X X*)(2)(2)由由(1)(1)、(2)(2)，得到，得到 f(y)f(y)f(f(X X*).).所以所以X X*为全局最小点为全局最小点.记记a:=a:=minf=f(minf=f(X X*),),则则S上的极小点的集合上的极小点的集合 S Sa a=X|XR,f(X)X|XR,f(X)aa.由性质由性质3 3知知,S Sa a是是凸凸集集.用反证法证明定理用反证法证明定理6：设设X X X X*S是一个局部极小点是一个局部极小点,则存在则存在0,0,使得对使得对任意任意XSXSN N N N(X X X X*),),),),恒有恒有恒有恒有 f(X)f(X)f(X)f(X)f(f(f(f(X X X X*).).).).假设假设假设假设X X X X*非全局最小非全局最小非全局最小非全局最小,则存在则存在则存在则存在X X X X S,S,使得使得f(f(X X X X*)f()f(X X X X).).由由S S的凸性的凸性,对任意对任意0,1,0,1,X X X X+(1-+(1-+(1-+(1-)X X X X*S,S,由由X X*X X X X,取取(0,1).(0,1).因为因为因为因为11时时,可使可使 X X X X+(1-+(1-+(1-+(1-)X X X X*SSN N N N(X X X X*).).).).又由又由f f凸凸,有有 f(f(X X X X+(1-+(1-+(1-+(1-)X X X X*)f(f(X X X X)+(1-)+(1-)+(1-)+(1-)f(X)f(X)f(X)f(X*)f(f(X X X X*)+(1-)+(1-)+(1-)+(1-)f(X)f(X)f(X)f(X*)=f(X =f(X =f(X =f(X*)此与此与此与此与X X X X*局部极小矛盾局部极小矛盾局部极小矛盾局部极小矛盾.所以所以所以所以X X X X*为全局最小点为全局最小点为全局最小点为全局最小点.定理定理7 设设f(X)是定义在凸集是定义在凸集S上的可微凸上的可微凸函数函数,若存在点若存在点X X*S,使得所有的使得所有的XS有有 f(Xf(X*)T T(X-X(X-X*)00则则X X*是是f(X)f(X)在在S S上的最小点上的最小点(全局极小点全局极小点).).证证 由定理由定理3,3,对任意对任意X XS有有 f(X)f(Xf(X*)+)+f(Xf(X*)T T(X-X(X-X*)f(Xf(X*),),证毕证毕.注注1:1:若若f(f(X X*)=0,=0,则则f(f(X X*)T T(X-XX-X*)0.0.注注2:2:最小点未必唯一最小点未必唯一,但凸集上严格凸函但凸集上严格凸函数的最小点唯一数的最小点唯一.注注3:3:对凹函数也有上述类似的结果对凹函数也有上述类似的结果.注注2:2:最小点未必唯一最小点未必唯一,但凸集上严格凸函但凸集上严格凸函数的最小点唯一数的最小点唯一.事实上事实上,设有两个最小点设有两个最小点X XY,Y,令令 Z=Z=X+(1-)Y,(0,1),X+(1-)Y,(0,1),则则 f(Z)f(Z)f(X)+(1-)f(Y)f(X)+(1-)f(Y)f(X)+f(X)+(1-)f(X)=f(X),(1-)f(X)=f(X),矛盾矛盾.例例4 求函数求函数f(x x1 1,x x2 2,x,x3 3)=x x1 1+2x x3 3+x2x3-x x1 12 2-x x2 22 2 x x3 32 2 的极值的极值.非线性规划的数学模型非线性规划的数学模型 Minf(X)(1.1)hi(X)=0 i=1,2,m (1.2)gj(X)0 j=1,2,l (1.3)满足约束条件满足约束条件(1.2)和和(1.3)的点称为的点称为可行点可行点(可行解可行解)，所有可行点的集合称为所有可行点的集合称为可行域可行域.若某个可行解使目标函数若某个可行解使目标函数(1.1)最小，就称最小，就称它为它为最优解最优解.1.4 凸规划凸规划n考虑非线性规划考虑非线性规划 MinxS f(X)S=X|gj(X)0,j=1,2,l假定其中假定其中f(X)为凸函数为凸函数,g gj j(X)(j=1,2,l)为凹为凹函数函数.这样的非线性规划称为这样的非线性规划称为凸规划凸规划.凸规划具有如下性质凸规划具有如下性质:1)凸规划的可行域为凸集凸规划的可行域为凸集;2)凸规划的局部最优解为全局最优解凸规划的局部最优解为全局最优解;3)凸规划的最优解集为凸集凸规划的最优解集为凸集;4)f(X)为严格凸函数时为严格凸函数时,凸规划的最优解唯一凸规划的最优解唯一.n例例5.5.求解非线性规划求解非线性规划迭代法基本思想迭代法基本思想:为了求函数为了求函数f(X)的最优解的最优解,首先给定一个首先给定一个初始估计初始估计X X(0)(0),然后按某种然后按某种算法算法找出比找出比X X(0)(0)更好更好的解的解X X(1)(1)(对极小化问题对极小化问题,f(f(X X(1)(1)f(X)f(Xf(X(0)(0),),再按此种规则找出再按此种规则找出比比X X(1)(1)更好的解更好的解X X(2)(2),.如此即可得到一个解的如此即可得到一个解的序列序列X X(k)(k).若这个解序列有极限若这个解序列有极限X X*，即即limlimkkXX(k)(k)-X-X*=0,=0,则称它则称它收敛收敛于于X X*.若这算法是有效的若这算法是有效的,那么它所产生的解的那么它所产生的解的序列将收敛于该问题的最优解序列将收敛于该问题的最优解.1.5 下降迭代算法下降迭代算法 若由某算法所产生的解的序列若由某算法所产生的解的序列X（k）使使目标函数值目标函数值f(X（k）)逐步减小逐步减小,就称这算法为就称这算法为下降算法下降算法.假定已迭代到点假定已迭代到点X X(k)(k),若从若从X X(k)(k)出发沿任出发沿任何方向移动都不能使目标函数下降何方向移动都不能使目标函数下降,则则X X(k)(k)是是局部极小点局部极小点,迭代停止迭代停止.若从若从X X(k)(k)出发至少存出发至少存在一个方向可使目标函数值有所下降在一个方向可使目标函数值有所下降,则可则可选能使目标函数值下降的某方向选能使目标函数值下降的某方向P P(k)(k)，沿这，沿这方向迈进适当的一步方向迈进适当的一步,得到下一个迭代点得到下一个迭代点X X(k+1)(k+1),并使并使 f(f(X X(k+1)(k+1)f()f(X X(k)(k).).这相当于在射线这相当于在射线X=X=X X(k)(k)+PP(k)(k)上选定新点上选定新点 X X(k+1)(k+1)=X X(k)(k)+k kP P(k)(k)X X(k+1)(k+1)=X X(k)(k)+k kP P(k)(k)其中其中P P(k)(k)称为称为搜索方向搜索方向;k k称为称为步长步长或或步长因子步长因子.下降迭代法的步骤下降迭代法的步骤:(1)(1).选定某一初始点选定某一初始点X X(0)(0),并令并令k:=0.k:=0.(2).(2).确定搜索方向确定搜索方向P P(k)(k).(3).从从X(k)出发，沿方向出发，沿方向P(k)求步长求步长k，以产生下一个迭代点以产生下一个迭代点X（k+1）.(4).检查得到的新点检查得到的新点X（k+1）是否为极小点是否为极小点或近似极小点或近似极小点.若是，则停止迭代若是，则停止迭代.否则，令否则，令k:=k+1，转回，转回(2)继续进行迭代继续进行迭代.在下降迭代步骤中在下降迭代步骤中,关键是关键是选取搜索方向选取搜索方向P P(k)(k)和和确定步长确定步长k.确定步长确定步长k k的常用方法：的常用方法：(1)令令k等于某一常数等于某一常数.(2)只要能使目标函数值下降只要能使目标函数值下降,可选取任意可选取任意k k.(3)沿射线沿射线X=X(k)+P(k)求目标函数求目标函数f(X)的极小的极小:k k:()=Minf(X X(k)(k)+PP(k)(k)称这一过程为称这一过程为(最优最优)一维搜索一维搜索或线搜索或线搜索,以此以此确定的步长为确定的步长为最佳步长最佳步长.一维搜索在搜索方向上所得最优点处的一维搜索在搜索方向上所得最优点处的梯度和该搜索方向正交梯度和该搜索方向正交.定理定理8 设目标函数设目标函数f(X)C(1)，X X(k+1)(k+1)按下按下述规则产生述规则产生k:Minf(X(k)+P(k)X(k+1)=X(k)+kP(k)则有则有 f(X(k+1)TP(k)=0.证证 设设()=f(X()=f(X(k)(k)+PP(k)(k),),则由则由 ()=()=f(Xf(X(k)(k)+PP(k)(k)T T P P(k)(k)=0=0 得得 =k k f(Xf(X(k)(k)+k kP P(k)(k)T T P P(k)(k)=f(Xf(X(k+1)(k+1)T TP P(k)(k)=0=0 n迭代计算法的收敛速度迭代计算法的收敛速度 设序列设序列x(k)收敛于收敛于x*,若存在与若存在与k无关的数无关的数,0+和和1,使得使得 X(k+1)-X*X(k)-X*，kk0则称则称x(k)收敛的阶为收敛的阶为,或或x(k)阶收敛阶收敛.当当=2时，称为二阶收敛时，称为二阶收敛,也称也称x(k)具有具有二阶敛速；当二阶敛速；当12时，称为超线性收敛；时，称为超线性收敛；当当=1,01时时,称为线性收敛或一阶收敛称为线性收敛或一阶收敛.n常用的收敛的准则有以下几种常用的收敛的准则有以下几种:(1).根据相继两次迭代的根据相继两次迭代的绝对误差绝对误差 X X(k+1)(k+1)-X X(k)(k)|f(|f(X X(k+1)(k+1)-f()-f(X X(k)(k)|)|(2).(2).根据相继两次迭代的根据相继两次迭代的相对误差相对误差 X X(k+1)(k+1)-X X(k)(k)/X X(k)(k)|f(|f(X X(k+1)(k+1)-f()-f(X X(k)(k)|/|f()|/|f(X X(k)(k)|)|这时要求分母不接近于零这时要求分母不接近于零.(3).根据目标函数梯度的模足够小根据目标函数梯度的模足够小 f(Xf(X（k k）)其中其中是事先给定的足够小的正数是事先给定的足够小的正数.n下单峰概念下单峰概念 设设f:RR,a,b为为R的区间的区间.若存在点若存在点x*a,b，使得，使得f(x)在在a,x*上严格单减，在上严格单减，在x*,b上严格单增，则称上严格单增，则称a,b是是f(x)的下单峰的下单峰区间，区间，f(x)是是a,b上的下单峰函数上的下单峰函数.n定理定理9 f(x)是是a,b上的下单峰函数上的下单峰函数,对任意对任意的的x1,x2a,b,x1x2,那么那么(1).若若f(x1)f(x2)，则则x1,b是是f(x)的下单峰区间的下单峰区间;(2).若若f(x1)f(x2)，则，则a,x2是是f(x)的下单峰区间的下单峰区间.第二节第二节 一维搜索一维搜索2.1 Fibonacci法(分数法)Fibonacci Fibonacci使用使用对称搜索对称搜索的方法的方法,逐步缩短逐步缩短所考察的区间所考察的区间,它能以尽量少的函数求值次数它能以尽量少的函数求值次数,达到预定的某一缩短率达到预定的某一缩短率.2.2 0.618法法(黄金分割法黄金分割法)若用不变的区间缩短率若用不变的区间缩短率0.618,代替分数代替分数法每法每次不同的缩短率次不同的缩短率,就得到了黄金分割法就得到了黄金分割法.0.618.0.618法是一种法是一种等速对称等速对称进行试探的方法进行试探的方法,每次的试每次的试点均取在区间长度的点均取在区间长度的0.6180.618倍和倍和0.380.382 2倍处倍处.设设y=f(t)是区间是区间a,b上的下单峰函数上的下单峰函数(如如下图下图),在此区间内它有唯一极小点在此区间内它有唯一极小点t.若在此区若在此区间内任取两点间内任取两点c和和d,cd,并计算函数值并计算函数值f(c)和和f(d),可能出现以下两种情形可能出现以下两种情形:1.f(c)f(d),这时极小点这时极小点t必在区间必在区间a,d内内.2.f(c)f(d),这时极小点这时极小点t必在区间必在区间c,b内内.第二节第二节 一维搜索一维搜索2.1.Fibonacci法(分数法)在区间在区间a,b内取两个不同的点内取两个不同的点,算出它们的函算出它们的函数值加以比较数值加以比较,就可以把就可以把搜索区间搜索区间a,b缩小成缩小成a,d或或c,b(缩小后仍包含极小点缩小后仍包含极小点).只要在只要在a,d或或c,b中再任取一点算出其函数值中再任取一点算出其函数值,并并与与f(c)或或f(d)加以比较加以比较,就可以继续缩小搜索区就可以继续缩小搜索区间间.只要缩小后的区间仍包含极小点只要缩小后的区间仍包含极小点t,则区间缩则区间缩得越小得越小,就越接近于函数的极小点就越接近于函数的极小点,但计算函数但计算函数值的次数也就越多值的次数也就越多.那么计算函数值那么计算函数值n次能把原来多大的区间次能把原来多大的区间缩小成一个单位区间呢缩小成一个单位区间呢?(1)用用Fn n表示计算表示计算n个函数值能缩短为单位区间个函数值能缩短为单位区间的最大原区间长度的最大原区间长度.则显然则显然F0 0=F1 1=1.(2)在区间在区间a,b内取两个不同的点内取两个不同的点c和和d,缩短缩短后区间后区间a,d和和c,b的长度之和必大于的长度之和必大于a,b的长度的长度.因此计算两次函数值一般无法把长度大于因此计算两次函数值一般无法把长度大于2个单位的区间缩成单位区间个单位的区间缩成单位区间.但是但是,对于长度对于长度为两个单位的区间为两个单位的区间,如下图如下图,取取为任意小的为任意小的正数正数,缩短后区间长度为缩短后区间长度为1+1+,接近于一个单接近于一个单位长度位长度.由此由此F2 2=2.根据同样的分析可得根据同样的分析可得F3 3=3 F4 4=5 F5 5=8,序列序列Fn n可写成一个可写成一个递推公式递推公式：Fn n=Fn-1n-1+Fn-2 n-2,n2.2.利用公式可依次算出利用公式可依次算出 各各Fn n的值的值,这些这些Fn n就是就是FibonacciFibonacci数数.由以上讨论可知由以上讨论可知,计算计算n n次函数值所能获得的最次函数值所能获得的最大缩短率为大缩短率为1/1/Fn n.若要计算若要计算n个函数值个函数值,把区间把区间a0,b0的长度缩的长度缩为原来长度的为原来长度的倍倍,即缩短后的区间长度为即缩短后的区间长度为bn-1-an-1(b0-a0),则只要则只要n n足够大满足下式即足够大满足下式即可可:Fn n 1/(6.30)(6.30)式中式中为一个正小数为一个正小数,称为区间缩短的称为区间缩短的相对精相对精度度.而对于区间的而对于区间的绝对精度绝对精度,即要求即要求 bn-1-an-1 相对精度和绝对精度的关系是相对精度和绝对精度的关系是:=(=(b0-a0)用用FibonacciFibonacci法缩短区间的步骤如下法缩短区间的步骤如下 1.1.确定试点的个数确定试点的个数n.n.根据缩短率根据缩短率,即可用式即可用式 (6.30)(6.30)算出算出Fn n,然后由递推公式确定最小的然后由递推公式确定最小的n.n.2.选取前两个试点的位置选取前两个试点的位置.由递推公式可知由递推公式可知,第一次缩短时的两个试点位第一次缩短时的两个试点位置是置是 t1=b0+(a0-b0)Fn-1n-1/Fn n t1，=a0+(b0-a0)Fn-1n-1/Fn n它们在区间内是对称的它们在区间内是对称的.3.计算函数计算函数值值f(t1)和和f(t1，),并比较它们的并比较它们的大小大小.若若f(t1)f(t1，),则取则取 a1=a0 b1=t1，t2，=t1 并令并令t2=b1+(a1-b1)Fn-2n-2/Fn-1n-1 否则否则,取取 a1=t1 b1=b0 t2=t1，并令并令t2，=a1+(b1-a1)Fn-2n-2/Fn-1n-1.4.计算计算f(t2)或或 f(t2，),如第三步那样一步步迭代如第三步那样一步步迭代.计算的一般公式为计算的一般公式为 tk=bk-1+(ak-1-bk-1)Fn-kn-k/Fn-k+1n-k+1 tk，=ak-1+(bk-1-ak-1)Fn-kn-k/Fn-k+1n-k+1 其中其中k=1,2,n-1.5.当进行至当进行至k=n-1时时,tn-1=tn-1，=1/2 (an-2+bn-2)无法比较函数值无法比较函数值f(tn-1)和和f(tn-1，)的大小以确定的大小以确定最后区间最后区间,为此为此,取取 tn-1=1/2 (an-2+bn-2)tn-1，=an-2+(1/2+)(bn-2-an-2)并取得最终区间并取得最终区间 an-2,tn-1，或或 tn-1,bn-2.由上述分析可知由上述分析可知,FibonacciFibonacci使用使用对称搜索对称搜索的的方法方法,逐步缩短所考察的区间逐步缩短所考察的区间,它能以尽量少的它能以尽量少的函数求值次数函数求值次数,达到预定的某一缩短率达到预定的某一缩短率.例例1 试用斐波那契法求函数试用斐波那契法求函数f(t)=t2-t+2的近似极的近似极小点和极小值小点和极小值,要求缩短后的区间不大于区间要求缩短后的区间不大于区间-1，3的的0.08倍倍.（其中（其中为任意小的数为任意小的数,在在tn-1和和tn-1，中以函数中以函数值较小者为近似极小点值较小者为近似极小点,相应的函数值为近似相应的函数值为近似极小值极小值.）2.2.0.618法法(黄金分割法黄金分割法)当用当用FibonacciFibonacci法以法以n n个试点来缩短某一个试点来缩短某一区间时区间时,区间长度的第一次缩短率为区间长度的第一次缩短率为Fn-1n-1/Fn n,其后各次分别为其后各次分别为 Fn-2n-2/Fn-1n-1,Fn-3n-3/Fn-2 n-2,F1 1/F2 2 把以上数列分为奇数项把以上数列分为奇数项F2k-12k-1/F2k2k和偶数和偶数项项F2k2k/F2k+12k+1,下面证明这两个数列收敛于同一个极限下面证明这两个数列收敛于同一个极限.证证.设当设当kk时时,F2k-12k-1/F2k2k,F2k2k/F2k+12k+1 由于由于 F2k-12k-1/F2k2k=F2k-12k-1/(F2k-12k-1+F2k-22k-2)=1/(1+F2k-22k-2/F2k-12k-1)故故limlimk k F2k-12k-1/F2k2k=1/(1+)=(6.36)(6.36)同理可证同理可证 =1/(1+)(6.37)(6.37)将将(6.36)(6.36)代入代入(6.37)(6.37)得得 =(1+)/(2+)即即2 2+-1=0-1=0 从而可得从而可得 =(=(5 51/21/2-1-1)/2)/2 若将若将(6.37)(6.37)代入代入(6.36)(6.36)式式,则得则得2 2+-1=0-1=0 故有故有=(=(5 51/21/2-1 1)/2=0.6180339887418948)/2=0.6180339887418948 若用不变的区间缩短率若用不变的区间缩短率0.618,代替代替FibonacciFibonacci法每法每次不同的缩短率次不同的缩短率,就得到了黄金分割法就得到了黄金分割法(0.618(0.618法法).).当用当用0.6180.618方法时方法时,计算计算n n个试点的函数值可以把个试点的函数值可以把原区间原区间 a0,b0 连续缩短连续缩短n-1n-1次次,因为每次缩短率均为因为每次缩短率均为,故最后的区间长度为故最后的区间长度为 (b0-a0)n-1n-1 故当已知缩短的相对精度为故当已知缩短的相对精度为时时,可以用下式计可以用下式计算试点个数算试点个数n:n:n-1n-1 当然当然,也可以不预先计算试点的数目也可以不预先计算试点的数目n,n,而在计算过而在计算过程中逐次加以判断程中逐次加以判断,看是否已满足了提出的精度要求看是否已满足了提出的精度要求.0.618 0.618法是一种法是一种等速对称等速对称进行试探的方法进行试探的方法,每次的每次的试点均取在区间长度的试点均取在区间长度的0.6180.618倍和倍和0.3280.328倍处倍处.第三节第三节 无约束极值问题的解法无约束极值问题的解法 无约束极值问题可表述为无约束极值问题可表述为 (MP)minf(X),X E En n (3.1)解上述问题常用迭代法解上述问题常用迭代法,迭代法大体分为两类迭代法大体分为两类:一类要用到函数值的一阶导数一类要用到函数值的一阶导数(或或)二阶导数二阶导数,由于由于用到了函数的解析性质用到了函数的解析性质,故称为故称为解析法解析法;另一类在迭代过程中仅用到函数值另一类在迭代过程中仅用到函数值,而不要求函数而不要求函数的解析性质的解析性质,这类方法称为这类方法称为直接法直接法.本节介绍几种常用的基本方法本节介绍几种常用的基本方法,其中前三种属解析其中前三种属解析法法,后面一种属直接法后面一种属直接法.3.1 梯度法梯度法(最速下降法最速下降法)无约束极值问题的解析法中无约束极值问题的解析法中,梯度法梯度法的特点的特点是迭代过程简单是迭代过程简单,使用方便使用方便,是某些方法的基础是某些方法的基础.一、一、梯度法的基本原理梯度法的基本原理:假定无约束极值问题假定无约束极值问题 minf(X)，X E En n 中中f(X)f(X)有一阶连续偏导数有一阶连续偏导数,具有极小点具有极小点X X*.以以X X(k)(k)表示极小点的第表示极小点的第k k次近似次近似,为了求其第为了求其第k+1k+1次近次近似点似点X X(k+1)(k+1),在在X X(k)(k)点沿方向点沿方向P P(k)(k)作作射线射线 X=XX=X(k)(k)+P P(k)(k)(00)将将f(X)f(X)在在X X(k)(k)点处展成泰勒级数点处展成泰勒级数 f(X)=f(Xf(X)=f(X(k)(k)+P P(k)(k)=f(X =f(X(k)(k)+)+f(Xf(X(k)(k)T T P P(k)(k)+o(+o()对于充分小的对于充分小的,只要只要 f(Xf(X(k)(k)T T P P(k)(k)0 (3.2)0 (3.2)即可保证即可保证 f(Xf(X(k)(k)+P P(k)(k)f(X)f(X(k)(k).).这时若取这时若取 X X(k+1)(k+1)=X X(k)(k)+P P(k)(k),就能使目标值下降就能使目标值下降.n下降方向的选取下降方向的选取 设设P(k)0,f(Xf(X(k)(k)00.由由 f(X(k)TP(k)=f(X(k)P(k)cos 式中式中为向量为向量f(X(k)与与P(k)的夹角的夹角,当当f(X(k)与与P(k)反向时反向时,=180。，cos=-1.这时式这时式(3.2)成立成立,而且其左端取最小值而且其左端取最小值,称方向称方向 P P(k)(k)=-=-f(Xf(X(k)(k)为为负梯度方向负梯度方向.它是使函数值它是使函数值(在在X X(k)(k)的附近的附近)下下降最快的方向降最快的方向.n 步长的选取步长的选取 若选取负梯度方向若选取负梯度方向,则存在则存在满足不等式满足不等式 f(X f(X(k)(k)-f(Xf(X(k)(k)f(X)0 及及k=1.(2)求搜索方向求搜索方向 P(k)=-f(Xf(X(k)(k).).(3)(3)若若f(Xf(X(k)(k)0 0 故必有故必有 ai=0=0，i=1,2,i=1,2,n,n从而从而P P(1)(1),P P(2)(2),P,P(n)(n)线性无关线性无关.正定二次函数正定二次函数极小化问题极小化问题 minf(X)=(1/2)XT TAX+BT TX+c c (3.4)式中式中A为为n nnn对称正定阵对称正定阵;X,BX,BEEn n;c;c为常数为常数.定理定理9 9 设向量设向量P P(i)(i),i=1,2,i=1,2,n-1,n-1,为为A A共轭共轭,则从任一点则从任一点X X(0)(0)出发出发,相继以相继以P P(0)(0),P P(1)(1),P,P(n-1)(n-1)为搜索方向的下述算法为搜索方向的下述算法:Min f(X(k)(k)+PP(k)(k)=f(X(k)(k)+k kP P(k)(k)X(k+1)(k+1)=X(k)(k)+k kP P(k)(k)经经n次一维搜索收敛于问题次一维搜索收敛于问题(3.4)的极小点的极小点X*.证证:由由(3.4),f(X)=AX+Bf(X)=AX+B 设相继各次搜索得到的近似解分别为设相继各次搜索得到的近似解分别为X X(1)(1),X X(2)(2),X,X(n)(n),则则 f(Xf(X(k)(k)=AX)=AX(k)(k)+B+B f(Xf(X(k+1)(k+1)=AX)=AX(k+1)(k+1)+B=A(+B=A(X(k)(k)+k kP P(k)(k)+B)+B =f(Xf(X(k)(k)+k kA AP P(k)(k)(3.5)假定假定f(Xf(X(k)(k)0,0,k=0,1,2,k=0,1,2,n-1,n-1,则则 f(Xf(X(n)(n)=)=f(Xf(X(n-1)(n-1)+n-1n-1A AP P(n-1)(n-1)=f(Xf(X(k+1)(k+1)+k+1k+1A AP P(k+1)(k+1)+k+2k+2A AP P(k+2)(k+2)+n-1n-1A AP P(n-1)(n-1)由于在进行一维搜索时由于在进行一维搜索时,为确定最佳步长为确定最佳步长k k,令令 df(Xdf(X(k+1)(k+1)/d)/d=df(Xdf(X(k)(k)+PP(k)(k)/d)/d =f(Xf(X(k+1)(k+1)T T P(k)(k)=0 (3.6)=0 (3.6)故对故对k=0,1,2,k=0,1,2,n-1,n-1有有(P P(k)(k)T Tf(Xf(X(n)(n)=)=(P P(k)(k)T Tf(Xf(X(k+1)(k+1)+k+1k+1(P P(k)(k)T TAPAP(k+1)(k+1)+n-1 n-1(P P(k)(k)T T A AP P(n-1)(n-1)=(P P(k)(k)T Tf(Xf(X(k+1)(k+1)=)=0 (3.7)0 (3.7)因为因为n+1n+1个个n n维向量线性相关维向量线性相关,由定理由定理8 8可知可知,f(Xf(X(n)(n)T Tf(Xf(X(n)(n)=)=f(Xf(X(n)(n)T Tk kP P(k)(k)=k kf(Xf(X(n)(n)T T P P(k)(k)=0=0从而必有从而必有 f(Xf(X(n)(n)=0.)=0.从而必有从而必有 f(Xf(X(n)(n)=0.)=0.由于由于f(X)f(X)为凸函数为凸函数,故故X X(n)(n)为为f(X)f(X)的极小点的极小点X X*.2.2.正定二次函数的正定二次函数的共轭梯度法共轭梯度法 对于问题对于问题(3.4)3.4)来说来说,由于由于A A为对称正定阵为对称正定阵,故故存在唯一极小点存在唯一极小点X X X X*,它满足方程组它满足方程组 f(X)=AX+B=0f(X)=AX+B=0f(X)=AX+B=0f(X)=AX+B=0且具有形式且具有形式 X X X X*=-A=-A=-A=-A-1-1B B B B 如果已知某共轭向量组如果已知某共轭向量组P P(0)(0),P P(1)(1),P,P(n-1)(n-1),由由定理定理9 9可知可知,问题问题(3.4)3.4)的极小点的极小点X X X X*可通过下列算法得到可通过下列算法得到:X(k+1)(k+1)=X(k)(k)+k kP P(k)(k),k=0,1,2,k=0,1,2,n-1 ,n-1 k k:Min f(X(k)(k)+PP(k)(k)(3.8)X(n)(n)=X*这种从任一点这种从任一点X(0)En出发出发,依次沿某组共轭方向进行依次沿某组共轭方向进行最优一维搜索最优一维搜索,求解无约束极值的方法求解无约束极值的方法,称为称为共轭方向法共轭方向法.n构造正定二次函数的构造正定二次函数的共轭梯度法共轭梯度法.任取初始近似点任取初始近似点任取初始近似点任取初始近似点X(0)(0),并取初始搜索方向为此并取初始搜索方向为此并取初始搜索方向为此并取初始搜索方向为此点的负梯度方向点的负梯度方向点的负梯度方向点的负梯度方向,即即即即 P P(0)(0)=-f(Xf(Xf(Xf(X(0)(0)沿射线沿射线沿射线沿射线X X X X(0)(0)+P P P P(0)(0)进行一维搜索进行一维搜索进行一维搜索进行一维搜索,得得得得 X(1)(1)=X(0)(0)+0 0P P(0)(0)0 0:Min f(X(0)(0)+PP(0)(0)一般地一般地一般地一般地,从点从点X(k)出发出发,沿方向沿方向P P(k)(k)进行最优一进行最优一维搜索维搜索,有有 f f f f(X(X(k+1)(k+1)T TP P(k)(k)=0=0（结合（结合3.53.5）.从而从而 k k=-=-=-=-f f f f(X(X(k)(k)T TP P(k)(k)/(P(P(k)(k)T TA A A AP P(k)(k)(3.9)(3.9)按按按按 P P P P(k+1)(k+1)=-=-=-=-f f f f(X(X(k+1)(k+1)+)+k k P P P P(k)(k)(3.10)(3.