最优化方法

第2章最优化方法《计算方法》第7章最优化方法§1引言§2一维搜索§3非线性最小二乘法§4最速下降法§5共轭斜量法§6变尺度方法§7单纯形方法第2章最优化方法《计算方法》§1引言1.1一元函数的极值1.定义设函数f(x)在点x0的某个邻域内有定义,在该邻域内,若满足f(x)＞f(x0)(x≠x0),则称f(x)在点x0达到极小值,x0为f(x)的极小点;若满足f(x)＜f(x0)(x≠x0),则称f(x)在点x0达到极大值,x0为f(x)的极大点。第2章最优化方法《计算方法》如图7.1,f(x)在点x1达到极大值,在点x2达到极小值,x1、x2分别为f(x)的极大点和极小点。极大值和极小值统称为极值。图7.1第2章最优化方法《计算方法》2.极值的必要条件设函数f(x)在点x0可微,且在x0达到极值,则f′(x0)=0如图7.1,曲线f(x)在A点、B点的切线都平行于x轴,也即f′(x1)=0,f′(x2)=0。这里的x0称为函数f(x)的驻点。驻点不一定是极值点,例f(x)=x3,有f′(0)=0,但x=0不是f(x)=x3的极值点。第2章最优化方法《计算方法》3.极值的充分条件第一种充分条件设函数f(x)在点x0的某个邻域内具有导数且f′(x0)=0,(1)若当x＜x0时,f′(x)＞0,当x＞x0时,f′(x)＜0,则函数f(x)在点x0处达到极大值;(2)若当x＜x0时,f′(x)＜0,当x＞x0时,f′(x)＞0,则函数f(x)在点x0处达到极小值;(3)当x取x0的左、右边附近的值时,f′(x)恒为正(或恒为负),则函数f(x)在点x0处无极值。第2章最优化方法《计算方法》第二种充分条件设函数f(x)在点x0处具有二阶导数且f′（x0)=0,f″(x0)≠0,则(1)当f″(x0)＜0时,函数f(x)在点x0处达到极大值;(2)当f″(x0)＞0时,函数f(x)在点x0处达到极小值。第2章最优化方法《计算方法》1.2二元函数的极值多元函数的极值不能完全从一元函数的情形反映出来,但能从二元函数中得到较好的反映。为此,我们给出二元函数的极值。读者可推广到一般的多元函数上去。1.定义设二元函数z=f(x,y)在点p0(x0,y0)的某个邻域内有定义,在该邻域内若满足f(x,y)＞f(x0,y0)(p(x,y)≠p0(x0,y0)),则称函数f(x,y)在点p0达到极小值,p0为f(x,y)的极小点;若满足f(x,y)＜f(x0,y0)第2章最优化方法《计算方法》(p(x,y)≠p0(x0,y0)),则称函数f(x,y)在点p0达到极大值,p0为f(x,y)的极大点。如图7.2,f(x,y)在p1(x1,y1)达到极大值,在p2(x2,y2)点达到极小值,p1、p2分别为f(x,y)的极大点和极小点。第2章最优化方法《计算方法》图7.2第2章最优化方法《计算方法》2.极值的必要条件设二元函数f(x,y)在p0(x0,y0)点的一阶偏导数存在,且在该点达到极值,则有f′x(x0,y0)=0f′y(x0,y0)=0满足(7―1)式的点p0(x0,y0)称为函数f(x,y)的驻点。为了求函数的极值点,应该先求函数的驻点,但驻点不一定是极值点。例如,z=xy的驻点为p(0,0),但它不是极值点。(7―1)第2章最优化方法《计算方法》3.极值的充分条件设函数f(x,y)在点p0(x0,y0)的某个邻域内有连续的直到二阶偏导数,且f′x(x0,y0)=0f′y(x0,y0)=02000000[(,)](,)(,)0xyxxyyfxyfxyfxy(7―2)第2章最优化方法《计算方法》则函数f(x,y)在点p0(x0,y0)达到极值。若f″xx(x0,y0)＞0,那么f(x,y)在点p0达到极小值,若f″xx(x,y)＜0,则函数f(x,y)在点p0达到极大值。第2章最优化方法《计算方法》1.3目标函数的最速上升方向和最速下降方向以二元函数为例,讨论f(x)的最速上升方向和最速下降方向。设f(x)为定义在二维空间R2上的函数(0)11(0)(0)22,xxxxxx第2章最优化方法《计算方法》将f(x)在x(0)点附近展成泰勒级数,取到二次项为(0)(0)(0)12122(0)2(0)211221122(0)2222()()()()1()()[()2()()]fxfxfxfxxxxxfxfxxxxxxxfxxx第2章最优化方法《计算方法》这里Δx1=x1-x(0)1Δx2=x2-x(0)2若用向量和矩阵记号,上式可以简写为(0)01()(2TTfxfxgxxAx(7―3)第2章最优化方法《计算方法》其中(0)110(0)222(0)(0)21122(0)2(0)2212(),()()()()()fxxxgxxfxxfxfxxxxAfxfxxxx第2章最优化方法《计算方法》g0为目标函数f(x)在点x(0)处的斜量(或称为梯度),常记为g0=f(x(0))(或gradf(x(0)))A为对称矩阵。我们知道,过点x(0)引向量p0,f(x)沿这个方向的变化率就是f(x)在该点沿此方向的方向导数,其值为(0)(0)1201212()()coscoscoscosTfxfxghxxh第2章最优化方法《计算方法》见图7.3。因为所以,h为单位向量。若用θ表示gT0和h正向之间的夹角,则gT0h=‖g0‖‖h‖cosθ=‖g0‖cosθ可知,当θ=0时,gT0h=‖g0‖为最大值,h的方向与g0一致;当θ=π时,gT0h=-‖g0‖为最小值,h的方向与g0相反。2212coscos1第2章最优化方法《计算方法》图7.3第2章最优化方法《计算方法》1.4求目标函数极值的迭代法数值解法中最为常见的是迭代法。它的基本思想为:首先给出目标函数f(x)极小点的初始点x(0),然后按一定的规则构造一系列点列x(k)(k=0,1,2,…),希望点列｛x(k)｝的极限x就是f(x)的一个极小点。下面讨论点列｛x(k)｝的产生。设｛x(k)｝为已知,要求x(k+1)。因为x(k+1)与x(k)之差是一个从x(k)出发指向x(k+1)的向量,而向量总是由方向和长度所确定,即总可以写成第2章最优化方法《计算方法》x(k+1)-x(k)=λkpk(7―4a)或x(k+1)=x(k)+λkpk(7―4b)选取pk与λk的方法有多种多样,但选择的原则应该满足我们的需要。第一,点列｛x(k)｝的每一项x(k)所对应的函数值f(x(k))必须逐次减小,即f(x(0))≥f(x(1))≥…≥f(x(k))≥…第2章最优化方法《计算方法》综合前面的讨论,最优化算法中的迭代法大致可分成下列步骤进行:(1)选择初始点x(0);(2)按某种规则产生方向pk,使得目标函数f(x)从x(k)出发,沿pk方向按下降算法找到x(k+1)(x(k+1)=x(k)+λkpk);(3)确定λ=λk,使得f(x(k)+λkpk)＜f(x(k)),也即沿射线x(k)+λpk求g(λ)=f(x(k)+λpk)(7―5)的极小值,也称为一维搜索第2章最优化方法《计算方法》(4)检验x(k+1)是否满足所给精度的最优解(例,f(x(k+1))-f(x(k))＜ε,ε为预给的精度),若已达到,则迭代过程终止,x≈x(k+1)f(x)≈f(x(k+1))否则再进行下一步迭代。第2章最优化方法《计算方法》§2一维搜索上面已经提到,在无约束极值的算法中,为了求点列｛x(k)｝,只要沿逐次确定的一系列射线x(k)+λpk求极小点。当方向pk确定以后,x(k)为已知,则f(x(k)+λpk)为以λ为单个自变量的函数,即g(λ)=f(x(k)+λpk)第2章最优化方法《计算方法》这样,求f(x(k)+λpk)的极小值实际上就是求一元函数g(λ)的极小值。为了方便,我们仍然讨论一元函数f(x)的极小值问题,并假设f(x)在局部范围内的极小值存在且唯一。由一元函数极值存在的必要条件,我们需要求f′(x)=0的解,也就是求解该方程。第2章最优化方法《计算方法》2.1牛顿法第二章第四节中介绍,求解非线性方程φ(x)=0的牛顿迭代公式为1(),0,1,2,()kkkkxxxkx为求解方程f′(x)=0,则迭代公式应改为1(),0,1,2,()kkkkfxxxkfx(7―6)是求一维无约束极值的牛顿迭代公式。第2章最优化方法《计算方法》2.2二分法设函数f(x)在某区间上连续可导,若x为f(x)的极小点,则f′(x)=0,且当x＜x时,f′(x)＜0,即函数单调减小;而当x＞x时,f′(x)＞0,即函数单调增加。如果能找到一个区间［a,b］,且有f′(a)＜0,f′(b)＞0,则在a,b之间必有f(x)的极小点x。下面介绍二分法。第2章最优化方法《计算方法》区间［a,b］为已知的二分法的计算步骤如下:①输入有根区间的端点a、b及ε。②(a+b)/2x。③若f′(x)=0,则停止计算,x=x。④若f′(x)＞0,则xb,转向⑤;否则xa,转向⑤。⑤若b-a＜ε,则x=x,结束;否则转向②。其计算框图如图7.5。第2章最优化方法《计算方法》图7.4第2章最优化方法《计算方法》图7.5第2章最优化方法《计算方法》2.3黄金分割法(0.618法)牛顿法和二分法都要计算函数的导数。这往往会给计算带来麻烦。黄金分割法就克服了这种计算中的不足,仅用函数值本身的方法解决。此方法曾作为优选法用于生产和科学实验,收到了良好的效果。第2章最优化方法《计算方法》由于不须求导数,函数在尖点上达到极值也可以,见图7.6。设x(x)的极小点,则在极小点x的左边f(x)单调减小,也即若x1＜x2≤x,则f(x1)＞f(x2);在极小点x的右边f(x)单调增加,也即若x≤x1＜x2,则f(x1)＜f(x2)。为了求出函数f(x)的极小点x,就要在［a,b］内选取一些点的函数值进行比较。当然,总想寻找最少点的函数值进行比较,尽快地接近x。第2章最优化方法《计算方法》图7.6图7.7第2章最优化方法《计算方法》如图7.7,在［a,b］内取两个对称的点x1和x′1,若f(x1)＜f(x′1)则极小点在［a,x′1］内,否则在［x1,b］内,记新的极小点存在的区间为［a1,b1］,如图7.8,这样原极小点存在的区间被缩短了一次;在区间［a1,b1］内再取得两个对称点x2和x′2,如图7.9,通过比较f(x2)和f(x′2)的值,又可确定极小点存在的新区间［a2,b2］;如上不断缩短区间,最终总可求出满足精度要求的近似极小点。第2章最优化方法《计算方法》图7.8第2章最优化方法《计算方法》图7.9图7.10第2章最优化方法《计算方法》我们的问题是如何选取xi和x′i(i=1,2,…),使每次区间的长度按一定比例缩短。现令区间［a,b］的长度为1,设区间［a,x′1］的长度为α,如图7.10,要使每次区间长度均按一定比例缩短,则应有11(7―7)210152(7―8)解得第2章最优化方法《计算方法》取正值510.61803398874189482一般取α=0.618(7―9)由上述讨论,黄金分割法用k个试点可以把原来的区间［a,b］连续缩短k-1次,而每次的缩短率为α(α=0.618),最后区间长度就缩短为111()kkkbaaba(7―10)第2章最优化方法《计算方法》若预先给定精度ε,则可取满足不等式αn-1＜ε(7―11)的最小n作为所需要试点的个数。具体计算步骤为:在n确定以后,可分下列五步进行。①在［a,b］内取两个试点a1和b1,如图7.11所示。图7.11第2章最优化方法《计算方法》2）计算函数值(a1)和f(b1),并令③比较f1和f2,