最优化方法第七章无约束(多维)最优化-选讲

1第七章无约束(多维)最优化梯度法（最速下降法）牛顿法与拟牛顿法变尺度法(DFP法)共轭梯度法模式搜索法Powell法单纯形加速法最小二乘法2;)(kkxfd搜索方向。步长)(min)(:kkkkkdxfdxf)(),(,,:21kkkkkkkkxfGxfggGdG其中可逆时当搜索方向2.牛顿法。步长1:。步长)(min)(:kkkkkdxfdxf3.拟牛顿法(变尺度法)1、梯度法（最速下降法）：多变量无约束优化间接法;)(:kkkxfHd搜索方向33.拟牛顿法(变尺度法)kkTkkTkkkkTkkTkkkgHgHggHgxxxHH1,,kkkkkkxxxggg11其中4.特殊拟牛顿法1——DFP算法：5.特殊拟牛顿法2——BFGS算法：。步长)(min)(:kkkkkdxfdxf;)(:kkkxfHd搜索方向.,,kkkkkkkTkkkTkkkTkkTkkTkkkTkkkkkgggxxxgxgHggxHgxxgHxxHH1111多变量无约束优化间接法46.共轭梯度法1——共轭梯度法eevesRFletcher,:1)1(gd搜索方向,)(1)1(kkkkdgd,)1()1()1(11AdddgTT其中)()(1)(kTkkTkkdAdgAd。）共轭梯度法PRPgggggkTkkkTkk()(117.共轭梯度法2——）。共轭梯度法PRP(多变量无约束优化间接法5无约束最优化问题的直接方法一、模式搜索法二、Powell算法三、单纯形替换法:无约束最优化问题;)(minxf直接方法：算函数值的方法。不用计算导数，只需计6x1x2x3x7.7模式搜索法也称为步长加速法，或Hooke-Jeeves法，1961年轴向搜索模式搜索),(min21xxf对于77.7模式搜索法年）方法，（1961JeevesHooke基本思想：.1向交替实施两种搜索：轴算法从初始基点开始，个坐标轴的方向进行，搜索依次沿搜索和模式搜索。轴向n。模式搜索则利于函数值下降的方向用来确定新的基点和有数值下降更快。线方向进行，试图使函沿着相邻两个基点的连算法分析.2;)(minxf问题个坐标轴方向。表示令nnjeTj,,,,),,,,,,(2100100作为第一个基点。。任取初始点，加速因子给定初始步长1x个基点。表示第以下用jxj步长加速法8方向搜索时个坐标轴表示沿第用在每一轮轴向搜索中，iieiy的出发点。轴向搜索：。令11xyO1e2e)1()1(yx方向搜索：沿1e，则令如果)()(111yfeyf;112eyy，否则，如果)()(111yfeyf;112eyy则令。令否则，12yy)2(y，进行搜索得到出发，仿上沿再从322yey)3(y9O1e2e)1()1(yx)2(y)3(y。到点依次进行搜索，直到得1ny)(一轮轴向搜索结束。模式搜索：,)()(11xfyfn如果。则令12nyx方向可能有利于函数12xx12xx值下降，因此下一步沿方向进行模式搜索。即令。)(1221xxxy)2(x)1(y为起点进行新的，仍以则缩小步长如果111,)()(xxfyfn轴向搜索。否则，进行模式搜索。10有效？如何判断模式搜索是否。搜索，所得的点仍记为为起点进行下一轮轴向以11nyy，令表明此次模式搜索成功如果,)()(21xfyfn。13nyx仿上继续进行迭代。表明此次如果,)()(21xfyfn进行下一轮轴向搜索。，点模式搜索失败，返回基2xO1e2e)1()1(yx)2(y)3(y)2(x)1(y)2(y)3(y11x1x2x3x4x12初始x,α,y(0)=x,ε0计算f=f(x)f1=f(y(0)),i=1y(i)=y(i-1)+αe(i)计算f2=f(y(i))f2f1?f1=f2in?yesyes1Noi=i+12Noy(i)=y(i-1)+(-α)e(i)计算f2=f(y(i))f2f1?y(i)=y(i-1)yesNo模式搜索法框图：.3131f1f?Noyesy(0)=y(n)+α(y(n)–x)x=y(n),,f=f(x)y(n)=x?Noy(0)=xYesαε?YesNoα=0.1α2停；x为解14模式搜索法步骤：.3，缩减率，加速因子初始步长给定初始点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:jkk15(1)步长加速法的收敛速度是线性的，且如果目标函数可微，则可收敛到平稳点。(2)由于步长加速法不使用导数，故可应用于任何形式的目标函数，应用范围极广。(3)在进行坐标轮换试探时，如果不采用固定步长（亦称离散步长）而使用一维搜索技术求目标函数在坐标方向的极小点，则可加速迭代速度。4.步长加速法性质与评价16,)(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)(111yfeyf。Teyy)1,75.0(112用模式搜索法求解问题例.1。2221xxxf)(min,.,),(1250111加速因子，初始步长取初始点Tx缩减。率20.。轮迭代：第2177.8Powell方法基本思想：.1调整搜索方向三个基本搜索、加速搜索和方法主要由Powell个搜索方向的括从基点出发沿着已知部分组成。基本搜索包n个新基点。进行一维搜索，确定一的两加速搜索是指沿着相邻降更快。一维搜索，使函数值下个基点的连线方向进行最后用基点新的搜索方向组，个搜索方向之一，构成连线方向代替已知的n进行下一轮迭代。182、原始Powell法步骤：个线性无关的方向：给定初始点nx,)1(0。),1()2,1()1,1(,,,nddd。，令允许误差10k出发，依次沿方向从令)0,(1)0,(,)2(kkkxxx),()2,()1,(,,,nkkkddd进行搜索，即令)(min)(:),(),(),(),(),(),(),(jkjkjkjjkjjkjjkjkdxfdxfdxx111得到点。),()2,()1,(,,,nkkkxxx进行一维出发沿从令)1,(),()0,(),()1,(,nknkknknkdxxxd。搜索得到点kx否则，令，停止，得到点若;||||)3(1kkkxxx。njddjkjk,,2,1,)1,(),1(）。返回（令2,1:kk19.2例方法求解下述问题：用原始Powell212211)()()(minxxxxf。初始搜索方向为初始点为TTTddx),(,),(,),(),(),(10011221110解：第一轮迭代：。令001xx),(作一维搜索，即求解出发沿着方向从),(),(1101dx.)(min),(),(1101dxfTTTdx),(),(),(),(),(1201121101,)()()()(),(),(22110113dxft记,)()(01232dd令。解得21。Tdxx),(),(),(),(101101110x)1,1(x1x2xo20作一维搜索，即求解出发，沿着方向再从),(),(2111dx.)(min),(),(2111dxf，解得12。所以Tdxx),(),(),(),(002121121。令方向Txxd),(),(),(),(12012131求解.)(min),(),(3121dxf。解得1323第二轮搜索：,),(),(Txx132134102初始点),(),(313211dxx所以:搜索方向为。TTdddd),(,),(),(),(),(),(121031222112。T),(1321340x)1,1(x1x2x)2,1(xo1x21求解。)(min),(),(1202dxf。所以解得Tdxx),(,),(),(),(13413413612102121求解。)(min),(),(2212dxf。所以解得Tdxx),(,),(),(),(16934169881691822212222。令方向Txxd),(),(),(),(1696016936022232求解。)(min),(),(3222dxf,493解得。所以极小点为Tdxx),(),(),(113232220x)1,1(x1x2x)2,1(xo1x)1,2(x)2,2(x2x22定理对称正定矩阵。阶是，其中设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的，因此必为极小点。是沿共轭方向搜索得到2x23定理对称正定矩阵。阶是，其中设nAcxbAxxxfTT21)(法求解下述最优化问题用原始Powell。)(minxf下一轮所确定的轮，且每一轮迭代后为若迭代已进行了)(nmm线性无关，则各轮迭代个搜索方向前)(,,,),()2,()1,(mkdddnnkkk共轭的向量组。成所产生的加速方向必构A注法。算法是一种共轭方向算原始Powell.1个搜索方向线性无关。的前算法不能保证各轮迭代原始nPowell.224.3例方法求解下述问题：用原始Powell,)(min2221xxxf。初始搜索方向为初始点为TTTddx),(,),(,),(),(),(10111121110解：第一轮迭代：。令001xx),(.)(min),(),(1101dxf求解。，所以解得Tdxx),(),(),(),(11011101111.)(min),(),(2111dxf求解。，所以解得Tdxx),(),(),(),(01121211212。令方向Txxd),(),(),(),(1001213125.)(min),(),(3121dxf求解。，所以解得Tdxx),(),(),(0103132113