第二次一维最优化

一维最优化2.黄金分割法3.进退法4.抛物线搜索法5.三次插值法1.一维最优化问题一.一维最优化问题下降迭代算法中最优步长的确定)(min)(kkkkkdxfdxf.kxkd.k一维最优化问题：)(minxfRxts..极值点的必要条件：0)('xf二.黄金分割法（0.618法）1.单峰函数定义：设)(xf是区间],[ba上的一元函数，x是)(xf在],[ba上的极小点，且对任意的,,],[,2121xxbaxx有（a）当xx2时，;)()(21xfxf（b）当时，xx1.)()(21xfxfa..b.x..1x2x则称是单峰函数。)(xf..性质：通过计算区间],[ba内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理设是区间],[ba上的一元函数，x是)(xf在],[ba上的极小点。任取点)(xf,],[badc则有（1）如果)()(dfcf，则;],[bcx（2）如果,)()(dfcf则。],[daxa..b.x..cd2.黄金分割法思想通过选取试探点使包含极小点的区间不断缩短，直到区间长度小到一定程度，此时区间上各点的函数值均接近极小值。下面推导黄金分割法的计算公式。上单峰，在设],[)(11baxf].,[11bax极小点假设进行次迭代前第k],,[kkbax],,[,kkkkba取规定.kk,)()(kkff和计算分两种情况：,)()(.1kkff若,1kka则令;1kkbb,)()(.2kkff若,1kkaa则令.1kkb？与如何确定kkkkkkab.1比率相同，即每次迭代区间长度缩短.2)0()(11kkkkabab)1()2(）可得：）与（由式（21)())(1(kkkkkkkkabaaba)3()4(件：要求其满足以下两个条kakbkku？取值的确定通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,)()()1(kkuffk次迭代时有设在第则有。],[],[11kkkkuaba,,111kkuk次迭代时选取在第）有则由（4)(1111kkkkabau)(2kkkaba。不必重新计算因此则，如果令112,1kkkuu618.021512。次迭代时有若在第)()()2(kkuffk同理可得。算法步骤：0.],,[.111精度要求给定初始区间ba.1:k令),(382.01111aba令),(618.01111aba).()(11ff与并计算,.2kkab若停止，.2kkabx且否则，；时，转当3)()(kkff.4)()(时，转当kkff,.31kka令,1kkbb,1kk),(618.01111kkkkaba),(1kf计算。转2,.41kkaa令,1kkb,1kk),(382.01111kkkkaba),(1kf计算,1:kk令。转2,1:kk令黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的。倍k)215(其它的试探点算法：Fibonacci算法。三．进退法思想从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤,.1)0(Rx给定初始点,00h初始步长,0hh令,)0()1(xx),()1(xf计算.0k并令,.2)1()4(hxx令),()4(xf计算.1:kk令),()(.3)1()4(xfxf若，则转45.否则，转,.4)1()2(xx令,)4()1(xx),()()1()2(xfxf),()()4()1(xfxf.2,2:转令hh如何确定包含极小点的一个区间？,1.5k若；则转6.7否则，转,:.6hh令,)4()2(xx),()()4()2(xfxf.2转,.7)2((3)xx令,)1()2(xx,)4()1(xx停止计算。例：)0(x)1(xhxx)1()4()2(x)1(x)4(x)3(x)2(x)1(x)0(x)1(x)4(xhh:)1(x)2(x)4(x)3(x)2(x)1(x。即为包含极小点的区间或区间],[],[)1()3()3()1(xxxx],[)1()3(xx：极小点区间],[)3()1(xx极小点区间：四.抛物线插值思想在极小点附近，用二次三项式),()(xfx逼近目标函数处有相同的函数值，在三点与令)3()2()1()()(xxxxfx并假设).()(),()()3()2()2()1(xfxfxfxf)1(x)2(x)3(x)(xf)(xx*x,)(2cxbxax设)()()1(2)1()1()1(xfcxbxax)()()2(2)2()2()2(xfcxbxax)()()3(2)3()3()3(xfcxbxax.)(cbx和的系数近函数解上述方程组，可得逼的极小点，再求函数)(x令cxbx2)(,0解得cbx2如何计算函数?)(x。的极小点的估计值作为以)(xfx])()()()()()([2)()()()()()()3()2()1()2()1()3()1()3()2()3()2()1()2()1()3()1()3()2(222222xfxxxfxxxfxxxfxxxfxxxfxx令抛物线插值算法步骤：,],[)1()3()1(xx给定初始区间).()(),()()3()2()2()1(xfxfxfxf设。给定精度。。令)1()0(1:xxk。令。设3,2,1,)()()()2()()(2ixfxcxbxaxii解出。的极小点解出。系数cbxxcbak2)(,,)(及其的函数值最小的三个点中选择和从)(,,)3()()3()2()1(xfxxxxk。）转（。令。重新标记为左、右两点，21:,,)3()2()1(kkxxx）。否则转（，则算法停止若3,|)()(|)1()(kkxfxf五.三次插值法思路：,0)()()()1()2()1()2()1(xfxxxxxf且有，的函数值、在点已知利用这两点的函数值的极小点。内存在（则区间)(),.0)()2()1()2(xfxxxf在这两点有相同的函使它与项式和导数构造一个三次多)(,)(xfx的极小点。的极小点近似并用逼近用数值和导数，)()(,)()(xfxxfx)1(x)2(x)(xf)(x*xx设)1()()()()()1(2)1(3)1(dxxcxxbxxax令)()()()()()()()()2()2()1()1()2()2()1()1(xfxxfxxfxxfx则有)()(2)(3)()()()()()()2()1()2(2)1()2()1()2()1()2(2)1()2(3)1()2()1(xfcxxbxxaxfcxfdxxcxxbxxaxfd)2(。从而确定函数，的值求解方程组得出系数)(,,,xdcba的方法：确定函数)(x求解满足0)(0)(xx的极小点令0)(2)(3)()1(2)1(cxxbxxax)3(。bxxax2)(6)()1(而解方程（3），有两种情况：解得时，当0.1a)4(2)1(bcxx由（2）可知。)1()2()2()1(,0)(,0)(xxxfxfc。所以0b的极小点。是即因此)(,02)(xxbx。x解得时，当0.2aaacbbxx332)1()5(acbbaacbbax322336)(22此时有式中应取则在为使)5(,0)(xaacbbxx332)1(acbbc32)6(式可知由时，而当)6(0a式所以，)6(2)1(bcxx一表达式。两种情况下极小点的统、是21极小点的计算公式：令)7()]()([3)1()2()1()2(xxxfxfs)8()()()2()1(xfxfst)9()()()2()1(22xfxftw)10()2)()()(1)(()1()2()2()1()2()1(wxfxfwtxfxxxx则有算法步骤：要求计算给定初始点,)(,)(,)(,)(,,.1)2()1()2()1()2()1(xfxfxfxfxx。满足条件：0)(,0)(,)2()1()1()2(xfxfxx。给定允许误差0,0。和、、计算、、、按照公式xwts)10()9()8()7(.2。否则，转；则停止计算，得到点，若4||.3)1()2(xxx。停止计算，得到点，若。计算xxfxfxf|)(|)(,)(.4。转。则令，若2)()(,)()(,0)()1()1()1(xfxfxfxfxxxf。转。则令，若2)()(,)()(,0)()2()2()2(xfxfxfxfxxxf述问题：用三次插值算法求解下例20..13)(min3xtsxxxf。则有取初始点解：2,0)2()1(xx,3)(,1)(,2)2()1()1()2(xfxfxx。9)(,3)()2()1(xfxf得由,33)(2xxf所以,3)]()([3)1()2()1()2(xxxfxfs,3)()()2()1(xfxfst6)()()2()1(22xfxftw。6w。则1)62396391(20x是极小点。，所以而10)(xxf其它插值算法：有理插值。收敛速度：三次插值算法的收敛阶为2。