技术数值分析最优化方法lecture07unconstrained optimization continued

1、1第七讲第七讲 无约束无约束 ( (多维多维) )最优化最优化n 梯度法（最速下降法）梯度法（最速下降法）n 牛顿法与拟牛顿法牛顿法与拟牛顿法n 变尺度法变尺度法(DFP(DFP法法) )n 共轭梯度法共轭梯度法n 模式搜索法模式搜索法n PowellPowell法法n 单纯形加速法单纯形加速法n 最小二乘法最小二乘法2;)(kkxfd 搜索方向。步长)(min)(:kkkkkdxfdxf )(),(,:21kkkkkkkkxfGxfggGdG 其中可逆时当搜索方向2. 2. 牛顿法牛顿法。步长1: 。步长)(min)(:kkkkkdxfdxf 3. 3. 拟牛顿法拟牛顿法( (变尺度法变尺度

2、法) )1、梯度法（最速下降法）：、梯度法（最速下降法）：多变量无约束优化间接法; )(:kkkxfHd 搜索方向3。步长)(min)(:kkkkkdxfdxf 3. 3. 拟牛顿法拟牛顿法( (变尺度法变尺度法) )kkTkkTkkkkTkkTkkkgHgHggHgxxxHH 1,kkkkkkxxxggg 11其其中中4. 特殊拟牛顿法特殊拟牛顿法1DFP算法：算法：5. 特殊拟牛顿法特殊拟牛顿法2BFGS算法：算法：; )(:kkkxfHd 搜索方向.,kkkkkkkTkkkTkkkTkkTkkTkkkTkkkkkgggxxxgxgHggxHgxxgHxxHH 1111 多变量无约束优化间

3、接法46. 6. 共轭梯度法共轭梯度法1 1 共轭梯度法共轭梯度法eevesRFletcher ,:1)1(gd 搜索方向,)(1)1(kkkkdgd ,)1()1()1(11AdddgTT 其中)()(1)(kTkkTkkdAdgAd 。）共轭梯度法共轭梯度法PRP()(11kTkkkTkkggggg 7. 7. 共轭梯度法共轭梯度法2 2 ）。）。共轭梯度法共轭梯度法PRP(多变量无约束优化间接法5无约束最优化问题的直接方法无约束最优化问题的直接方法一、一、 模式搜索法模式搜索法二、二、 Powell 算法算法三、三、 单纯形替换法单纯形替换法:无约束最优化问题; )(minxf直接方法：

4、算函数值的方法。不用计算导数，只需计67.1 模式搜索法模式搜索法年）年）方法，方法，（1961JeevesHooke 基本思想： 1.向向交交替替实实施施两两种种搜搜索索：轴轴算算法法从从初初始始基基点点开开始始，个个坐坐标标轴轴的的方方向向进进行行，搜搜索索依依次次沿沿搜搜索索和和模模式式搜搜索索。轴轴向向n。模模式式搜搜索索则则利利于于函函数数值值下下降降的的方方向向用用来来确确定定新新的的基基点点和和有有数数值值下下降降更更快快。线线方方向向进进行行，试试图图使使函函沿沿着着相相邻邻两两个个基基点点的的连连算法分析. 2; )(minxf求解问题求解问题个个坐坐标标轴轴方方向向。表表示

5、示令令nnjeTj,2,1,)0,0,1,0,0( 作作为为第第一一个个基基点点。任任取取初初始始点点，加加速速因因子子给给定定初初始始步步长长1x 个基点。个基点。表示第表示第以下用以下用jxj步长加速法步长加速法7方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中，iieiy的出发点。轴向搜索：。令令11xy O1e2e)1()1(yx 方向搜索：方向搜索：沿沿1e，则令，则令如果如果)()(111yfeyf ;112eyy ，否则，如果否则，如果)()(111yfeyf ;112eyy 则令则令。令令否则，否则，12yy )2(y，进行搜索得到进行搜索得到出发，仿上沿出发，仿上沿再从再从32

6、2yey)3(y8O1e2e)1()1(yx )2(y)3(y。到点到点依次进行搜索，直到得依次进行搜索，直到得1 ny)(一一轮轮轴轴向向搜搜索索结结束束。模式搜索：, )()(11xfyfn 如果如果。则令则令12 nyx方方向向可可能能有有利利于于函函数数12xx 12xx 值下降，因此下一步沿值下降，因此下一步沿方方向向进进行行模模式式搜搜索索。即令即令。)(1221xxxy )2(x )1(y为为起起点点进进行行新新的的，仍仍以以则则缩缩小小步步长长如如果果111, )()(xxfyfn 轴向搜索。轴向搜索。否否则则，进进行行模模式式搜搜索索。9有效？如何判断模式搜索是否。搜索，所得

7、的点仍记为搜索，所得的点仍记为为起点进行下一轮轴向为起点进行下一轮轴向以以11 nyy，令令表表明明此此次次模模式式搜搜索索成成功功如如果果, )()(21xfyfn 。13 nyx仿仿上上继继续续进进行行迭迭代代。表表明明此此次次如如果果, )()(21xfyfn 进进行行下下一一轮轮轴轴向向搜搜索索。，点点模模式式搜搜索索失失败败，返返回回基基2xO1e2e)1()1(yx )2(y)3(y)2(x )1(y)2(y)3(y 10 x1x2x3x4x5x6x11yesno1yes2NoyesNo模式搜索法框图：. 3)( ,0, )0(xffxyx 计算计算初始初始 1),()0(1 iy

8、ff)( )(2)()1()(iiiiyffeyy 计算计算 ?12ff 21ff ?ni 1 ii)1()( iiyy?12ff )( )()(2)()1()(iiiiyffeyy 计算计算 121NoyesNoYesYesNo2停；停；x 为解为解?1ff ?)(xyn ? )(, )(,)0()(xffxxxyyn xy )0(13模式搜索法步骤：. 3，缩缩减减率率，加加速速因因子子初初始始步步长长给给定定初初始始点点1,)1(1 nRx。精度精度0, )1,0( 。令令1,1,11 jkxy轴向搜索：轴向搜索：)2(）；）；（转转则令则令如果如果3, )()(1jjjjjjeyyyf

9、eyf ）；）；（转转则令则令如果如果3, )()(1jjjjjjeyyyfeyf 。否则，令否则，令jjyy 1。转转则令则令，若若)2(,1:)3( jjnj。否则，转否则，转；转转如果如果)5()4(, )()(1knxfyf 。令令模式搜索：模式搜索：)(,)4(11111kkknkxxxyyx ）。）。转（转（令令2,1,1: jkk；停止，得到点停止，得到点如果如果)(,)5(kx ,: 否则，令否则，令。kkkxxxy 11,）。）。转（转（令令2,1,1: jkk14(1) 步长加速法的收敛速度是线性的，且如果目标函数可微，则可收敛到平稳点。(2) 由于步长加速法不使用导数，故

10、可应用于任何形式的目标函数，应用范围极广。(3) 在进行坐标轮换试探时，如果不采用固定步长（亦称离散步长）而使用一维搜索技术求目标函数在坐标方向的极小点，则可加速迭代速度。4. 步长加速法性质与评价15, )(125. 2)(222yfeyf , )(125. 1)(222yfeyf 。Teyy)75. 0,75. 0(223 , )()(13xfyf 。令令32yx 。取加速方向Txxd).,.(250250121 模式搜索：。Tdxy).,.(5050121 :解轮迭代：第1。则则令令2)(,)1,1(111 yfxyT, )(5625. 2)(111yfeyf , )(5625. 1)(

11、111yfeyf 。Teyy)1,75. 0(112 用模式搜索法求解问题例 . 1。2221xxxf )(min,.,),(1250111 加速因子，初始步长取初始点Tx缩减。率20. 。轮迭代：第2167.2 Powell 方法方法基本思想：. 1调调整整搜搜索索方方向向三三个个基基本本搜搜索索、加加速速搜搜索索和和方方法法主主要要由由 Powell个个搜搜索索方方向向的的括括从从基基点点出出发发沿沿着着已已知知部部分分组组成成。基基本本搜搜索索包包n个个新新基基点点。进进行行一一维维搜搜索索，确确定定一一的的两两加加速速搜搜索索是是指指沿沿着着相相邻邻降更快。降更快。一维搜索，使函数值下

12、一维搜索，使函数值下个基点的连线方向进行个基点的连线方向进行最后用基点最后用基点新新的的搜搜索索方方向向组组，个个搜搜索索方方向向之之一一，构构成成连连线线方方向向代代替替已已知知的的 n进进行行下下一一轮轮迭迭代代。172、原始、原始 Powell 法步骤：法步骤：个个线线性性无无关关的的方方向向：给给定定初初始始点点nx ,)1(0。),1()2,1()1,1(,nddd。，令，令允许误差允许误差10 k 出出发发，依依次次沿沿方方向向从从令令)0,(1)0,(,)2(kkkxxx ),()2,()1,(,nkkkddd进进行行搜搜索索， 即令即令 )(min)(:),()1,(),()1

13、,(),()1,(),(jkjkjkjjkjjkjjkjkdxfdxfdxx 得到点得到点。),()2,()1,(,nkkkxxx进进行行一一维维出出发发沿沿从从令令)1,(),()0,(),()1,(, nknkknknkdxxxd。搜搜索索得得到到点点kx否则，令否则，令，停止，得到点，停止，得到点若若;|)3(1kkkxxx 。njddjkjk,2,1,)1,(),1( ）。）。返回（返回（令令2,1: kk18. 2例方法求解下述问题：用原始 Powell21221)1()()(min xxxxf。初初始始搜搜索索方方向向为为初初始始点点为为TTTddx)1,0(,)0,1(,)1,2

14、()2,1()1 ,1(0 解： 第一轮迭代：。令令0)0, 1(xx 作作一一维维搜搜索索，即即求求解解出出发发沿沿着着方方向向从从)1 ,1()0,1(dx. )(min)1 , 1()0, 1(dxf TTTdx)1 ,2()0,1()1 ,2()1 , 1()0, 1( ,)1()3()()(22)1 , 1()0, 1( dxf记记, 0)1(2)3(2 dd令。解得解得21 。Tdxx)1 ,0()1 , 1()0, 1()1 , 1( 0 x)1 , 1(x1x2xo19作作一一维维搜搜索索，即即求求解解出出发发，沿沿着着方方向向再再从从)2,1()1 ,1(dx. )(min)

15、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 第二轮搜索：,)132,134(1)0,2(Txx 初始点初始点)3, 1(3)2, 1(1dxx 所以所以:搜索方向为。TTdddd)1,2(,)1 ,0()3, 1()2,2()2, 1()1 ,2( 。T)132,134( 0 x)1 , 1(x1x2x)2, 1(xo1x20求解。)(min)1 ,2()0,2(dxf 。所以所以解得解

16、得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 0 x)1 , 1(x1x2x)2, 1(xo1x)1 ,2(x)2,2(x2x21定理对对称称正正定定矩矩阵阵。阶阶是是，其其中中设设nAcxbAxxxfTT 2

17、1)(作作一一维维搜搜索索得得极极小小出出发发沿沿方方向向。从从和和点点任任意意取取定定方方向向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( 搜搜索索得得极极小小点点沿沿方方向向搜搜索索得得到到极极小小点点沿沿方

18、方向向)2,2()0,2(1)3, 1(,dxxd ,)2,2(x共轭。共轭。和方向和方向所以由定理可知方向所以由定理可知方向)2,2()0,2()2,2()3,2(dxxd 的的，因因此此必必为为极极小小点点。是是沿沿共共轭轭方方向向搜搜索索得得到到2x22定定理理对对称称正正定定矩矩阵阵。阶阶是是，其其中中设设nAcxbAxxxfTT 21)(法法求求解解下下述述最最优优化化问问题题用用原原始始 Powell。)(minxf下下一一轮轮所所确确定定的的轮轮，且且每每一一轮轮迭迭代代后后为为若若迭迭代代已已进进行行了了)(nmm 线线性性无无关关，则则各各轮轮迭迭代代个个搜搜索索方方向向前前

19、)(,),()2,()1 ,(mkdddnnkkk 共共轭轭的的向向量量组组。成成所所产产生生的的加加速速方方向向必必构构A注注法法。算算法法是是一一种种共共轭轭方方向向算算原原始始 Powell. 1个个搜搜索索方方向向线线性性无无关关。的的前前算算法法不不能能保保证证各各轮轮迭迭代代原原始始nPowell. 223. 3例方法求解下述问题：方法求解下述问题：用原始用原始 Powell,)(min2221xxxf 。初初始始搜搜索索方方向向为为初初始始点点为为TTTddx)1,0(,)1,1(,)1,1()2,1()1 ,1(0 解：第一轮迭代：第一轮迭代：。令令0)0, 1(xx . )(

20、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( 24. )(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( ，到到的的线线性性相相

21、关关，以以下下迭迭代代得得和和)2()0,1()2,2()1 ,2( kxddTk。不不能能得得到到最最优优解解Tx)0,0(* 。，所以，所以解得解得Tdxx)0,1(1)2, 1(2)1 , 1()2, 1(2 。令方向令方向Txxd)1,0()0, 1()2, 1()3, 1( 25个搜索方向线性无关？个搜索方向线性无关？如何确保各轮迭代的前如何确保各轮迭代的前问题：问题：n)0,(),()1,(knknkxxd 分析：)(1)0,(),()1,()(knknnkxdx )0,(),()2,(2)1 ,(1)0,(knknkkkxdddx ),()2,(2)1 ,(1nknkkddd 因

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

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

24、skskkknksdddddxx kknksxx )0,(),(| 28方法：方法：改进的改进的Powell个个线线性性无无关关的的方方向向：给给定定初初始始点点nx ,)1(0。njedjj,1,),0( 。，令，令允许误差允许误差1,100 k 。令令1)0,()2( kkxx )(min)(:., 2 , 1,),1()1,(),1()1,(),1()1,(),(jkjkjkjjkjjkjjkjkdxfdxfnjdxx 即即个方向进行一维搜索，个方向进行一维搜索，依次沿依次沿 n令令。令令)0,(),()0,(),()1, 1()3(knkknknkxxxxd )(min)(:)1,1(

25、),()1,1(1),(1)1,1(1),(nknknknnknnknnkkdxfdxfdxx 29）。否否则则转转（算算法法结结束束，令令如如果果5;,)4(*1kkkxxxx , 1:,1,)5(0),0( kxxniednknii令令。则令则令，若若）。）。转（转（2。使得使得确定确定，若若inissnk 1max,)0,(),( kknksxx如果如果。则则niddikik,1,), 1(),( ）。）。转（转（令令2,1 kk；则令则令如果如果1,1,), 1(),()0,(),( siddxxikikkknks 。nsiddddikiknksk,1,;)1, 1(),()1, 1(

26、),( ）。）。转（转（令令2,1:,1)0,(),( kkxxkknksk 301.单纯形加速法单纯形加速法: Spendley、Hext 和和Himsworth 于于1962年提出年提出; Nelder 和和Mead 1965年改进年改进2. 问题问题:)(minxfnRx 上上连连续续函函数数是是nRxf)()()(nRCxf 即即7.3 单纯形加速单纯形加速替换法替换法复形法复形法单纯形加速法是一种不使用导数的求解无约束极小化问题的直接搜索方法.31集集合合迭迭代代的的思思想想。(1)为为单单纯纯形形这这里里),i(SSSSSikk21110 3.算法思想算法思想下下降降迭迭代代的的思

27、思想想。(2)降降。中中顶顶点点的的目目标标函函数数值值下下使使iS324. 单纯形概念单纯形概念三角形三角形:2R四面体四面体:3R线段线段:1R0V1V0V0V1V1V2V2V3V（1 1）例）例33,10nnRVVV 设,),2,1(0线性无关如果njVVj 即记为构成的单纯形称为由的凸组合则, ,101010nnnVVVSVVVVVV ,10nVVVS 为为该该单单纯纯形形的的顶顶点点。称称nV,V,V10（2 2）单纯形的定义）单纯形的定义0,1,|00 jnjjnjjjVx 其中34纯形：，可按以下方式构造单和正数对于给定的点 0 x)()(2101210221210110100n

28、nnnneeeVVeVVeeVVeVVeVVeVVxV 5.如何构造单纯形如何构造单纯形?。构成一个单纯形则,10nVVVS .,21维空间中的基坐标为其中neeen35例则则,)1,0,23()0,0,1(21)1,0,1(101TTTeVV ,)1,21,23()0,1,0(21)1,0,23(212TTTeVV 。TTTeVV)23,21,23()1,0,0(21)1,21,23(323 。构构成成一一个个单单纯纯形形则则,3210VVVVS 01,0,1) ,12TV设（。366.单纯形加速法的几何解释单纯形加速法的几何解释。给给定定单单纯纯形形,10nVVVS , )(, )(, )

29、(max)(10nhVfVfVfVf 设。)(, )(, )(min)(10nlVfVfVfVf *x0V2V1VVrVeV劣点形心点反射点延伸点37延伸步：: )()(lrVfVf 如果。一般取延伸系数延伸点2:,: Ve，则令)(VVVVre :反射步。一般取，反射系数，反射点1: rV hiiVnV1令,),()(构成新的单纯形代替则用若heleVVVfVf 构成新的单纯形。代替否则用,hrVV)(hrVVVV 形心380V2V1VVrVcV。：收缩系数，一般取收缩点，则令有21:)()()()( crchriVVVVVVfVfVfhi:收缩步（情形一）收缩步（情形一）构成新的单纯形。代

30、替则用若,),()(hchcVVVfVf 390V2V1VVrVcV:收缩步（情形二）收缩步（情形二）。：收缩系数，一般取收缩点，则令，若21:)()()( chchrVVVVVVfVf构成新的单纯形。代替则用若,),()(hchcVVVfVf 。棱长减半步：,n),1, 0(i211nokliiVVVSVVV , )()(hcVfVf 如果40. 5)()(. 4)()(stepVfVfstepVfVflrlr则转，如果则转，如果 7.单纯形加速法的步骤单纯形加速法的步骤001100 :, ,).(k,V,VVSxStepno，精度构造初始单纯形给定初始点初始步 。，计算（准备步）nVVVf

31、VfVfVfStephiiinilinih/)(min)()(max)(. 200 )1:()().(3 一般取，反射系数，反射点反射步rhrVVVVVstep41)2,:,:()()().(4延伸步延伸点延伸步erheVVVVVVVVstep.7,:) )()()()(101（判断步）转则，如果stepVVVSVVVfVfVfVfnkehrele .stepV,V,VS,VV)V(f)V(f)V(f)V(fnkrhrele（判判断断步步）转转则则，如如果果7,:)(101 则使得如果存在收缩步),()(1).(5irVfVfhistep.stepV,V,VS,VVnkrh7,:101转转 )

32、21:()()()()(2)。：收缩系数，一般取收缩点，令则，有如果 crchriVVVVVVfVfVfhi42).(7,:)()(101判判断断步步转转则则，如如果果stepVVVSVVVfVfnkchrc . )(6)()(棱棱长长减减半半步步转转则则，如如果果stepVfVfrc 。则则，如如果果)()()(3)VVVVVfVfhchr ).(7,:)()(101判判断断步步转转则则，如如果果stepVVVSVVVfVfnkchrc . )(6)()(棱棱长长减减半半步步转转则则，如如果果stepVfVfrc 。判判断断步步转转减减半半步步)7( Step,n),1,0i (2).(61

33、1nokliiVVVSVVVstep 43 ,1).(70 nVVstepnii计计算算判判断断步步。得得到到则则算算法法结结束束，）（或或者者如如果果1 ,max0*01 nVVxVVVVniinijinii 。准准备备步步转转那那么么）（如如果果)(2 Step, 1:, ,max1101 kkVVVSVVVVnoknijinii 44例例: :用单纯形加速法解用单纯形加速法解2221)6()3(5min xx分别计算相应函数值：分别计算相应函数值：构成初始单纯形，构成初始单纯形，任取点任取点解解 65,74,53 321xxx2061)(321xxxfxx构构成成的的线线段段的的形形心心

34、，计计算算由由比比较较得得最最坏坏点点213,xxxxh ）和和相相应应函函数数值值的的反反射射点点（取取关关于于计计算算16 2/72/)75(2/)43( 030 xxx5)(62)66(6 )52/7(2/7 rrxfx，321),()()(xxxfxfxfrr代替代替所以以所以以因为因为 相相应应的的函函数数值值为为：新新的的单单纯纯形形，其其顶顶点点和和经经过过第第一一次次迭迭代代，得得到到5)6 , 2(6)7 , 4(1)()5 , 3(321TTTxxxfxx ）和和相相应应函函数数值值的的反反射射点点（取取关关于于计计算算12/112/52/)65(2/)23( 020 xx

35、x24)(41)72/11(2/11)42/5(2/5 rrxfx，chrxxfxf所所以以计计算算因因为为),()( 构构成成的的线线段段的的形形心心，计计算算由由比比较较得得最最坏坏点点312,xxxxh 8/3)(4/254/132/ )2/117(2/112/ )2/54(2/5 ccxfx，hchcxxxfxf替替换换所所以以以以因因为为),()( 相相应应的的函函数数值值为为：新新的的单单纯纯形形，其其顶顶点点和和经经过过第第二二次次迭迭代代，得得到到5)6 , 2(8/3)4/25, 4/13(1)()5 , 3(321TTTxxxfxx 46）和和相相应应函函数数值值的的反反射

36、射点点（取取关关于于计计算算18/458/252/)4/255(2/)4/133( 030 xxx8/67)(4/214/17)68/45(8/45)28/25(8/25 rrxfx，构构成成的的线线段段的的形形心心，计计算算由由比比较较得得最最坏坏点点213,xxxxh chrxxfxf所所以以计计算算因因为为),()( 128/127)(16/9316/412/ )8/456(8/452/ )8/252(8/25 ccxfx，hchcxxxfxf替替换换所所以以以以因因为为),()( 相相应应的的函函数数值值为为：新新的的单单纯纯形形，其其顶顶点点和和经经过过第第三三次次迭迭代代，得得到到

37、128/127)16/93,16/41(8/3)4/25, 4/13(1)()5 , 3(321TTTxxxfxx 47）和和相相应应函函数数值值的的反反射射点点（取取关关于于计计算算132/19332/932/)16/934/25(2/)16/414/13( 010 xxx128/167)(16/11316/45)532/193(32/193)332/93(32/93 rrxfx，构构成成的的线线段段的的形形心心，计计算算由由比比较较得得最最坏坏点点321,xxxxh chrxxfxf所所以以计计算算因因为为),()( hchcxxxfxf替替换换所所以以以以因因为为),()( 相相应应的的

38、函函数数值值为为：新新的的单单纯纯形形，其其顶顶点点和和经经过过第第四四次次迭迭代代，得得到到128/67)16/93,16/41(8/3)4/25, 4/13(2048/503)()64/353,64/189(321TTTxxxfxx 2048/503)(64/35364/1892/ )32/1935(32/1932/ )32/933(32/93 ccxfx，可以继续迭代，直到满度一定的精度48h例:用复形法解49hhhh50 (一)、线性最小二乘法 (二)、非线性最小二乘法 1. 改进的改进的Gauss-Newton法法 2. Levenberger-Marquart方法方法7.4 最小二

39、乘法最小二乘法51一、线性最小二乘法一、线性最小二乘法)()()(min: )(xfxfxSPT 满满足足）的的最最优优解解问问题题（*xPbAxxf )(这这里里mnnmRbRxRA ,bAAxATT 2bAx 1. 问题问题2. 性质性质52bbAxbAxAxxSTTTT 2)(证明：证明：022)( bAAxAxSTTxx* 22b)x(AbAx* )bAx(AAbAx*TT* 22222 AbAx* 时时取取到到最最小小值值. .可可见见，当当0 )(2*22*bAAxAAbAxTTT )*( )*( AbAxAbAxT 满满足足）的的最最优优解解问问题题（*xPbAAxATT 2.

40、性质性质53 程程组组试试用用最最小小二二乘乘法法求求此此方方给给定定方方程程组组,3412322212121xxxxxx的近似解。的近似解。,)44()12()322()(221221221 xxxxxxxF令令。则原问题化为则原问题化为)(minxFRx ，记记 313,41212221bxxxA。则则)()()(bAxbAxxFT 例解,24666412122422112 AAT54,24666412122422112 AAT。 1610313422112bAT。(1AATbAAAxTT1)(* 。 313416101811811819255二、非线性最小二乘法

41、二、非线性最小二乘法1.一般形式：2)()()()(minxfxfxfxST ;),.,()(),.,(),()(2121TnTmxxxxxfxfxfxf 其中：其中：线性最小二似非线性函数，再模仿思想：用线性函数来近乘法求解。56, )()()(kkkxxxAxfxf 所以所以。),.,2 , 1(),()()()(mixxxfxfxfkTkikii 则由泰勒公式可知，次的迭代点设已知第kxk。其中其中nmjkixxnmmnkxxfxf.xfxf.xfxAk )()(1111分析求解.25722)()()()(kkkkkkxfdAxxAxfxS 。其中：其中：kkxxd 法法可可得得问问题题

42、，由由线线性性最最小小二二乘乘对对于于)(minx 可逆时则有可逆时则有当当kTkAA则有则有记记, )(kkxAA , )( )(kkkTkkkxfdAxfdA )(min, )( )()(xxfdAxfdAxkkkTkkk 则可用则可用记记 题的极小点。问题的极小点近似原问)(kTkkkTkxfAdAA )1()()(1kTkkTkkxfAAAd )2(58 收敛阶至少是二阶的。收敛阶至少是二阶的。当当是收敛的是收敛的由迭代得到的由迭代得到的则：则：，充分接近充分接近）满足一定条件且）满足一定条件且（若若, 0*)()2(;)1(*0 xfxxxxfk3.改进的Gauss-Newton法：

43、)()(11kTkkTkkkkkxfAAAxdxx ，则有迭代公式，则有迭代公式令令kkkdxx 1, )()(2)()(2)(1 miTiixfxAxfxfxS又矩阵。矩阵。的的在点在点是是则则Hesse)(kkxxH ,2kTkkAAH 记记）式可改写为）式可改写为（ 1)(kkkxSdH )4()3(性质:2)()()()(xfxfxfxST )(kTkkkTkxfAdAA 59)(1kkkxSHd 即)5(所以)(11kkkkxSHxx )6(公式，公式，式称为式称为NewtonGauss )6(方向。方向。）式称为）式称为（NewtonGauss 5。令令)()()(2)(kTkkk

44、TkkxfAxfxAxSg 则由其正定性可知：则由其正定性可知：存在存在若若,)(1 kTkAA为下降方向kd0)(2)(1 kkTkTkkTkgAAgdxS。奇奇异异，则则解解不不出出否否则则，若若kkTkdAA。此时令此时令kkgd 60算法（共五步）算法（共五步）改进的改进的NewtonGauss 。精精度度给给定定初初始始点点0,:10 xStep。令令0: k;)(:2)(kjkikijAxxfaStep 计算：计算：。 mikjkikikjgxxfxfg1)()()( nArankxfAgnArankxfAAAdStepkTkkkTkkTkk)()()()()(:31如果如果如果如

45、果令令。其中其中令令)(min:,:41kkkkkkkdxfdxxStep 。转转否则否则算法结束算法结束则则若若2, 1: ,;, ,|)(|:51*StepkkxxxfAStepkkTk .)(;)(,),()(:1nmjiTmxfxAxfxfxf 已已知知61三、三、Levenberger-Marquart方法方法时时，迭迭代代无无法法继继续续！）接接近近于于（条条件件数数为为奇奇异异或或法法的的迭迭代代中中，当当1)()(NewtonGauss. 11BBxAxABT 迭迭代代继继续续！的的对对角角元元的的措措施施使使方方法法采采用用适适当当增增加加)()(ML.2xAxAT 方方程程

46、组组：方方法法求求解解如如下下满满足足当当前前的的迭迭代代点点ML, 0)(. 3 kkxSx过过大大！能能够够成成立立又又不不至至于于使使为为正正定定，且且中中不不断断调调整整使使是是一一个个正正数数，它它在在迭迭代代其其中中 )()()(:1kkkxSxSxC 。得得到到下下一一迭迭代代点点然然后后令令11 kkkxzxx(*)()()(:)()(kTkkkTkxfxAzxCzIxAxA 62!)( 3NewtonGauss0. 4敛敛速速度度的的增增加加，否否则则将将影影响响收收尽尽可可能能限限制制方方向向。因因而而充充分分大大时时便便接接近近负负梯梯度度偏偏移移，当当方方向向逐逐步步向

47、向负负梯梯度度表表明明方方向向的的增增大大，下下面面的的性性质质方方向向；随随着着就就是是，得得到到的的若若取取 XSzz ）的解，那么有：是方程组（，设*.z05 )()()()(1zyzxAxfyxAxfkkkk （：性质22).()(2kkxSzxS 适当大，总成立：只要性质 充分接近。与方向充分大时，方向：当性质)(3kxSz 63。并返回并返回：则令则令若若1Step),()(:2Step xSzxS放大。遇到困难时将缩小，迭代：一次成功迭代后将采用进退方法调整 . 6调整算法： . 7。的初值，控制终止常数，初始点给定和步长缩小因子子初始：给定步长放大因 xxf),(, 101 。

48、得得求解求解zxfxAzIxAxATT)()()()(:1Step 。否则返回否则返回则迭代终止，则迭代终止，）（若若令令1Step)(;,:3Step xfxAzxxT642221mindxCx beqxAeq 有约束线性最小二乘的标准形式为sub.to 其中：C、A、Aeq为矩阵；d、b、beq、lb、ub、x是向量。在MATLAB5.x中，约束线性最小二乘用函数conls求解。1 约束线性最小二乘bxA buxbl 65bxAbeqxAeqbuxbl函数 lsqlin 格式 x = lsqlin(C,d,A,b) %求在约束条件下，方程Cx = d的最小二乘解x。x = lsqlin(C

49、,d,A,b,Aeq,beq) %Aeq、beq满足等式约束若没有不等式约束，则设A= ，b= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub) %lb、ub满足若没有等式约束，则Aeq= ，beq= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0) % x0为初始解向量，若x没有界，则lb= ，ub= 。x = lsqlin(C,d,A,b,Aeq,beq,lb,ub,x0,options) % options为指定优化参数x,resnorm = lsqlin() % resnorm=norm(C*x-d)2，即2-范数。x,resnorm,re

50、sidual = lsqlin() %residual=C*x-d，即残差。x,resnorm,residual,exitflag = lsqlin() %exitflag为终止迭代的条件x,resnorm,residual,exitflag,output = lsqlin() % output表示输出优化信息x,resnorm,residual,exitflag,output,lambda = lsqlin() % lambda为解x的Lagrange乘子 66例例5-15 求解下面系统的最小二乘解求解下面系统的最小二乘解系统：系统：约束：约束：bxA buxbl 先输入系统系数和先输入系统

51、系数和x的上下界：的上下界：C = 0.9501 0.7620 0.6153 0.4057; 0.2311 0.4564 0.7919 0.9354; 0.6068 0.0185 0.9218 0.9169; 0.4859 0.8214 0.7382 0.4102; 0.8912 0.4447 0.1762 0.8936;d = 0.0578; 0.3528; 0.8131; 0.0098; 0.1388;A = 0.2027 0.2721 0.7467 0.4659; 0.1987 0.1988 0.4450 0.4186; 0.6037 0.0152 0.9318 0.8462;b = 0

52、.5251; 0.2026; 0.6721;lb = -0.1*ones(4,1);ub = 2*ones(4,1);然后调用最小二乘命令：然后调用最小二乘命令：x,resnorm,residual,exitflag,output,lambda = lsqlin(C,d,A,b, , ,lb,ub);dCx 67结果为：结果为：x = -0.1000 -0.1000 0.2152 0.3502resnorm = 0.1672residual = 0.0455 0.0764 -0.3562 0.1620 0.0784exitflag = 1 %说明解说明解x是收敛的是收敛的output = it

53、erations: 4 algorithm: medium-scale: active-set firstorderopt: cgiterations: lambda = lower: 4x1 double upper: 4x1 double eqlin: 0 x1 double ineqlin: 3x1 double通过通过lambda.ineqlin可查看非线性不等式约束是否有效。可查看非线性不等式约束是否有效。682 2 非线性最小二乘非线性最小二乘69buxbl函数 lsqnonlin格式 x = lsqnonlin(fun,x0) %x0为初始解向量；fun为f(x)i=1,2,m，

54、fun返回向量值F，而不是平方和值，平方和隐含在算法中，fun的定义与前面相同。x = lsqnonlin(fun,x0,lb,ub) %lb、ub定义x的下界和上界：x = lsqnonlin(fun,x0,lb,ub,options) %options为指定优化参数，若x没有界，则lb= ，ub= 。x,resnorm = lsqnonlin() % resnorm=sum(fun(x).2)，即解x处目标函数值。x,resnorm,residual = lsqnonlin() % residual=fun(x)，即解x处fun的值。x,resnorm,residual,exitflag

55、= lsqnonlin() %exitflag为终止迭代条件。x,resnorm,residual,exitflag,output = lsqnonlin() %output输出优化信息。x,resnorm,residual,exitflag,output,lambda = lsqnonlin() %lambda为Lagrage乘子。x,resnorm,residual,exitflag,output,lambda,jacobian =lsqnonlin() %fun在解x处的Jacobian矩阵。 70713 非负线性最小二乘7273 命令格式为命令格式为: x，fval，exitflag，output= fminunc(fun, x0 ，options)； 或或 x，fval，exitflag，output= fminsearch(fun, x0 ,options)；标准型为标准型为：min F(X)matlab解多元函数无约束优化问题解多元函数无约束优化问题fminsearchfminsearch是用单纯形法寻优是用单纯形法寻优. . fminuncfminunc的算法见以下几点说明：的算法见以下几点说明：使用使用fminuncfminunc和和