第六次直接法最优化

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

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

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

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

5、y 3y2x x1x2x3x4x模式搜索法：模式搜索法：，缩缩减减率率，加加速速因因子子初初始始步步长长给给定定初初始始点点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 ）。转转（

6、令令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

7、, )(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个个搜搜索索方方向向的的括括从从基基点点出出发发沿沿着着已已知知部部分分组组

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

9、,(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例例方法求解下述问题：方法求解下述问

10、题：用原始用原始 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 令令。解得解得2

11、1 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解得解得。所以极小点为所以极小点为T

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

14、 ,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)(法法求求解解下下述述最最优优化化问问题题用用

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

16、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()

17、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,

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

19、假设设初初始始的的 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,(