第二章 一维极小化方法

第二章一维极小化方法2.黄金分割法3.进退法4.抛物线搜索法5.牛顿法1.一维最优化问题一.一维优化问题本章讨论无约束条件的一维优化问题，即只有一个变量的函数，求其无约束条件下的极小点问题一维优化问题：)(minxfRxts..古典微分法的求解步骤如下a)求一阶导函数b)令一阶导函数为零，解得驻点c)根据驻点处的二阶导函数的符号，判断驻点是否为极小点一.一维优化问题古典微分法的局限性情况1：目标函数复杂，令导函数为零时得不到解析解（例2-1，2-2）情况2：目标函数写不出明显的表达式（例2-3）实际化工问题中，有许多属于以上两种情况，因此必须寻求其他方法进行求解，而借助于计算机进行的数值计算方法则能够完成这一任务一维问题的优化方法也是后面几章多维优化问题的基础二.黄金分割法（0.618法）黄金分割•把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。其比值是[5^(1/2)-1]/2，取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，因此称为黄金分割。•这是一个十分有趣的数字，通过简单的计算就可以发现：1/0.618=1.618(1-0.618)/0.618=0.618•这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。2.2黄金分割法（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α1βaμλb1.kkkk比率相同，即每次迭代区间长度缩短2.α/1β/α/1μαμ/αλα0)(α)aα(babkkkkkkkk1k1k即，另有：)1()2(）可得：）与（由式（21)aα(baμ)aβ(baλkkkkkkkk)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算法。2.3进退法如何确定包含极小点x*的一个区间，且区间较窄？思想从初选的一点出发，按一定的步长，试图确定出函数值呈现“高-低-高”的三点。这样就可以确定包含极小点x*的区间。沿着x增大方向搜索叫前进运算；若前进运算不成功，就退回来，再沿相反方向寻找，称为后退运算，故将该求解方法称为进退法。根据黄金分割法的求解策略，必须首先确定包含极小点x*的搜索区间。而大多数实际问题中，包含极小点x*的存在区间是未知的，或者区间太宽，使得计算效率降低。进退法的计算步骤,.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极小点区间：2.4抛物线插值思想在极小点附近，用二次三项式),()(xfx逼近目标函数处有相同的函数值，在三点与令)3()2()1()()(xxxxfx并假设(1)(2)(3)(2)()(),()().fxfxfxfx)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()(kkxfxf2.5Newton法)(minxfnRx上二次连续可微函数是nRxf)()()(2nRCxf即1.问题。近似，用二次函数产生为了由)()(1xfxQxxkk110kkxxxx))(()(21)()()()()(2kkTkkTkkxxxfxxxxxfxfxQxf2.算法思想)()(21)()(kkTkkTkkxxGxxxxgxf。其中)(,)(2kkTkkxfGxfg0)()(kkkxxGgxQ可逆，此时有若kGkkkkgGxx11。迭代公式这就是Newton令有比较迭代公式,1kkkdxx,1kkkgGd。1λ而0010:k,x.step，精度给定初始点)x(fG)x(fg.stepkkkk22和计算。可逆时，当kkkkkgGxxG113.算法步骤;xx停止，,ε||)f(x||若step3.1k*1k。3转step,1k:k令，否则牛顿法的几何解释例题5-2Minf(x)=x^4-x+1,初始点为3，收敛条件为：x的变化小于10-7；或f’(x)的绝对值小于0.001收敛速度快，为二阶收敛。（2）初始点的选取困难，甚至无法实施。。的存在性和计算量问题1(3)kG?(1)1)x(f)x(fkk4.算法特点5.存在缺点及修正初始点要选在初始点附近。?1)x(f)x(fkk如何使得问题一：)(min)(:1kkkkkkkkkkdtxfdtxftdtxxNewton法稍作修正：如果对kkkkkkdxgGxx11Newton法中，有在,0)()(011kkTkkkTkkTkkgGggGxfdxfG有时，当是下降方向。时，当kkdG0。则有：)()(1kkxfxf?32））和（如何克服缺点（问题二：)(Newton变尺度法算法二、拟)x(fGxxNewton.kkkk111迭代公式：先考虑)x(fHxxGHNewtonkkkkkk11，则有：替代正定矩阵用迭代公式中，如果我们在)x(fHtxx.kkkkk12考虑更一般的形式：xIxxxfdIHxfHtxxTkkkkkkkk度量为最速下降方向梯度法时,)()(1xGxxxfGdNewtonGHkTkkkkk111),(度量为最速下降方向法时法为变尺度算法。称Newton）收敛速度要快（的计算量要小）（质）迭代公式具有下降性（附加某些条件使得：如何对3213kkHH.0kH)HHH(HHHkkkkkk111kkGH？如何确定和如何保证kkkkH?GHH101kkGHNewton条件拟条件拟Newton则因为记),()(),()(2kkkkxfGxfgxfxg)xx(Gggkkkkk111这样我们想到,xx)gg(Gkkkkk1111。kkkkkxxggH111)(。此条件确定需满足的条件，并利用分析：kkHG1)()()()(111kTkkxxxfxfxf))(()(211121kKTkxxxfxx))(()()(1121kkkxxxfxgxg