第五次模搜索法

《第五次模搜索法》由会员分享，可在线阅读，更多相关《第五次模搜索法（25页珍藏版）》请在装配图网上搜索。

1、无约束最优化问题的直接方法1.模式搜索法模式搜索法2.Powell 算法算法3.单纯形替换法单纯形替换法无约束最优化问题的直接方法无约束最优化问题的直接方法无无约约束束最最优优化化问问题题;)(minxf直直接接方方法法：算算函函数数值值的的方方法法。不不用用计计算算导导数数，只只需需计计一.模式搜索法年）年）方法，方法，（1961JeevesHooke 基本思想：基本思想：向向交替实施两种搜索：轴交替实施两种搜索：轴算法从初始基点开始，算法从初始基点开始，个个坐坐标标轴轴的的方方向向进进行行，搜搜索索依依次次沿沿搜搜索索和和模模式式搜搜索索。轴轴向向n。模式搜索则。模式搜索则利于函数值下降的

2、方向利于函数值下降的方向用来确定新的基点和有用来确定新的基点和有数数值值下下降降更更快快。线线方方向向进进行行，试试图图使使函函沿沿着着相相邻邻两两个个基基点点的的连连.1算法分析算法分析.2;)(minxf问题问题个个坐坐标标轴轴方方向向。表表示示令令nnjeTj,2,1,)0,0,1,0,0(作作为为第第一一个个基基点点。任任取取初初始始点点，加加速速因因子子给给定定初初始始步步长长1x 个基点。个基点。表示第表示第以下用以下用jxj方方向向搜搜索索时时个个坐坐标标轴轴表表示示沿沿第第用用在在每每一一轮轮轴轴向向搜搜索索中中，iieiy的出发点。的出发点。轴向搜索：轴向搜索：。令令11xy

3、 O1e2e)1()1(yx 方向搜索：方向搜索：沿沿1e，则令，则令如果如果)()(111yfeyf ;112eyy ，否则，如果否则，如果)()(111yfeyf ;112eyy 则令则令。令令否则，否则，12yy )2(y，进行搜索得到进行搜索得到出发，仿上沿出发，仿上沿再从再从322yey)3(yO1e2e)1()1(yx)2(y)3(y。到点到点依次进行搜索，直到得依次进行搜索，直到得1 ny)(一一轮轮轴轴向向搜搜索索结结束束。模式搜索：模式搜索：,)()(11xfyfn 如果如果。则令则令12 nyx方方向向可可能能有有利利于于函函数数12xx 12xx 值下降，因此下一步沿值下

4、降，因此下一步沿方方向向进进行行模模式式搜搜索索。即令即令。)(1221xxxy )2(x)1(y为为起起点点进进行行新新的的，仍仍以以则则缩缩小小步步长长如如果果111,)()(xxfyfn 轴向搜索。轴向搜索。否否则则，进进行行模模式式搜搜索索。有效？有效？如何判断模式搜索是否如何判断模式搜索是否。搜索，所得的点仍记为搜索，所得的点仍记为为起点进行下一轮轴向为起点进行下一轮轴向以以11 nyy，令令表表明明此此次次模模式式搜搜索索成成功功如如果果,)()(21xfyfn 。13 nyx仿仿上上继继续续进进行行迭迭代代。表表明明此此次次如如果果,)()(21xfyfn 进进行行下下一一轮轮轴

5、轴向向搜搜索索。，点点模模式式搜搜索索失失败败，返返回回基基2xO1e2e)1()1(yx)2(y)3(y)2(x)1(y)2(y)3(y x1x2x3x4x5x6x模式搜索法：模式搜索法：，缩减率，缩减率，加速因子，加速因子初始步长初始步长给定初始点给定初始点1,)1(1 nRx。精度精度0,)1,0(。令令1,1,11 jkxy轴向搜索：轴向搜索：)2(）；）；（转转则令则令如果如果3,)()(1jjjjjjeyyyfeyf ）；）；（转转则令则令如果如果3,)()(1jjjjjjeyyyfeyf 。否则，令否则，令jjyy 1。转转则令则令，若若)2(,1:)3(jjnj。否则，转否则，

6、转；转转如果如果)5()4(,)()(1knxfyf 。令令模式搜索：模式搜索：)(,)4(11111kkknkxxxyyx ）。）。转（转（令令2,1,1:jkk；停止，得到点停止，得到点如果如果)(,)5(kx ,:否则，令否则，令。kkkxxxy 11,）。）。转（转（令令2,1,1:jkk注注维搜索确定步长，维搜索确定步长，中的固定步长改为用一中的固定步长改为用一将轴向搜索和模式搜索将轴向搜索和模式搜索算算法法仍仍然然收收敛敛。用用模模式式搜搜索索法法求求解解问问题题例例.1。2221)(minxxxf ,125.0,)1,1(1 加速因子加速因子，初始步长初始步长取初始点取初始点Tx

7、缩减缩减。率率2.0 :解解轮轮迭迭代代：第第1。则则令令2)(,)1,1(111 yfxyT,)(5625.2)(111yfeyf ,)(5625.1)(111yfeyf 。Teyy)1,75.0(112 ,)(125.2)(222yfeyf ,)(125.1)(222yfeyf 。Teyy)75.0,75.0(223 ,)()(13xfyf。令令32yx 。取加速方向取加速方向Txxd)25.0,25.0(121 模模式式搜搜索索：。Tdxy)5.0,5.0(121 二.Powell 方法基本思想：基本思想：调调整整搜搜索索方方向向三三个个基基本本搜搜索索、加加速速搜搜索索和和方方法法主主

8、要要由由 Powell个个搜搜索索方方向向的的括括从从基基点点出出发发沿沿着着已已知知部部分分组组成成。基基本本搜搜索索包包n个个新新基基点点。进进行行一一维维搜搜索索，确确定定一一的的两两加加速速搜搜索索是是指指沿沿着着相相邻邻降更快。降更快。一维搜索，使函数值下一维搜索，使函数值下个基点的连线方向进行个基点的连线方向进行最后用基点最后用基点新新的的搜搜索索方方向向组组，个个搜搜索索方方向向之之一一，构构成成连连线线方方向向代代替替已已知知的的 n进进行行下下一一轮轮迭迭代代。原始 Powell 法步骤：个个线线性性无无关关的的方方向向：给给定定初初始始点点nx,)1(0。),1()2,1(

9、)1,1(,nddd。，令，令允许误差允许误差10 k 出出发发，依依次次沿沿方方向向从从令令)0,(1)0,(,)2(kkkxxx ),()2,()1,(,nkkkddd进进行行搜搜索索，即令即令 )(min)(:),()1,(),()1,(),()1,(),(jkjktjkjjkjjkjjkjkdtxfdtxftdtxx得到点得到点。),()2,()1,(,nkkkxxx进进行行一一维维出出发发沿沿从从令令)1,(),()0,(),()1,(,nknkknknkdxxxd。搜索得到点搜索得到点kx否则，令否则，令，停止，得到点，停止，得到点若若;|)3(1kkkxxx 。njddjkjk,

10、2,1,)1,(),1(）。）。返回（返回（令令2,1:kk.2例例方法求解下述问题：方法求解下述问题：用原始用原始 Powell21221)1()()(min xxxxf。初始搜索方向为初始搜索方向为初始点为初始点为TTTddx)1,0(,)0,1(,)1,2()2,1()1,1(0 解：解：第一轮迭代：第一轮迭代：。令令0)0,1(xx 作作一一维维搜搜索索，即即求求解解出出发发沿沿着着方方向向从从)1,1()0,1(dx.)(min)1,1()0,1(dtxft TTTttdtx)1,2()0,1()1,2()1,1()0,1(,)1()3()()(22)1,1()0,1(ttdtxft

11、 记记,0)1(2)3(2 ttdtd 令令。解得解得21 t。Tdtxx)1,0()1,1()0,1()1,1(作作一一维维搜搜索索，即即求求解解出出发发，沿沿着着方方向向再再从从)2,1()1,1(dx.)(min)2,1()1,1(dtxft，解得解得12 t。所以所以Tdtxx)0,0()2,1(2)1,1()2,1(。令方向令方向Txxd)1,2()0,1()2,1()3,1(求解求解.)(min)3,1()2,1(dtxft。解得解得1323 t第二轮搜索：第二轮搜索：,)132,134(1)0,2(Txx 初始点初始点。所以所以Tdtxx)132,134()3,1(3)2,1(1

12、 :搜索方向为搜索方向为。TTdddd)1,2(,)1,0()3,1()2,2()2,1()1,2(求解求解。)(min)1,2()0,2(dtxft。所以所以解得解得Tdtxxt)134,134(,136)1,2(1)0,2()1,2(1 求解求解。)(min)2,2()1,2(dtxft。所以所以解得解得Tdtxxt)16934,16988(,16918)2,2(2)1,2()2,2(2 。令方向令方向Txxd)16960,16936()0,2()2,2()3,2(求解求解。)(min)3,2()2,2(dtxft,493 t解得解得。所以极小点为所以极小点为Tdtxx)1,1()3,2(

13、3)2,2(2 0 x)1,1(x1x2x)2,1(xo1x)1,2(x)2,2(x2x迭代过程迭代过程定理定理对称正定矩阵。对称正定矩阵。阶阶是是，其中，其中设设nAcxbAxxxfTT 21)(作作一一维维搜搜索索得得极极小小出出发发沿沿方方向向。从从和和点点任任意意取取定定方方向向dxxxd121,dyyydxy方向方向与与则有则有作一维搜索得极小点作一维搜索得极小点出发沿方向出发沿方向从从点点12221,共轭。共轭。关于关于 A的的分分析析：对对例例 2。第一轮搜索方向：第一轮搜索方向：TTTddd)1,2(,)1,0(,)0,1()3,1()2,1()1,1(。第二轮搜索方向：第二轮

14、搜索方向：，TTTddd)16960,16936(,)1,2(,)1,0()3,2()22()1,2(搜搜索索得得极极小小点点沿沿方方向向搜搜索索得得到到极极小小点点沿沿方方向向)2,2()0,2(1)3,1(,dxxd,)2,2(x共轭。共轭。和方向和方向所以由定理可知方向所以由定理可知方向)2,2()0,2()2,2()3,2(dxxd 的的，因因此此必必为为极极小小点点。是是沿沿共共轭轭方方向向搜搜索索得得到到2x定理定理对称正定矩阵。对称正定矩阵。阶阶是是，其中，其中设设nAcxbAxxxfTT 21)(法法求求解解下下述述最最优优化化问问题题用用原原始始 Powell。)(minxf

15、下下一一轮轮所所确确定定的的轮轮，且且每每一一轮轮迭迭代代后后为为若若迭迭代代已已进进行行了了)(nmm 线线性性无无关关，则则各各轮轮迭迭代代个个搜搜索索方方向向前前)(,),()2,()1,(mkdddnnkkk 共共轭轭的的向向量量组组。成成所所产产生生的的加加速速方方向向必必构构A注注法法。算算法法是是一一种种共共轭轭方方向向算算原原始始 Powell.1个个搜搜索索方方向向线线性性无无关关。的的前前算算法法不不能能保保证证各各轮轮迭迭代代原原始始nPowell.2.3例例方法求解下述问题：方法求解下述问题：用原始用原始 Powell,)(min2221xxxf 。初始搜索方向为初始搜

16、索方向为初始点为初始点为TTTddx)1,0(,)1,1(,)1,1()2,1()1,1(0 解：解：第一轮迭代：第一轮迭代：。令令0)0,1(xx.)(min)1,1()0,1(dtxft 求解求解。，所以，所以解得解得Tdtxxt)1,1(0)1,1(1)0,1()1,1(1 .)(min)2,1()1,1(dtxft 求解求解。，所以，所以解得解得Tdtxxt)0,1(1)2,1(2)1,1()2,1(2 。令方向令方向Txxd)1,0()0,1()2,1()3,1(.)(min)3,1()2,1(dtxft 求解求解。，所以，所以解得解得Tdtxxt)0,1(0)3,1(3)2,1(1

17、3 第第二二轮轮迭迭代代：搜索方向：搜索方向：。TTdddd)1,0(,)1,0()3,1()2,2()2,1()1,2(，到到的的线线性性相相关关，以以下下迭迭代代得得和和)2()0,1()2,2()1,2(kxddTk。不不能能得得到到最最优优解解Tx)0,0(*个个搜搜索索方方向向线线性性无无关关？如如何何确确保保各各轮轮迭迭代代的的前前问问题题：n)0,(),()1,(knknkxxd 分分析析：)1()0,(),()1,()(knknnkxdtx )0,(),()2,(2)1,(1)0,(knknkkkxdtdtdtx ),()2,(2)1,(1nknkkdtdtdt 因因。搜搜索索

18、方方向向线线性性相相关关的的原原的线性组合。的线性组合。，是是则则如果如果),()3,()2,()1,(1,0nkkknkddddt 个个搜搜索索方方向向线线性性相相关关。轮轮的的则则第第令令nkddikik1,)1,(),1(解解决决方方法法：)2(但但不不一一定定是是个个搜搜索索方方向向中中的的一一个个，换换出出原原来来的的每每次次用用ndnk)1,(第一个。第一个。搜搜索索方方向向？如如何何确确定定应应换换出出哪哪一一个个。个个搜搜索索方方向向是是单单位位向向量量假假设设初初始始的的 n。令令)0,(),()0,(),()1,(knkknknkxxxxd 满满足足使使其其选选择择搜搜索索

19、方方向向,),(skd,|max|1inistt ,|),(det|),()1,()1,()1,()1,(nksknkskkddddd且且。否则，令否则，令niddikik,2,1,),(),1(次次的的搜搜索索方方向向。构构成成第第换换出出则则用用1,),()1,(kddsknk行行列列式式的的计计算算)3(|),det(|),()1,()1,()1,()1,(1nksknkskkkddddd|),det(|),()1,()0,(),(),()1,(1)1,()1,(nkskknknknkskkddxxdtdtdd|),det(|),()1,(),()1,()1,()0,(),(nksksk

20、skkknksdddddxxt kknksxxt )0,(),(|方法：方法：改进的改进的Powell个个线线性性无无关关的的方方向向：给给定定初初始始点点nx,)1(0。niedii,1,),0(。，令，令允许误差允许误差0,100 k。令令kkxx)0,()2()(min)(:),()1,(),()1,(),()1,(),(jkjktjkjjkjjkjjkjkdtxfdtxftdtxx即即个方向进行一维搜索，个方向进行一维搜索，依次沿依次沿n令令。令令)0,(),()0,(),()1,()3(knkknknkxxxxd )(min)(:)1,(),()1,(1),(1)1,(1),(1nk

21、nktnknnknnknnkkdtxfdtxftdtxx）。）。否则转（否则转（算法结束，令算法结束，令如果如果5;,)4(1*1 kkkxxxx,0:,1,1)5(0),0(kxxniednknii令令。则令则令，若若）。）。转（转（2。使得使得确定确定，若若inisttsnk 1max1,)0,(),(kknksxxt如果如果。则则niddikik,1,),(),1(）。）。转（转（令令2,1kk ；则令则令如果如果1,1,),(),1()0,(),(siddxxtikikkknks。nsiddddikiknksk,1,;)1,(),1()1,(),1(）。）。转（转（令令2,1:,)0,(),(1 kkxxtkknksk