第四章 2011修改--无约束最优化的直接方法

1、min( )nxRfx1 单纯形单纯形：Rn中的单纯形指具有n+1个顶点的多面体，若各棱长彼此相等，则称为正规单纯形。如：在R2中，三角形就是单纯形，正三角形就是正规单纯形。（正三角形是R2中周长一定包围面积最大的布点方式） 结论： 对于任意给定初始点z1和正数l，按如下公式取定的单纯形是一个以为z 1顶点棱长为l的Rn中的正规单纯形：v 1= z 1 , v i = z1+z(i) i=2,3,4n+1其中n 维向量z(i)=q q,pi-1,q qT如:z(2)=p,q qT.z(n+1)=q,q pT.其中(11)2(1 1)2lpnnnlqnn 22ijvvlij，21 ivv 222

2、22111 1ivvzz izz ipnq221 ivvl 22222222 ( ) 11ijvvz iz jz iz jz i z jz i z jllpq pqnqpq pqnq 1,101nhiiivnv00()01rhvvvv为反射系数,常取zhviv0v brvlvlvev0vvzivhv a00()chvvvvhi 21)(orocvvvvivhvrvlv divhvrvlv eivhvrvlv c1,1, 2, 312liivvvil in!1*111,11niiniivnvfnfeffnii211222121654,minxxxxf0128 , 9,1 0 , 1 1,8 ,

3、1 1TTTxxx2018,102Tihixxx0122101200m a x1 2 5,m i n4 5,hlffffxxffffxx4344, 8,8Txxrxxfx43fxfx1434,8,13Txxfx0 ,12220 ,121 ,1ma x ,6 5,mi n ,8llffffxxffffxx0120128 , 9,4 , 8,8 , 1 14 5 ,8 ,6 5TTTxxxfff336,9,13Thxxxxfx313fx013343416 , 8 .524 , 6,42 , 3 .5,8TThTlxxxxxxxfxxxrxxfxfn 这个方法由两类移动所构成，一类是这个方法由两类移

4、动所构成，一类是探测性移动探测性移动，另一类是，另一类是模模式性移动式性移动；前者为了揭示函数变化规律，探测函数；前者为了揭示函数变化规律，探测函数f (x)下降方向，下降方向，后者是利用发现的函数变化规律循着有利方向（也可看作近似梯度后者是利用发现的函数变化规律循着有利方向（也可看作近似梯度方向）寻找较好的点，可看成一种加速。下面先对算法过程做一些方向）寻找较好的点，可看成一种加速。下面先对算法过程做一些说明，再给出算法过程。说明，再给出算法过程。n 给定初始点给定初始点 x0 和步长和步长 （也可对不同坐标方向给出不同步（也可对不同坐标方向给出不同步长长: ，以向量，以向量 =( ) i=

5、 1,2,3 ,n 描述步长）描述步长）n 探测性移动探测性移动：从迭代点出发，依次沿坐标方向找下降点，为标：从迭代点出发，依次沿坐标方向找下降点，为标出点与坐标方向之间的关系，采用记号出点与坐标方向之间的关系，采用记号 表示第表示第 k 次迭代按坐次迭代按坐标方向标方向 ei 在探测性移动时得到的点。在探测性移动时得到的点。iiik ,110,1 ,ekkkk0,1,0kkff,1,011kke0,1,kkff,1,01 1kke,1,011kke0,1 ,kkff, 0kk,k i,1,1k ik iiik ik iieff若不 变,1,1,()()01k ik ik ik iiifff若

6、,1,1,-()()k ik iiik ik ik iiefff若不 变,1,0kkff,1,0kk11（如各分量减半）重新开始探测性移动。若 充分小，则终止。 上式对上式对i=1，2，n 进行。求出进行。求出 若此若此 则完成了探则完成了探测性移动，再开始模式移动。若测性移动，再开始模式移动。若 则再进行探测性移动。再则再进行探测性移动。再进行探测性移动时，若步长进行探测性移动时，若步长 ： 时，则认为时，则认为 即为近似极即为近似极小小值点（这是因为值点（这是因为 而而 时，必将有时，必将有 很小很小接近于接近于0）nk,0 .,knk0 .,knk0 . k0 .,knk)(kf1111

7、1111( ),( )kkkkkkkkif yfyiif yf若则令一次迭代完成。若则令并将步长 缩小 下面再看模式移动（Pattern Move）记 从 出发，沿方向 以步长 求出新的试验点 即 然后再从 出发进行一次探测性移动，得到点 这时有：1kl0 .,1knkkkkkP11112(1)kkkkkkkl Pl1+k1k1ky1+k模式移动方向可以看作梯度方向的一个近似，因而本方法也可以看作是最速下降的一个近似。因此这个方法的收敛速度较慢。特别是在最优点附近，但当变量个数较少时，此方法可能是有用的。此方法也可以与其它方法结合使用，以便在最优化过程开始阶段找到一个较好的初始点。)()(11

8、kkfyfi0kk1k21kk1k11kky1k)()(11kkfyfii1ky1k12kk1k0,kk( ),fza 二算 法 过 程 ：已 知 目 标 函 数步 长 向 量个nTn. 1.0 .),.,(2112,.neee不 同 方 向 ， 不 妨 取 为控 制 误 差,:0 .10kz。选定初始点ikkzziaa,00:,:0 .1.2 .2探测位移。1,.1.1.0:)()()( :),()()( .:).()(.3.2ikikikzzzfzfzfzzzfzfzfzzzfzf，则若则若则若0.11.11.2 .2 . :.-: ,:k iiik iiik izez zezzz0000

9、3,2.2,.5.2:1.4.2转，若则返回若niniii0,111102,:1).()(.6转则若kkzDzfDfkkkk。转。否则转则若00,0,1,0,04,5:.3knkknkknkzzzzzz。转则则终止，否则最优解若0,*01.2.:,|.|.4aaazzank01015 .2-:.2.kkkzzzzD从出 发 再 做 探 测 移 动 。即 类 似 于步 ， 得 出0,11111.2:,:1:).()(转则若kkzzzfDfkkkk2112221212-4-2),(minxxxxxxxf+=例：求解：00 , 0100()( (1 , 1 )(1 , 0 ) )( 2 , 1 )6

10、(,)(1 , 1 )3zfzefffzf从出发做探测性移动：由于21,1)1 ,0(,)0,1(,)1 ,1(21210=TTTeez取解：0 ,10 ,120 ,10 ,120110 ,20 ,1110(2 ,1).()(2 , 2 )4()(2 ,1)6 .()(2 , 0 )4(, )(2 ,1),()6 .TTzfzeffzffzeffzzzzfzzz 故但故 ，以 上 完 成 一 次 探 测 性 移 动 ， 因可 开 始 模 式 移 动 。110111221122 (2 ,1)(1,1)(3,1),:()(),TTTkzzzzeeeefzfz令再 从出 发 做 探 测 性 移 动

11、。由 于 沿探 测 得 到 点 的 函 数 值 均大 于则 :1111111111,21,01(3,1) ,()()7()(3,1) , ()1,(3,1) ,(3,1)1(1,1)(0.5, 0.5) .2TTTTTTDzfDfzfzzDzkzzzza 而故 令与 前 面 算 法 描 述 有 点 不 同令从开 始 第 二 次 迭 代 。首 先 进 行 探 测 性 移 动 ， 求 得仍 然 为。 因 而 将 步 长 缩 小 一 半 进 行 探 测 ， 即令 ：这 样 有。再进行模式移动，取5 . 7-)()5 . 1 , 3(.) 1 , 3()5 . 1 , 3(220, 12, 1zfzz

12、zTTT1,21,02222122(3,1.5)(3,1) .(3,1.5)()7.523 2()7,10.5TTTTzzzf zzzzf zz 取，。再进行模式移动，（ ，）。再从出发做探测性移动。（取的结果如下，若，则多做一步)2222232(4, 2) ,()-8()-7()()(4, 2)TTDfDfzfDfzzz得 到 : 。 从 而 得 新 迭 代 点 :，开始迭代，则总有若再从，3032,33zzzz*(4,2) .Tz 可以不断缩小步长，因此最优解为)(az)(bz1x2x*zz（0）)1(z1x2x1x2xP0P0p1*z)(bz)(az)(oz)1(z （2） P0. Pm

13、-1 是互为Q共轭的向量系，mn. （3）z 1 ,z 2是任意的两个不同点，则若分别从z 1 ,z 2 出发依次沿方向P。 作直线搜索，最后得到直线搜索的极小点分别设为 设P= ，那么P 与 是互为Q 的共轭的.定理一： 若（1）二次函数f(z)= 中的Q对称正定。121CZbQZzTT11.mPP11.mPP*2*1,zz*2*1zz 这就是说，由 z (0) 出发，依次沿方向P0, P1 求极小，便得到最优点。而我们在介绍共轭梯度法及共轭方向时，也具有这一性质。可以证明此种P0 P1方向是共轭方向。 对于n维情形。我们在第三章已经证明过有下边结论：下面我们看一个具体例子：例:f( ) 解

14、：取 沿方向 求极小得点在从 出发沿方向 求极小，得点又从 出发沿方向 求极小，得点 于是那么此方向应与 P0 是共轭的。事实上也是这样，因为：21,xx2122212xxxx(22Tz 。， ）Tp），（。10Taz) 1 , 2()()(aZ1(1,0)Tp 1(0.25,1)Tz 1z0(0,1)Tp Tbz)125. 0 ,25. 0()(pzzab)875. 0,75. 1()()(2114Q可见从不同起点沿同一方向进行直线搜索可以产生共轭方向。Powell方向正是基于这一思想而产生的。他的办法是沿着n个坐标方向依次求极小值，这样经过n次以后所得到的n个新方向就是相互共轭的。这是po

15、well方法的原始方案，过程如下： 已知目标函数f(z).给定z0,.21neee. . . 1,:,:01njpekjj。0410( 1.75, 0.85)0121Tp Qp 故,020:,:kkj zz。11,1,3+=jjjkjkptzz。中其)(min)(1,11,jjkjjjktpzfptzfjj : 14。1, 0, 07:, (11 ):jjknknknkppjnxxpxx。若则 最优解 ,0k nkzznkzz,*终止否则转。7。6。5若转若. nj nj。6转30kk:1转2沿 作直线搜索npnnnnkskpppppppzlz.,:.,),(21110,1 但是，原始但是，原

16、始 powell 方法有一个主要的缺点，即这样更换方法有一个主要的缺点，即这样更换方向所产生的方向所产生的n个向量有时可能是近似线性相关的，从而使个向量有时可能是近似线性相关的，从而使其真的极小点可能被漏掉。为克服这些缺点，其真的极小点可能被漏掉。为克服这些缺点，powell自己自己将其方法做了某些改进，但改进后的方法一般不是二次终将其方法做了某些改进，但改进后的方法一般不是二次终结的了，即对于结的了，即对于n元二次函数元二次函数f(z)求极小点，即使求极小点，即使n次迭代也次迭代也不一定能找到极小点。但修正的不一定能找到极小点。但修正的powell方法能克服出现退方法能克服出现退化的情形，尽

17、管收敛速度比原始的化的情形，尽管收敛速度比原始的Powell方法慢些，但仍方法慢些，但仍不失为无约束极小值直接优化方法中最有效的一个不失为无约束极小值直接优化方法中最有效的一个。其过程如下：其过程如下：已知已知f(z),取及取及n个初始搜索方向，不防取个初始搜索方向，不防取给定控制误差，较大的正数给定控制误差，较大的正数M。Zneee.2110 :,:,1ojjk epjn0,20:,-:,k jj zM 11,1,3+=jjjkjkoptzzo4: )()(,)()(1,1,jkjkjkjkzfzfzfzf)(min)(1,11,jjkjjjktpzfptzf其中Jj:1否则J,不变，转 5

18、jjo :15o6若转7； 若转3。nj nj o7若则最优解否则转8oknkzz,nkzz,*)-2 (),(),(8,3,2,1oknknkokozzffzffzffo11,:1,:1,kkzzknk转2。o10若转11否则转12231221321)(21)(2(fffffffo9若转11 ，若则转10,13ff 3ffo12令,:1,:),11( ,:)(min)(.,1,*,*,1,kkpppnjpptpzfptzfptzzzzpnjjnknknkkoknk转2解：取 初始方向 第一轮Tz) 1 , 1 (0TTpp) 1 , 0(,) 1, 1 (211221 ,02,010,01

19、,00,00:,)0 , 1 (),()1 , 1 (),(:PPPZLZPZLZZZTSTS2221)(minxxzf例：用原始powell方法求解无约束问题：再沿加速方向 进行直线搜索，即Toozzp) 1, 0(2,2222,01)(minttpzf则 则完成一轮迭代0*tTzptzz) 0 , 1 (2 , 02*2 , 01TSTSPZLZZPZLZZZ)0 , 1 (),()0 , 1 (),(:21 , 12, 1110, 11 , 10, 11TTopp) 1,(,) 1 , 0(21（线形相关）第二轮，有两个搜索方向 这样原始powell法导出任一第k轮迭代点z始终停留在非最

20、优点 处而原向量最优点为可见原始powell方法失效。Toz), 1 (1Tz)0 , 0(* 修正的目的在于保证 线性无关。关于其证明过程从略，参见 computer Journal, vol.7. p154162.1964nppp.21 由迭代过程可以看出：在某些时候一组n个方向不变，因此当n很大时，powell修正方案接近于轮换坐标法。因而收敛速度慢，根据经验，powell方法适应的范围大体上可限制在问题中的变量在20个以下，当然，计算机速度快时，问题维数也可以提高。例：给定初始点 则211222121242),(minxxxxxxxfTz) 1 , 1 (03)(0zf因 因此5 .

21、0)()(, 4)()(2 , 01 , 01 , 00 , 0zfzfzfzf4, 1j5 . 7)(,)5 . 1 , 3(212,21 , 02, 0oTzfpzz故21,0)(,7-2-2)1 , 3()()1 , 3(7-)(,)4, 3(2,221 ,02,01 ,010,01 ,0ttFtttftFttpzzzfpzzTT故2,0)(,34)1 ,1()()1 ,1()1 , 1(,)1 ,0(,)0, 1(,210,01 ,000,021ttFtttftFttpZZZZppTTTT取故令 并从 出发沿方向P求极小，得 完成一次迭代。而且下一次迭代的两个搜索方向为： Tzzp)

22、5 . 0 , 2 (0 , 02 , 09.7)(,)517,519(11zfzT2, 0z7)(, 5 . 7)(3)(, 7)(,) 5 . 0 , 2 (232 , 020 , 010 , 02 , 0zffzffzffzfzzzT又32)(2125. 1)(2221221321fffffff,13ff 因 且TZZ)517,519(10 , 1取12(0,1) ,(2,0.5)TTpp016.0)()(,08.0)()(2, 11 , 11 , 10, 1zfzfzfzfTzzzj)5024,25103(208.0,10,12,1又故TTTppzfzfffffzf)5.0,2(.)1

23、 ,0(996.7)(,)5097,2599(,3,996.7,9.7,3)(212213321搜索方向仍为：故令因996.7)(.)5097,2599(98.7)(.)1019,519(,2,12,11,1)1,1(21zfzzfzppTT求极小得：分别沿向量，于是仍按更换搜索方向进行方法。在第二次迭代时若我们不用修正值为而此时近似解为极小值为易见原向题的极小点为powellzzTT99984.7)988.1 ,992.3(8,)2 , 4(*Tzzp)256,254(0 , 12, 1=此时已得极小点。），（求极小，即为点出发沿则从Tpz242,1是共轭的。）关于（注意2111)6,4(,

24、)5.0,2(21QppT99984.7)(.)250497,250998(9992.7)(.)5099,2599(996.7)(.)5097,2599(,2,22,21,21,20,20,221zfzzfzzfzppTTT求极小得依次沿 Rosenbrock在1960年提出一种直接最优化法。此法的每一轮迭代采用变步长的轴向移动。然后再利用轴向的旋转来产生一组新的方向作为下一轮迭代的轴向。由于方法特点是在每一轮迭代之后要进行轴向的旋转，故而叫作旋转方向法旋转方向法，旋转方向的目的是为了加速收敛速度。 前面Hook-Jeeves 模式搜索法中，轴向移动的步长在一定阶段保持不变，只在适当条件时才做

25、缩减。 但在Rosenbrock法中，轴向移动的步长在探测过程中独立地随时变化。即探测成功增加步长，失败则减小步长，具体做法是：4.4 Rosenbrock法 （旋转方向法）1kzkzkznddd.211kz 事先给定一个步长增大系数 和步长缩减系数 若从一个参考点出发沿平行与某轴向作探测成功时则下一次沿此方向探测的步长增加 倍，若失败，则取原步长的 倍。10111 12 2.kkn nzzddd由于第k轮迭代中沿平行于每一轴向的各方向都移动过，因而 令njj1, 011122222.nnnnnnnddddddddd利用 gram-smith 正交化方法得方向组标准正交化为新的 作为下一轮迭代轴向。其算法过程为：nddd,.,21nddd,.,2111 取初点 ，标准正交化向量组 初始