运筹：第二章.pptx

一、无约束最优化问题的最优性条件一、无约束最优化问题的最优性条件 无约束优化问题 min f(x)x Rn 对于单元函数(x)，在微积分解有如下最优性条件。若x*为(x)的局部极小点，则(x*)=0 若(x*)=0，(x*)0，则x*为(x)的严格局部极小点 若 x*为(x)的 局 部 极 小 点，则(x*)=0，(x*)0第二章第二章:无约束最优化方法无约束最优化方法 同理，得到多元的函数f(x)最优性的必要和充分条件 定定理理2.1.1（一一阶阶必必要要条条件件）：若x*为f(x)的局部极小点，且在x*的某邻域内f(x)具有一阶连续偏导数，则g*=f(x*)=0（f(x*)为函数f(x)在x*处的梯度）第二章第二章:无约束最优化方法无约束最优化方法 证明：证明：假设x*为f(x)的局部极小点，g*0，则存在方向p Rn，使pTg*0，存在1（0，），使得 f(x+p)=f(x*)+pTg(x*+p)由于g在x*的某邻域内连续，故存在0，使得对于任意0,，有 pTg(x+p)0 f(x+p)0,则x*为f(x)的严格局部极小点，H(x*)为f(x)在点x*处的海赛（Hesse）矩阵。第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法 对于任意Z0(即Z的元素不全为零)，若ZTHZ0，则ZTHZ是正定的；若ZTHZ0，则ZTHZ是半正定的；若ZTHZ0，而另一些Z0，ZTHZ0，则其为不定的。由霍尔维茨定理可知：由霍尔维茨定理可知：ZTHZ为正定的充要条件是H的各阶主子式都为正；ZTHZ为负定的充要条件是H的奇数阶主子式为负，偶数阶主子式为正。第二章第二章:无约束最优化方法无约束最优化方法二、凸函数二、凸函数 凸函数以及凸函数的极值性质，是研究非线形规划问题所不可缺少的内容。1、凸集和凸函数 (1)凸集：凸集：设R为n维空间上的一个点集,x1,x2R,若x1和x2连线上的一切点x=x1+(1-)x2R，则称R为凸集。（01）第二章第二章:无约束最优化方法无约束最优化方法(2)(2)凸函数凸函数：设f(x)为定义在n维欧氏空间En中某个凸集R上的函数，若对任何实数(01)以及R中的任意两点x1和x2，恒有 fx1+(1-)x2f(x1)+(1-)f(x2)则称f(x)为定义在R上的凸函数。若对每一个(01)和x1x2R,恒有 fx1+(1-)x20）若f(xk+1)f(xk)成立，则kf(xk)T pk0 即f(xk)T pk0 (1)取初始点x0，k=0 (2)计算gk=g(xk)=f(xk),(3)若|gk|,则x*=xk，停止；否则，令pk=-gk,由一维搜索确定合适的步长k第二章第二章:无约束最优化方法无约束最优化方法 (4)令xk+1=xk+kpk,k=k+1,转(2)例1、求min f(x)=(1/2)x12+(9/2)x22,设初始点为(9,1)T解：g(x)=(x1,9x2)T ;第二章第二章:无约束最优化方法无约束最优化方法 显然G(x)为正定的，有唯一的极小点x*存在 g(x0)=(x0,9x0)T=(9,9)T；g(x0)=(92+92)1/2=10.726 ；p0=-g0=-(9,9)T x1=x0+0p0=(9,1)T-0(9,9)T=(9-90,1-90)T 第二章第二章:无约束最优化方法无约束最优化方法 0=0.2 x1=x0+0p0=(9-9*0.2,1-9*0.2)T =(7.2,-0.8)T g(x1)=(x1,9x1)T=(7.2,-7.2)T；g(x1)=(7.22+7.22)1/2=10.16 5；p1=-g1=-(7.2,-7.2)T x2=x1+1p1=(7.2,-0.8)T-1(7.2,-7.2)T =(7.2-7.21,-0.8+7.21)T 第二章第二章:无约束最优化方法无约束最优化方法 1=0.2 x2=x1+1p1=(0.8*7.2,0.64)T=0.82(9,(-1)2)T g(x2)=(x2,9x2)T=0.82(9,-9*(-1)2)T；g(x2)=(x22+(9x2)2)1/2；第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法 若f(x)具有二阶连续偏导数，在xK做 f(xK+f(xk)T的泰勒展开f(xk+k f(xk)T)f(xk)+k f(xk)T f(xk)+0.5 k2 f(xk)T H(xk)f(xk)（k0）对求导并令其等于0，则得近似最佳步长第二章第二章:无约束最优化方法无约束最优化方法 由此可见，步长不仅与梯度有关，而且与H(XK)有关，计算越来越比较麻烦，确定步长k，可用任一种一维搜索方法。有时，将搜索方向的模规格化为1，即则例2、求 min f(x)=(x1-1)2+(x2-1)2,设初始点为(0，0)T第二章第二章:无约束最优化方法无约束最优化方法 解：第二章第二章:无约束最优化方法无约束最优化方法 解：第二章第二章:无约束最优化方法无约束最优化方法 解：2、收敛性(1)整体收敛性 定理:设f(x)具有一阶连续偏导数,给定x0Rn,假定水平集L=xRn|f(x)f(x0)有界，令xk为由最速下降法产生的点列,则当k时,gk=f(xk)0或者对于某个k0,使 gk0=f(xk0)=0。证明：假设对任意k,gk0，因为f(x)单调下降且水平集L有界，故lim f(xk)存在，所以有fk-fk+10。用反证法。假设gk0不成立，则存在 0及无穷多个k，使gk 对于这样的K，有第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法于是泰勒公式 由于g(x)连续且L有界，所以g(x)在L上一致连续。故存在0，使当0|Pk|时，|g(K)-gK|1/2对所有K成立，对上式取=/|Pk|，第二章第二章:无约束最优化方法无约束最优化方法则有，与假设矛盾，故gK0(2)、用于二次函数时的收敛速度、用于二次函数时的收敛速度 最速下降法仅是线性收敛的，并且有时是很慢的线性收敛。定理：设f(x)=(1/2)XTGX+BTX+C，其中G是正定矩阵，用1，n表示G的最小与最大特征值，则由最速下降法产生的点列xk满足 第二章第二章:无约束最优化方法无约束最优化方法 当G的特征值比较分散，即n1，则1时，收敛速度很慢，接近于线性收敛；由以上定理可知，对于二次目标函数，最速下降法至少是线性收敛的，其收敛比第二章第二章:无约束最优化方法无约束最优化方法对其进一步分析 当G的特征值比较集中，即n 1，0时，收敛速度接近于超线性收敛。所谓最速下降方向pk=-gk仅反映f(x)在xk点的局部性质，对局部来说是最速下降方向，对整体来说不一定是最速下降方向。由gk+1T pk=0可知，在相继两次迭代中，搜索方向是相互正交的，其逼近极小点的路线是锯齿形的，并且越靠近极小点步长越小，即越走越慢。所以最速下降法有很好的整体收敛性，但收敛速度很慢，它是一个基本算法，不是一个有效的算法。第二章第二章:无约束最优化方法无约束最优化方法 3、牛顿法、牛顿法 最速下降法的本质是用线性函数近似目标函数，故收敛速度很慢，要想得到快速算法，需要考虑对目标函数的高阶逼近。牛顿法就是通过二次模型近似目标函数得到的。设xk为f(x)的极小点x*的一个近似，将f(x)在xk附近进行泰勒展开，f(x)=f(xk)+gkT(x-xk)+(1/2)(x-xk)TG(xk)(x-xk)若 G(xk)为正定，则f(x)有唯一极小点，将它取为x*的下一次近似xk+1，第二章第二章:无约束最优化方法无约束最优化方法 由一阶必要条件可知，xk+1应满足 f(x)=0，即 gkT+G(xk)(xk+1-xk)=0 令xk+1=xk+pk，则gkT+G(xk)pk=0 pk=-gkT/G(xk)xk+1=xk-gkT/G(xk)称xk+1=xk-gkT/G(xk)或pk=-gkT/G(xk)为牛顿迭代公式。由此可得牛顿算法如下：给定控制误差0第二章第二章:无约束最优化方法无约束最优化方法 (1)取初始点x0，令k=0 (2)计算g(xk)=f(xk)(3)若g(xk)，则x*=xk，停止；否则，计算G(xk)，并由pk=-gkT/G(xk)求出pk (4)令xk+1=xk+pk，k=k+1，转(2)第二章第二章:无约束最优化方法无约束最优化方法例2、用牛顿法求解min f(x)=(x1-1)2+(x2-1)2,设初始点为(0，0)T第二章第二章:无约束最优化方法无约束最优化方法 解：收敛性 对于正定二次函数，只需要一次迭代就可得到其极小点。对于一般函数，牛顿法只要收敛，就有较快的收敛速度。第二章第二章:无约束最优化方法无约束最优化方法 解：例3、用牛顿法求解min f(x)=x14+(x2+1)2,设初始点为(0，0)T定理：f(x)是某一开域内的三阶连续可微函数，且它在该开域内有极小点x*，设G*=G(x*)正定，则当x0与x*充分接近时，对一切k，牛顿法有定义，且当xk为无穷点列时，xk二阶收敛于x*。即hK0且|h K+1|=0(|hK|)2其中hK=xK-x*第二章第二章:无约束最优化方法无约束最优化方法证明：g(XK+h)=g(xK)+G(xK)h+0(|h|2)h=-hK,xK+h=x*g*=g(xK)-G(xK).hK+0(|hK|2)由于G*正定，且G（X）连续，所以存在的一个邻域N(x*)=x|x-x*|，第二章第二章:无约束最优化方法无约束最优化方法 使x N(x*)，G（X）正定且G（x）-1有上界，于是，若xK N(x*),对上式两边乘以Gk-1,在由h K+1的定义，有0=-PK-hK+0(|hK|2)=-h K+1+0(|hK|2)因此，由0(.)的定义，存在常数使得|h K+1|hK|成立，若取充分小，使之满足 0 (1)给定初始点x0及初始下降方向p0，令k=0 (2)作精确一维搜索，求步长k，使 f(xk+kpk)=min f(xk+pk）（0）第二章第二章:无约束最优化方法无约束最优化方法 (3)令xk+1=xk+kpk (4)若gk+1,则x*=xk+1，停止；否则，转(5)(5)取共轭方向pk+1，使得 pk+1TGpi=0，i=1,2,k (6)令k=k+1，转(2)它仅是一个概念性算法，不同的选择pk方法会产生不同的共轭方向法。(3)、共轭梯度法 共轭梯度法的基本思想是在共轭方向法和最速下降法之间建立某种联系，以求得到一个既有效又有较好收敛性的算法。第二章第二章:无约束最优化方法无约束最优化方法 对于正定二次函数 f(x)=(1/2)XTGX+BTX+C f(x)=GX+B f(xk+1)-f(xk)=G(xk+1-xk)xk+1=xk+kpk f(xk+1)-f(xk)=G(kpk)任取初始近似点x0，并取初始搜索方向为此点的负梯度方向p0=-f(x0)，沿射线x0+p0进行一维搜索，得 第二章第二章:无约束最优化方法无约束最优化方法 算出f(x1)，由f(x1)Tp0=-f(x1)T f(x0)=0 从而f(x1)与f(x0)正交，f(x1)与f(x0)构成一正交系。我们可以在由它们生成的二维子空间中寻求p1，为此，可令 p1=-f(x1)+0f(x0)(0为待定系数)欲使p1与p0关于G共轭，必须 -f(x1)+0f(x0)T f(x1)-f(x0)=0 0=-f(x1)T f(x1)/f(x0)T f(x0)令0=-0，则 第二章第二章:无约束最优化方法无约束最优化方法 0=f(x1)T f(x1)/f(x0)T f(x0)p1=-f(x1)-0p0 同理，以p1为搜索方向进行最优一维搜索，可得 第二章第二章:无约束最优化方法无约束最优化方法 则 p2=-f(x2)1p1 可得一般公式如下：对于正定二次函数来说，f(x)=GX+B f(xk+1)=f(xk)+kGpk由于进行了一维搜索，故有f(xk+1)T pk=0 k=-f(xk)T pk/pkTGpk则可得共轭梯度法的一组计算公式如下：第二章第二章:无约束最优化方法无约束最优化方法 此法称FR法。(F-Fletcher 弗莱彻,R-Reeves 瑞夫斯)第二章第二章:无约束最优化方法无约束最优化方法 如迭代步数kn已达到精度要求，则以xk作为要求的近似；否则可将前n步作为一个循环，同时以所有的xn作为新的初始点，重新开始，进行循环，直到满足要求的精度。得二次函数共轭梯度法的计算步骤如下：选择初始x0，给出允许误差 0，（1）k=0，xk=x0，计算f(xk)和G（2）令pk=-f(xk)（3）第二章第二章:无约束最优化方法无约束最优化方法 计算f(xk+1)(4)若f(xk+1)，则x*=xk+1，停止；否则，转下一步(5)若k n，则 第二章第二章:无约束最优化方法无约束最优化方法k=k+1，转(3)；否则，x0=xk，k=0，转(1)。例：试用共轭梯度法求下列二次函数的极小点 f(x)=(3/2)x12+(1/2)x22-x1x2-2x1,初始点为(-2,4)T第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法(4)非二次函数的共轭梯度法非二次函数的共轭梯度法 可将共轭梯度法推广到求解一般无约束极值问题。设f(x)为某一严格凸函数，具有二阶连续偏导数,其唯一极小点为x*。现任取初始近似x0，计算f(x0)，选取p0=-f(x0)为初始搜索方向。作射线x0+p0(0)并将f(x)=f(x0+p0)于x0附近作泰勒展开 f(x0+p0)f(x0)+f(x0)T p0+1/22p0TH(x0)p0 上式为的二次函数，因p0TH(x0)p0 0，故使该二次函数沿p0方向取极小值的为 第二章第二章:无约束最优化方法无约束最优化方法 它近似满足min f(x0+p0)令x1=x0+0p0，则x1近似满足f(x1)T p0=0 现构造向量 p1=-f(x1)+0p0，使 p1TH0p0=0则第二章第二章:无约束最优化方法无约束最优化方法这就确定了p1。.同理，有第二章第二章:无约束最优化方法无约束最优化方法 由于在导出上述公式的过程中利用了近似关系，以及H(x)的逐次变化，使其共轭性遭到破坏，因而对于一般非二次函数来说，要以步迭代取得收敛常常是不可能的，所以在实际应用中，如迭代步数kn已达到精度要求，则以xk作为要求的近似；否则可将前n步作为一个循环，同时以所有的xn作为新的初始点，重新开始，进行循环，直到满足要求的精度。这就得到非二次函数的共轭梯度的算法非二次函数的共轭梯度的算法：第二章第二章:无约束最优化方法无约束最优化方法非二次函数的共轭梯度的算法非二次函数的共轭梯度的算法：选择初始点x0，给出允许误差 0，k=0，xk=x0（1）计算f(xk)和G(xk)（2）令pk=-f(xk)（3）第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法 计算f(xk+1)和H(x K+1)(4)若f(xk+1)，则x*=xk+1，停止；否则，转下一步(5)若k n，则 k=k+1，转(3)；否则，x0=xk，k=0，转(1)。第二章第二章:无约束最优化方法无约束最优化方法例：例：f(X)=(X1-2)4+(X1-2)2X22+(X2+1)2的极小点，初始点为（1，1）T5、变尺度法 我们知道，牛顿法具有收敛速度快的优点，但又有明显的缺点。牛顿法要计算海赛矩阵，其计算量是很大的。一个自然的想法是采用梯度的离差近似海赛矩阵来克服这一困难。为了减少牛顿法在每一步的计算量，Davidon于1959年提出了一个设想。其核心是仅用在每次迭代中得到的梯度信息来近似海赛矩阵。即拟牛顿法。(1)、基本原理 假定无约束极值问题的目标函数f(x)具有二阶连续偏倒数，xk为其极小点的某一近似，第二章第二章:无约束最优化方法无约束最优化方法 在这个点附近取f(x)的二阶泰勒多项式展开：f(x)=f(xk)+f(xk)Tx+1/2xTH(xk)x x=x-xk 则其梯度为 f(x)f(xk)+H(xk)x这个近似函数的极小点满足 f(xk)+H(xk)x=0从而 x=xk H(xk)-1 f(xk)如果f(x)是二次函数，则H(xk)为常数阵，则逼近是准确的。在这种情况下，从任一点xk出发，只要一步即可求出f(x)的极小点。若f(x)不是二次函数，则逼近式仅是f(x)在xk点附近的近似表达式。第二章第二章:无约束最优化方法无约束最优化方法 这时，求得的所谓极小点，只是f(x)的极小点的近似，在这种情况下，常取 pk=H(xk)-1 f(xk)为搜索方向，即牛顿方向。问题在于：计算二阶导数的工作量太大或根本不可能。况且当x的维数很高时，计算逆阵也相当费事。为了解决此问题，构造另一个矩阵Hk，用它来直接逼近二阶导数矩阵的逆阵。下面就构造海赛矩阵逆阵的近似矩阵Hk，并且要求，在每一步都能以现有的信息来确定一个搜索方向，每做一次迭代，目标函数值均有所下降，而且这些近似矩阵最后应收敛于解点处的海赛矩阵的逆阵。第二章第二章:无约束最优化方法无约束最优化方法 当f(x)是二次函数时，其Hk为常数阵，可知其在任两点xk和xk+1处的梯度之差为 f(xk+1)-f(xk)=G(xk+1 xk)xk+1 xk=G-1f(xk+1)-f(xk)对于非二次函数，仿照二次函数的情形，要 求其海赛矩阵的逆阵的第k+1次近似矩阵Hk+1满足关系式 xk+1 xk=Hk+1f(xk+1)-f(xk)此式就是拟牛顿条件。第二章第二章:无约束最优化方法无约束最优化方法若令 Gk=f(xk+1)-f(xk)xk=xk+1 xk则 xk=H k+1Gk 现设H k+1已知，Hk和H k+1都为对称正定阵。H k+1=Hk+Hk (H k为第k次校正矩阵)H k+1应满足拟牛顿条件，即 xk=(H k+H k)Gk 或 HkGk=xk-HkGk 由此可以设想HK 的一种较简单形式为 HK=xk(Qk)T HKGk(Wk)T Qk与Wk为两个待定向量。第二章第二章:无约束最优化方法无约束最优化方法 xk(Qk)T HkGk(Wk)T Gk =xk HkGk 即 xk(Qk)TGkHkGk(Wk)TGk=xkHkGk 这就是说，应使 (Qk)TGk=Gk(Wk)T=1由于Hk应为对称阵，最简单的办法就是取 Qk=k xk Wk=k HkGk 设xkTGk以及GkTHkGk皆不为零，则有 k=1/xkTGk k=1/GkTHkGk第二章第二章:无约束最优化方法无约束最优化方法于是得到校正矩阵-第二章第二章:无约束最优化方法无约束最优化方法从而得到 上述矩阵为尺度矩阵，在整个迭代过程中，它是在不断变化的，由此可得变尺度法的算法：(2)、变尺度法的算法(1)给定初始点x0及梯度允许误差 0,H0=I,k=0(2)计算 f(xk)的值(3)若f(xk)2，则x0即为近似极小点，停止；否则，转下一步(4)pk=-Hk f(xk)，由一维搜索f(x)=min f(xk+kpk)确定合适的步长k(5)xk+1=xk+kpk，计算f(xk+1)的值(6)若f(xk+1)2，则x*=xk+1，停止；否则，xk=xk+1 xk，Gk=f(xk+1)f(xk)第二章第二章:无约束最优化方法无约束最优化方法 k=k+1，转(2)。此算法又叫DFP法(变尺度法)。例：用DFP方法求f(x)=(3/2)x12+(1/2)x22-x1x2-2x1的极小值，初始点为(-2,4)T。第二章第二章:无约束最优化方法无约束最优化方法DFP算法具有下列重要性质：(1)对于正定二次函数a.至多经过n次迭代即终止，且Hk=G-1b.保持满足前面的拟牛顿方程 HiGj=xj j=0,1,i-1c.产生的搜索方向是共轭方向第二章第二章:无约束最优化方法无约束最优化方法(2)对于一般函数a.保持矩阵Hk的正定性，从而确保算法的下降性b.算法为超线性的收敛速度c.对于凸函数是整体收敛d.每次迭代需要3n2+(n)次乘法运算第二章第二章:无约束最优化方法无约束最优化方法(3)、Broyden族拟牛顿法，又称BFGS算法。Broyden于1967年提出了一族修正公式第二章第二章:无约束最优化方法无约束最优化方法为实参数，可取任意实数。这组公式被称为Broyden族修正公式。当=0时，则Broyden族修正公式变成了DFP法修正公式。第二章第二章:无约束最优化方法无约束最优化方法此公式称为对称秩公式。当=1时，此公式即为BFGS修正公式。由于舍入误差的存在以及一维搜索的不精确，DFP算法的效率会受到很大影响，但BFGS算法所受影响要小得多。BFGS算法被公认为最好的拟牛顿算法。一般认为：解析法从迭代次数上考虑，DFP算法所需迭代次数较小，共轭梯度法次之，最速下降法最多。单从计算工作量来考虑，则最速下降法最简单，共轭梯度法次之，DFP方法最繁。第二章第二章:无约束最优化方法无约束最优化方法第二章第二章:无约束最优化方法无约束最优化方法6、步长加速法、步长加速法 步长加速法又称模式法或模矢法(Pattern Search)。(1)、基本原理 假定欲求某实值函数f(x)的极小点，任选一基点B1，算出此点的目标函数值f(xB1)，然后沿第i个坐标方向以某一步长i进行搜索,即在B1+xi和B1-xi 这二点中寻求能使目标函数值下降的点，并把它作为临时矢点；再由此点出发沿另一坐标方向进行同样的搜索，如能得到比以前更好的点，就以该点代替前面的点作为新的临时矢点，如此沿各个坐标方向轮流搜查一遍，并选这一轮搜索最好的点(最后的临时矢点)为第二个基点B2。由第一个基点B1到第二个基点B2构成了第一个模矢，对第一个基点来讲，可以认为这是使目标函数值得以改善的最有利的移动方向，沿这一方向前进，目标函数值下降最快。现假定在第二个基点B2附近进行类似的搜索，其结果可能和B1处的情况相同，则略去这一步搜索，把第一个模矢加长一倍（即所谓的加速）。现设其端点T20为第二个模矢的终点，在T20附近进行如上类似搜索，得出最好的点 第三个基点B3，据此修改假定的第二个模矢，使它的起点为B2，终点为B3，再把第二个模矢加长一倍，即可得到越来越好的目标函数下降点。第二章第二章:无约束最优化方法无约束最优化方法 如果搜索进行到某一步时，得不出新的下降点，则应缩小步长以进行更精细的搜索。当步长缩小到某一精度要求时，仍得不到新的下降点，则将该点作为所求的近似极小点，停止迭代。(2)、计算步骤、计算步骤(1)任选初始近似点B1,以它作为初始基点进行搜索(2)为每一独立变量xi(i=1,2,n)选定步长 xi=(0,i,0)T (第i个分量)(3)算出初始基点B1的目标函数值f(B1)，考虑点B1+x1，若f(B1+x1)f(B1)，就以B1+x1为临时矢点，否则还以B1为临时矢点。第二章第二章:无约束最优化方法无约束最优化方法 并记为T11 B1+x1；若 f(B1+x1)f(B1)T11=B1-x1；若 f(B1-x1)f(B1)B1；若 f(B1)minf(B1+x1),f(B1-x1)计算第二个独立变量x2的步长,并用T11代替基点B1第二章第二章:无约束最优化方法无约束最优化方法 T1j+xj+1 f(T1j+xj+1)f(T1j)T1,j+1=T1j-xj+1 f(T1j-xj+1)f(T1j)T1j f(T1j)minf(T1j+xj+1),f(T1j-xj+1)0 j n-1,T10=B0 得到临时矢点T1n，并令T1n=B2，原来的基点B1和新基点B2确定了第一个模矢。(4)将第一个模矢延长一倍，得到第二个模矢的初始临时点T20，T20=B1+2(B2-B1)=2B2-B1(5)在T20附近进行上述搜索，建立一系列临时矢点T21，T2n，以T2n 为第三个基点B3，则B2，B3就确定了第二个模矢，则第三个模矢的初始临时点为 T30=B2+2(B3 B2)=2B3 B2第二章第二章:无约束最优化方法无约束最优化方法(6)继续上述过程，对于第i个模矢，如果f(Ti0)0，初始点x0，设e1,e2,en为n个坐标轴上的单位向量，令k=1(1)计算f(x0)，f0=f(x0)，pi=ei，i=1,2,n(2)作一维搜索f(xk-1+k-1pk)=min f(xk-1+k-1pk)xk=xk-1+kpk，fk=f(xk)(3)若k=n，转下一步;否则k=k+1，转(2)(4)若xn-x2,则x*=xn,停止;否则转下一步第二章第二章:无约束最优化方法无约束最优化方法(5)=max(fk-fk+1)=fm-fm+1 0kn-1 f*=f(2xn-x0)(6)若f*f0,或(f0-2fn+f*)(f0-fn-)21/2(f0-f*)2 则p1,p2,pn不变。f0=f(xn),x0=xn,k=1，转(2)；否则转下一步。(7)令pk=pk，k=1,2,m，pk=pk+1，k=m+1,n-1，pn=(xn-x0)/xn-x0，f(xn+pn)=min f(xn+pn)，x0=xn+pn，f0=f(x0)，k=1，转(2)第二章第二章:无约束最优化方法无约束最优化方法例、用powell算法求解f(x)=x12+2x22-2x1x2-4x1的极小值，取x0=(1,1)T。第二章第二章:无约束最优化方法无约束最优化方法