67第五次模式搜索法和Powell算法

无约束昀优化问题的直接方法1.模式搜索法2.Powell算法3.单纯形替换法无约束昀优化问题;)(minxf直接方法：算函数值的方法。不用计算导数，只需计模式搜索法年）方法，（1961JeevesHooke−.1向交替实施两种搜索：轴算法从初始基点开始，基本思想：个坐标轴的方向进行，搜索依次沿搜索和模式搜索。轴向n。模式搜索则利于函数值下降的方向用来确定新的基点和有数值下降更快。线方向进行，试图使函沿着相邻两个基点的连算法分析.2个坐标轴方向。表示令nnjeTj,,2,1,)0,,0,1,0,,0(LLL==作为第一个基点。。任取初始点，加速因子给定初始步长1xαδ个基点。表示第以下用jxj方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中，iieiy的出发点。轴向搜索：。令11xy=O1e2e)1()1(yx=方向搜索：沿1e，则令如果)()(111yfeyf+δ;112eyyδ+=，否则，如果)()(111yfeyf−δ;112eyyδ−=则令。令否则，12yy=)2(y)3(y，进行搜索得到出发，仿上沿再从322yey。到点依次进行搜索，直到得1+ny)(一轮轴向搜索结束。为起点进行新的，仍以则缩小步长如果111,)()(xxfyfnδ≥+O1e2e)1()1(yx=)2(y)3(y模式搜索：,)()(11xfyfn+如果。则令12+=nyx方向可能有利于函数12xx−12xx−值下降，因此下一步沿方向进行模式搜索。即令。)(1221xxxy−+=α)2(x=)1(y轴向搜索。否则，进行模式搜索。有效？如何判断模式搜索是否。搜索，所得的点仍记为为起点进行下一轮轴向以11+nyy，令表明此次模式搜索成功如果,)()(21xfyfn+。13+=nyx仿上继续进行迭代。表明此次如果,)()(21xfyfn≥+进行下一轮轴向搜索。，点模式搜索失败，返回基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。否则，转；转如果)5()4(,)()(1knxfyf+。令模式搜索：)(,)4(11111kkknkxxxyyx−+==++++α）。转（令2,1,1:=+=jkk；停止，得到点如果)(,)5(kxεδ≤,:βδδ=否则，令）。转（令2,1,1:=+=jkk。kkkxxxy==+11,维搜索确定中的固定步长改为用一将轴向搜索和模式搜索注步长，算法仍然收敛。用模式搜索法求解问题例.1。2221)(minxxxf+=,125.0,)1,1(1===αδ加速因子，初始步长取初始点Tx缩减。率2.0=β:解轮迭代：第1。则令2)(,)1,1(111===yfxyT,)(5625.2)(111yfeyf=+δQ,)(5625.1)(111yfeyf=−δ。Teyy)1,75.0(112=−=∴δ,)(125.2)(222yfeyf=+δQ,)(125.1)(222yfeyf=−δ。Teyy)75.0,75.0(223=−=∴δ,)()(13xfyfQ。令32yx=∴。取加速方向Txxd)25.0,25.0(121−−=−=模式搜索：。Tdxy)5.0,5.0(121=+=α二.Powell方法基本思想：调整搜索方向三个基本搜索、加速搜索和方法主要由Powell个搜索方向的括从基点出发沿着已知部分组成。基本搜索包n个新基点。进行一维搜索，确定一的两加速搜索是指沿着相邻降更快。一维搜索，使函数值下个基点的连线方向进行昀后用基点新的搜索方向组，个搜索方向之一，构成连线方向代替已知的n进行下一轮迭代。原始Powell法步骤：。),1()2,1()1,1(,,,ndddL个线性无关的方向：给定初始点nx,)1(0。，令允许误差10=kε出发，依次沿方向从令)0,(1)0,(,)2(kkkxxx−=),()2,()1,(,,,nkkkdddL进行搜索，即令⎪⎩⎪⎨⎧+=++=−−−)(min)(:),()1,(),()1,(),()1,(),(jkjkjkjjkjjkjjkjkdxfdxfdxxλλλλλ得到点。),()2,()1,(,,,nkkkxxxL进行一维出发沿从令)1,(),()0,(),()1,(,++−=nknkknknkdxxxd。搜索得到点kx否则，令，停止，得到点若;||||)3(1kkkxxxε−−。njddjkjk,,2,1,)1,(),1(L==++）。返回（令2,1:+=kk.2例方法求解下述问题：用原始Powell21221)1()()(min−++=xxxxf。初始搜索方向为初始点为TTTddx)1,0(,)0,1(,)1,2()2,1()1,1(0===解：第一轮迭代：作一维搜索。出发沿着方向从)1,1()0,1(dx。令0)0,1(xx=)(min)1,1()0,1(dxfλλ+TTTdx)1,2()0,1()1,2()1,1()0,1(λλλ+=+=+Q,)1()3()()(22)1,1()0,1(λλλλϕ+++=+=dxf记,0)1(2)3(2=+++=λλλϕdd令。解得21−=λ。Tdxx)1,0()1,1(1)0,1()1,1(=+=∴λ作一维搜索，即求解出发，沿着方向再从)2,1()1,1(dx.)(min)2,1()1,1(dxfλλ+，解得12−=λ。所以Tdxx)0,0()2,1(2)1,1()2,1(=+=λ。令方向Txxd)1,2()0,1()2,1()3,1(−−=−=求解.)(min)3,1()2,1(dxfλλ+。解得1323−=λ。所以Tdxx)132,134()3,1(3)2,1(1=+=λ第二轮搜索：,)132,134(1)0,2(Txx==初始点:搜索方向为。TTdddd)1,2(,)1,0()3,1()2,2()2,1()1,2(−−====求解。)(min)1,2()0,2(dxfλλ+。所以解得Tdxx)134,134(,136)1,2(1)0,2()1,2(1−=+=−=λλ求解。)(min)2,2()1,2(dxfλλ+。所以解得Tdxx)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(dxfλλ+求解,493=λ解得。所以极小点为Tdxx)1,1()3,2(3)2,2(2−=+=λ迭代过程0x)1,1(x2x)2,1(xo1x)1,2(x)2,2(x2x1x定理对称正定矩阵。阶是，其中设nAcxbAxxxfTT++=21)(作一维搜索出发沿方向。从和点任意取定方向dxxxd121,则有作一维搜索得极小点出发沿方向从得极小点,,221ydxy12。共轭关于方向与Adyy−1x2x1y2ydd的分析：对例2。第一轮搜索方向：TTTddd)1,2(,)1,0(,)0,1()3,1()2,1()1,1(−−===。第二轮搜索方向：，TTTddd)16960,16936(,)1,2(,)1,0()3,2()22()1,2(−=−−==搜索得沿方向搜索得到极小点沿方向)2,2()0,2(1)3,1(,dxxd=和所以由定理可知方向)0,2()2,2()3,2(xxd−=,)2,2(x极小点共轭。和方向)2,2(d的，因此必为极小点。是沿共轭方向搜索得到2x对称正定矩阵。阶是，其中设nAcxbAxxxfTT++=21)(定理法求解下述昀优化问题用原始Powell。)(minxf下一轮轮，且每一轮迭代后为若迭代已进行了)(nmm≤线性个搜索方向所确定的前)(,,,),()2,()1,(mkdddnnkkk≤L向量组。共轭的生的加速方向必构成无关，则各轮迭代所产A注法。算法是一种共轭方向算原始Powell.1线性无关。个搜索方向的前算法不能保证各轮迭代原始nPowell.2方法求解下述问题：用原始Powell.3例,)(min2221xxxf+=。初始搜索方向为初始点为TTTddx)1,0(,)1,1(,)1,1()2,1()1,1(0=−==解：第一轮迭代：。令0)0,1(xx=.)(min)1,1()0,1(dxfλλ+求解。，所以解得Tdxx)1,1(0)1,1(1)0,1()1,1(1=+==λλ.)(min)2,1()1,1(dxfλλ+求解。，所以解得Tdxx)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(dxfλλ+求解。，所以解得Tdxx)0,1(0)3,1(3)2,1(13=+==λλ第二轮迭代：搜索方向：。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分析：)1(因。搜索方向线性相关的原)0,(),()1,(knknkxxd−=+)0,(),()1,()(knknnkxdx−+=−λL=)0,(),()2,(2)1,(1)0,(knknkkkxdddx−++++=λλλL),()2,(2)1,(1nknkkdddλλλ+++=L的线性组合。，，，是则如果),()3,()2,()1,(1,0nkkknkddddL+=λ个搜索方向线性相关。轮的则第令nkddikik1,)1,(),1(+=++解决方法：)2(。第一个一定是但不个搜索方向中的一个，换出原来的每次用ndnk)1,(+搜索方向？如何确定应换出哪一个。个搜索方向是单位向量假设初始的n。令)0,(),()0,(),()1,(knkknknkxxxxd−−=+满足使其选择搜索方向,),(skd,||max||1inistt≤≤=,|),,,,,,(det|),()1,()1,()1,()1,(ε++−nksknkskkdddddLL且次的搜索方向。构成第换出则用1,),()1,(++kddsknk。否则，令niddikik,,2,1,),(),1(L==+行列式的计算)3(|),,,,,,det(|),()1,()1,()1,()1,(1nksknkskkkdddddLL++−+=∆|),,,,,,det(|),()1,()0,(),(),()1,(1)1,()1,(nkskknknknkskkddxxdtdtddLLL+−−++=|),,,,,,det(|||),()1,(),()1,()1,()0,(),(nkskskskkknksdddddxxtLL+−−=kknksxxt∆−=)0,(),(||方法：改进的Powell。niedii,,1,),0(L==个线性无关的方向：给定初始点nx,)1(0。，令允许误差0,100==∆kε即个方向进行一维搜索，依次沿n。令kkxx=)0,()2(⎪⎩⎪⎨⎧+=++=−−−)(min)(:),()1,(),()1,(),()1,(),(jkjktjkjjkjjkjjkjkdtxfdtxftdtxx令。令)0,(),()0,(),()1,()3(knkknknkxxxxd−−=+⎪⎩⎪⎨⎧+=++=+++++++)(min)(:)1,(),()1,(1),(1)1,(1),(1nknktnknnknnknnkkdtxfdtxftdtxx）。否则转（算法结束，令如果5;,)4(1*1++=≤−kkkxxxxε,0:,,,1,1)5(0),0(====−=kxxnie