无约束最优化问题的直接方法

无约束最优化问题的直接方法1.模式搜索法2.Powell算法3.单纯形替换法无约束最优化问题的直接方法无约束最优化问题;)(minxf直接方法：算函数值的方法。不用计算导数，只需计一.模式搜索法年）方法，（1961JeevesHooke基本思想：向交替实施两种搜索：轴算法从初始基点开始，个坐标轴的方向进行，搜索依次沿搜索和模式搜索。轴向n。模式搜索则利于函数值下降的方向用来确定新的基点和有数值下降更快。线方向进行，试图使函沿着相邻两个基点的连.1算法分析.2;)(minxf问题个坐标轴方向。表示令nnjeTj,,2,1,)0,,0,1,0,,0(作为第一个基点。。任取初始点，加速因子给定初始步长1x个基点。表示第以下用jxj方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中，iieiy的出发点。轴向搜索：。令11xy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值下降，因此下一步沿方向进行模式搜索。即令。)(1221xxxy)2(x)1(y为起点进行新的，仍以则缩小步长如果111,)()(xxfyfn轴向搜索。否则，进行模式搜索。有效？如何判断模式搜索是否。搜索，所得的点仍记为为起点进行下一轮轴向以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,:否则，令。kkkxxxy11,）。转（令2,1,1:jkk注维搜索确定步长，中的固定步长改为用一将轴向搜索和模式搜索算法仍然收敛。用模式搜索法求解问题例.1。2221)(minxxxf,125.0,)1,1(1加速因子，初始步长取初始点Tx缩减。率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方法基本思想：调整搜索方向三个基本搜索、加速搜索和方法主要由Powell个搜索方向的括从基点出发沿着已知部分组成。基本搜索包n个新基点。进行一维搜索，确定一的两加速搜索是指沿着相邻降更快。一维搜索，使函数值下个基点的连线方向进行最后用基点新的搜索方向组，个搜索方向之一，构成连线方向代替已知的n进行下一轮迭代。原始Powell法步骤：个线性无关的方向：给定初始点nx,)1(0。),1()2,1()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,,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记,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:搜索方向为。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(3)2,2(20x)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(。第二轮搜索方向：，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下一轮所确定的轮，且每一轮迭代后为若迭代已进行了)(nmm线性无关，则各轮迭代个搜索方向前)(,,,),()2,()1,(mkdddnnkkk共轭的向量组。成所产生的加速方向必构A注法。算法是一种共轭方向算原始Powell.1个搜索方向线性无关。的前算法不能保证各轮迭代原始nPowell.2.3例方法求解下述问题：用原始Powell,)(min2221xxxf。初始搜索方向为初始点为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(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)0,(),()1,(knknkxxd分析：)1()0,(),()1,()(knknnkxdtx)0,(),()2,(2)1,(1)0,(knknkkkxdtdtdtx),()2,(2)1,(1nknkkdtdtdt因。搜索方向线性相关的原的线性组合。，，，是则如果),()3,()2,()1,(1,0nkkknkddddt个搜索方向线性相关。轮的则第令nkddikik1,)1,(),1(解决方法：)2(但不一定是个搜索方向中的一个，换出原来的每次用ndnk)1,(第一个。搜索方向？如何确定应换出哪一个。个搜索方向是单位向量假设初始的n。令)0,(),()0,(),()1,(knkknknkxxxxd满足使其选择搜索方向,),(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,(),(nkskskskkknksdddddxxt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),(1nknktnknnknnknnkkdtxfdtxftdtxx）。否则转（算法结束，令如果5;,)4(1*1kkkxxxx,0:,,,1,1)5(