《非线性最优化.pptx》由会员分享，可在线阅读，更多相关《非线性最优化.pptx（147页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一节第一节 基本概念基本概念1.1 非线性问题的提出 例1 某公司经营两种设备，第一种设备售价30元，第二种设备售价450元。根据统计，售出一件第一种设备所需要的营业时间平均是0.5小时，第二种设备是(2+0.25 x2 )小时,其中x2是第二种设备的售出数量。已知该公司在这段时间内的总营业时间为800小时，试决定使其营业额最大的营业计划.分析：设该公司经营第一种设备x1件,第二种设备 x2 件，其营业额为f(X)，依题意列出问题的数学模型：第1页/共147页 maxf(X)=30 x1+450 x2 s.t.0.5 x1+(2+0.25 x2)x2 800 x1 0,0,x2 0 0 例1
2、 1的目标函数为自变量的线性函数，但其第一个约束条件却是自变量的二次函数，因而它是非线性规划问题。若规划问题的目标函数及约束函数中至少有一个是非线性函数,则称这种规划为非线性规划。第2页/共147页非线性规划的数学模型 非线性规划的数学模型常表示成以下形式 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.第3页/共147页1.2 极值问题 设f(X)为定义在n
3、维欧氏空间 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*)为第4页/共147页严格局部极小值。全局极小点(值)：对于所有的X X S S，都有f(X)f(f(X)f(X*),),则称X*为f(X)在S上的全
4、局极小点，f(f(X*)为全局极小值。严格全局极小点(值)：对于所有X XS且XX*，都有f(X)f(f(X)f(X*),),则称X*为f(X)在R上的严格全局极小点，f(f(X*)为严格全局极小值。将上述不等式反向，即可以得到相应的极大点和极大值的定义。第5页/共147页极值点存在的必要条件和充分条件 定理1(必要条件)设S是n维欧氏空间E En n 上的某一开集，f(X)在S上有一阶连续偏导数，且在点X*S取得局部极值，则必有 或 其中 为函数f(X)在点X*处的梯度。第6页/共147页 定理2(充分条件)设S是n维欧氏空间E En n 上的某一开集，f(X)在S上具有二阶连续偏导数，X*
5、S S，若f(X*)=0,且对任何非零向量ZEn有 ZTH(X*)Z0 （1.4）则X*为f(X)的严格局部极小点.此处H(X*)为f(X)在点X*处的海赛(Hesse)矩阵.第7页/共147页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)
6、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)第12页/共147页由于f f为凸函数,有 f(f(y)+(1-y)+(1-y)+(1-y)+(1-)f(X)f(X)f(X
7、)f(X*)f(f(y+(1-y+(1-y+(1-y+(1-)X X X X*)(2)(2)由由(1)(1)(1)(1)、(2)(2)(2)(2)，得到，得到 f(y)f(y)f(y)f(y)f(f(f(f(X X X X*).).).).所以所以X X X X*为全局最小点为全局最小点.记a:=a:=minf=f(minf=f(X X X X*),),则S上的极小点的集合 S Sa a=X|XR,f(X)X|XR,f(X)aa.由性质3 3知,S Sa a是凸集.第13页/共147页 用反证法证明定理6：设X X X X*S是一个局部极小点,则存在0,0,使得对任意XSXSN N N N(X
8、 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
9、 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*为全局最小点为全局最小点.第14页/共147页 定理7 设f(X)是定义在凸集S上的可微凸函数,若存在点X X X X*S,使得所有的XS有 f(Xf(X*)T T(X-X(X-X*)00则X X X X*是f(X)f(X)在S
10、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:对凹函数也有上述类似的结果.第15页/共147页 注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)+(
11、1-)f(Y)f(X)+f(X)+(1-)f(X)=f(X),(1-)f(X)=f(X),矛盾.例4 求函数f(x x x x1 1 1 1,x x x x2 2 2 2,x,x,x,x3 3 3 3)=x x x x1 1 1 1+2x x x x3 3 3 3+x2x3-x x x x1 1 1 12 2 2 2-x x x x2 2 2 22 2 2 2 x x x x3 3 3 32 2 2 2 的极值.第16页/共147页 非线性规划的数学模型 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)
12、的点称为可行点(可行解)，所有可行点的集合称为可行域.若某个可行解使目标函数(1.1)最小，就称它为最优解.1.4 凸规划凸规划第17页/共147页考虑非线性规划 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)为严格凸函数时,凸规划的最优解唯一.第18页/共147页例5.5.求解非线性规划第19页/共147页迭代法基本思想:为了求函数f(X)的最优解,首先给定一个初
13、始估计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 下降迭代算法下降迭代算法第20页/共147页 若由某算法所产生的解的序列X（k）使目标函数值f(X（k）)逐步减小,就称这算法为下降算法.假定
14、已迭代到点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)第21页/共147页 X X(k+1)(k+1)=X X(k)
15、(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)继续进行迭代.第22页/共147页在下降迭代步骤中,关键是选取搜索方向P P(k)(k)和确定步长k.确定步长k k的常用方法：(1)令k等于某一常数.(2)只要能使目标函数值下
16、降,可选取任意k k.(3)沿射线X=X(k)+P(k)求目标函数f(X)的极小:k k:()=Minf(X X(k)(k)+PP(k)(k)称这一过程为(最优)一维搜索或线搜索,以此确定的步长为最佳步长.第23页/共147页 一维搜索在搜索方向上所得最优点处的梯度和该搜索方向正交.定理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
17、 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 第24页/共147页迭代计算法的收敛速度 设序列x(k)收敛于x*,若存在与k无关的数,0+和1,使得 X(k+1)-X*X(k)-X*，kk0则称x(k)收敛的阶为,或x(k)阶收敛.当=2时，称为二阶收敛,也称x(k)具有二阶敛速；当12时，称为超线性收敛；当=1,01时,称为线性收敛或一阶收敛.第25页/共147页n常用的收敛的准则有以下几种:(1).根据相继两次迭代的绝对误差 X X(k+1)(k+1)-
18、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)|)|这时要求分母不接近于零.第26页/共147页(3).根据目标函数梯度的模足够小 f(Xf(X（k k）)其中是事先给定的足够小的正数.第27页/共147页下单峰概念 设f:RR,a,b为R的区间.若存在点x*a,b，使得f(x)在a,x*上严格单减，在x*,b上严格单增，则称a,
19、b是f(x)的下单峰区间，f(x)是a,b上的下单峰函数.定理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)的下单峰区间.第28页/共147页第二节第二节 一维搜索一维搜索2.1 Fibonacci法(分数法)Fibonacci Fibonacci使用对称搜索的方法,逐步缩短所考察的区间,它能以尽量少的函数求值次数,达到预定的某一缩短率.2.2 0.618法(黄金分割法)若用不变的区间缩短率0.618,代替分数等速对称2 2倍处.第29页/共147
20、页 设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法(分数法)第30页/共147页 在区间a,b内取两个不同的点,算出它们的函数值加以比较,就可以把搜索区间a,b缩小成a,d或c,b(缩小后仍包含极小点).只要在a,d或c,b中再任取一点算出其函数值,并与f(c)或f(d)加以比较,就可以继续缩小搜索区间.只要缩小后
21、的区间仍包含极小点t,则区间缩得越小,就越接近于函数的极小点,但计算函数值的次数也就越多.第31页/共147页 那么计算函数值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.第32页/共147页 根据同样的分析可得F3 3=
22、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数.第33页/共147页 由以上讨论可知,计算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 相对精度和绝对精度
23、的关系是:=(=(b0-a0)第34页/共147页 用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它们在区间内是对称的.第35页/共147页 3.计算函数值f(t1)和f(t1，),并比较它们的大小.若f(t1)f(t1，),则取 a1=a0 b1=t1，t2，=t1 并令t2=b1+(
24、a1-b1)Fn-2n-2/Fn-1n-1 否则,取 a1=t1 b1=b0 t2=t1，并令t2，=a1+(b1-a1)Fn-2n-2/Fn-1n-1.第36页/共147页 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
25、=1/2 (an-2+bn-2)tn-1，=an-2+(1/2+)(bn-2-an-2)第37页/共147页 并取得最终区间 an-2,tn-1，或 tn-1,bn-2.由上述分析可知,FibonacciFibonacci使用对称搜索的方法,逐步缩短所考察的区间,它能以尽量少的函数求值次数,达到预定的某一缩短率.例1 试用斐波那契法求函数f(t)=t2-t+2的近似极小点和极小值,要求缩短后的区间不大于区间-1，3的0.08倍.（其中为任意小的数,在tn-1和tn-1，中以函数值较小者为近似极小点,相应的函数值为近似极小值.）第38页/共147页第39页/共147页第40页/共147页第41页
26、/共147页第42页/共147页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,下面证明这两个数列收敛于同一个极限.第43页/共147页 证.设当kk时,F2k-12k-1/F2k2k,F2k2k/F2k+12k+1 由于 F2k-12k-1/F2k2k=F2k-12k-1/(F2k-12k-1+
27、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 第44页/共147页 若用不变的区间缩短率0.618,代替FibonacciFibonacci
28、法每次不同的缩短率,就得到了黄金分割法(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法是一种等速对称第45页/共147页第三节 无约束极值问题的解法 无约束极值问题可表述为 (MP)minf(X),X E En n (3.1)解上述问题常用迭代法
29、,迭代法大体分为两类:一类要用到函数值的一阶导数(或)二阶导数,由于用到了函数的解析性质,故称为解析法;另一类在迭代过程中仅用到函数值,而不要求函数的解析性质,这类方法称为直接法.本节介绍几种常用的基本方法,其中前三种属解析法,后面一种属直接法.第46页/共147页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
30、)(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)点处展成泰勒级数第47页/共147页 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)
31、+P P(k)(k),就能使目标值下降.下降方向的选取 设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)成立,第48页/共147页而且其左端取最小值,称方向 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)=
32、-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)线性无关.第56页/共147页 正定二次函数极小化问题 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)为搜索方向的下述
33、算法: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*.第57页/共147页 证:由(3.4),f(X)=AX+Bf(X)=AX+Bf(X)=AX+Bf(X)=AX+B 设相继各次搜索得到的近似解分别为设相继各次搜索得到的近似解分别为X X(1)(1),X X(2)(2),X,X(n)(n),则则 f(Xf(Xf(Xf(X(k)(k)=AX)=AX)=AX)=AX(k)(k)+B+B+B+B f(Xf(Xf(Xf(X(k+1)(k+1)=AX)
34、=AX)=AX)=AX(k+1)(k+1)+B=A(+B=A(+B=A(+B=A(X(k)(k)+k kP P(k)(k)+B)+B)+B)+B =f(Xf(Xf(Xf(X(k)(k)+k kA A A AP P(k)(k)(3.5)假定f(Xf(Xf(Xf(X(k)(k)0,0,0,0,k=0,1,2,k=0,1,2,n-1,n-1,则 f(Xf(Xf(Xf(X(n)(n)=)=)=)=f(Xf(Xf(Xf(X(n-1)(n-1)+n-1n-1A A A AP P(n-1)(n-1)=f(Xf(Xf(Xf(X(k+1)(k+1)+k+1k+1A A A AP P(k+1)(k+1)+k+2k
35、+2A A A AP P(k+2)(k+2)+n-1n-1A A A AP P(n-1)(n-1)第58页/共147页由于在进行一维搜索时由于在进行一维搜索时,为确定最佳步长为确定最佳步长k k,令令 df(Xdf(Xdf(Xdf(X(k+1)(k+1)/d)/d)/d)/d=df(Xdf(Xdf(Xdf(X(k)(k)+PP(k)(k)/d)/d)/d)/d =f(Xf(Xf(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(Xf(Xf(X(n)(n)=)=)=)=(
36、P P(k)(k)T Tf(Xf(Xf(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 A A AP P(n-1)(n-1)=(P P(k)(k)T Tf(Xf(Xf(Xf(X(k+1)(k+1)=)=)=)=0 (3.7)0 (3.7)因为n+1n+1个n n维向量线性相关,由定理8 8可知,f(Xf(Xf(Xf(X(n)(n)T T T Tf(Xf(Xf(Xf(X(n)(n)=)=)=)=f(Xf(Xf(Xf(X(n)(n)T T T Tk k k kP P P P(k)(k)(k)(k)=k
37、k k kf(Xf(Xf(Xf(X(n)(n)T T T T P P P P(k)(k)(k)(k)=0=0=0=0从而必有从而必有 f(Xf(Xf(Xf(X(n)(n)=0.)=0.)=0.)=0.第59页/共147页从而必有从而必有 f(Xf(Xf(Xf(X(n)(n)=0.)=0.)=0.)=0.由于由于f(X)f(X)f(X)f(X)为凸函数为凸函数,故故X X X X(n)(n)为为f(X)f(X)f(X)f(X)的极小点的极小点X X X X*.第60页/共147页 2.2.正定二次函数的共轭梯度法 对于问题(3.4)3.4)来说,由于A A为对称正定阵,故存在唯一极小点X X X
38、 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出发,依次沿某组共轭
39、方向进行最优一维搜索,求解无约束极值的方法,称为共轭方向法.第61页/共147页构造正定二次函数的共轭梯度法.任取初始近似点任取初始近似点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+
40、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.10)来产生搜索方向.欲选择k k使P P P P(k+1)(k+1)和P P P P(k)(k)为A A共轭,第62页/共147页则应有则应有 0=(P0=(P0=(P0=(P(k+1)(k+1)T TA A
41、P P P P(k)(k)=-=-=-=-ffff(X(X(k+1)(k+1)T TA AP P P P(k)(k)+k k(P P P P(k)(k)T TA AP P P P(k)(k)从而对从而对 K=0,1,K=0,1,n-2,n-2,取 k k=ffff(X(X(k+1)(k+1)T TA AP P P P(k)(k)/(P/(P(k)(k)T TA A A AP P(k)(k)(3.11)(3.11)下面简化k k的表示式:记记g g g gk k k k=f(Xf(Xf(Xf(X(k)(k),),),),由(3.5)(3.5)知,AP AP(k)=(=(g g g gk+1k+1
42、k+1k+1-g-g-g-gk k k k)/)/)/)/k k,代入(3.11)(3.11)得 k k=g g g gk+1k+1k+1k+1T T T T(g g g gk+1k+1k+1k+1-g-g-g-gk k k k)/)/)/)/(P(P(k)(k)T T(g g g gk+1k+1k+1k+1-g-g-g-gk k k k)(3.12)(3.12)(3.12)(3.12)0=g0=g0=g0=gk+2k+2k+2k+2T T T T P P P P(k+1)(k+1)=-=-g g g gk+2k+2k+2k+2T T T Tg g g gk+1k+1k+1k+1+k kg g
43、 g gk+2k+2k+2k+2T T T TP P P P(k)(k)=-=-g g g gk+2k+2k+2k+2T T T Tg g g gk+1k+1k+1k+1即即 g g g gk+2k+2k+2k+2T T T Tg g g gk+1k+1k+1k+1=0,=0,=0,=0,K=0,1,K=0,1,n-2.(3.13),n-2.(3.13)第63页/共147页又已知 0=g0=g0=g0=g1 1 1 1T T T T P P P P(0)(0)=-=-g g g g1 1 1 1T T T Tg g g g0 0 0 0 g g g gk+1k+1k+1k+1T T T Tg
44、g g gk k k k=0,g=0,g=0,g=0,gk+1k+1k+1k+1T T T TP P P P(k)(k)(k)(k)=0,=0,=0,=0,K=0,1,K=0,1,n-1.(3.14),n-1.(3.14)将(3.14)(3.14)代入(3.12)(3.12)得k k=g g g gk+1k+1k+1k+1T T T Tg g g gk+1k+1k+1k+1-g-g-g-gk+1k+1k+1k+1T T T Tg g g gk k k k/(P(P(k)(k)T Tg g g gk+1k+1k+1k+1-(-(-(-(P P(k)(k)T Tg g g gk k k k =g
45、g g gk+1k+1k+1k+12 2/-(P P(k)(k)T Tg g g gk k k k =g g g gk+1k+1k+1k+12 2/g g g gk k k k2 2k-1k-1(P P(k-1)(k-1)T Tg g g gk k k k =g g g gk+1k+1k+1k+12 2/g g g gk k k k2 2 故故 k k=g g g gk+1k+1k+1k+12 2/g g g gk k k k2 2 (3.15)(3.15)综上所述,可得共轭梯度法的一组计算公式如下:第64页/共147页 X(k+1)(k+1)=X(k)(k)+k kP P(k)(k)(3.1
46、6)(3.16)k k=-g=-g=-g=-gk k k kT T T TP P(k)(k)/(P(P(k)(k)T TA A A AP P(k)(k)(3.17)(3.17)P P(k+1)(k+1)=-g g g gk+1k+1k+1k+1+k k P P(k)(k)(3.18)(3.18)k k=g g g gk+1k+1k+1k+12 2/g g g gk k k k2 2 (3.19)(3.19)共轭梯度法的计算步骤:(1)选取初始近似X(0)(0),给出允许误差 0.0.(2)(2)计算 g g g gk k k k=f f f f(X(X(k)(k),若g g g gk+1k+1
47、k+1k+1=0,=0,则stop,stop,得 X X*=X=X(k)(k).否则转下一步.(3)(3)按(3.16)(3.16)（3.19)3.19)计算X(k+1)(k+1)和P P(k+1)(k+1).(4)(4)若k=n,k=n,则stop,stop,得 X X*=X=X(k)(k).否则goto(2).goto(2).第65页/共147页附注:对于二次函数的情形,从理论上说,进行n n次迭代即可达到极小点.但是,在实际计算中,由于数据的舍入以及计算误差的积累,往往做不到这点此外,由于n n维问题的共轭方向最多只有n n个,在n n步以后继续如上进行是没有意义的.因此,在实际应用时,
48、如迭代到n n步还不收敛,就将X X(n)(n)作为新的初始近似,重新开始迭代.第66页/共147页第67页/共147页第68页/共147页第69页/共147页第70页/共147页第71页/共147页3.3 变尺度法 一 基本原理 假定无约束极值问题的目标函数f(X)C(2),X X(k)(k)为其极小点X*的某一近似.由点X X(k)(k)附近取f(X)的二阶泰勒多项式逼近 f(X)f(Xf(X(k)(k)+)+f(Xf(X(k)(k)T TXX +(1/2)X +(1/2)XT TH(H(X X(k)(k)X)X 则其梯度为 f(X)f(X)f(Xf(X(k)(k)+)+H(H(X X(k
49、)(k)X )X 若H(H(X X(k)(k)正定,则这个近似函数的极小点满足 f(Xf(X(k)(k)+)+H(H(X X(k)(k)X=0)X=0第72页/共147页从而 X=XX=X(k)(k)-H(H(X X(k)(k)-1-1f(Xf(X(k)(k)算法 X X(k+1)(k+1)=X=X(k)(k)-H(H(X X(k)(k)-1-1f(Xf(X(k)(k)称为NewtonNewton法.NewtonNewton法的计算步骤：1 1 给定初始点X X(0)(0),梯度允许误差0,k:=00,k:=0 2 2 若f(Xf(X(0)(0),则X X(0)(0)即为近似极小点,停止迭代.
50、否则,转下一步.3 3 取P P(k)(k)=-=-2 2f(Xf(X(k)(k)-1-1 f(Xf(X(k)(k),),令X(k+1):=:=X X(k)(k)+k kP(k),k:=k+1,k:=k+1,转(2).(2).第73页/共147页当X X(0)(0)靠近X X*时NewtonNewton法二次收敛，X X(0)(0)远离X X*时NewtonNewton法可能发散。算法 P P(k)(k)=-=-H(H(X X(k)(k)-1-1g gk k (3.25)(3.25)X X(k+1)(k+1)=X X(k)(k)+k k P(k)(k)(3.26)(3.26)k k:minf(