优化设计2一维优化及牛顿法

2020/1/713.3一维优化问题优化问题的数值解法：X(k+1)=X(k)+λ(k)S(k)F[X(k)+λ(k)S(k)]=minF[X(k)+λ(k)S(k)]从一个初始点X(0)出发，按一定规则确定一个搜索方向S(0),然后在S(0)上搜索到目标函数的极小值X(1)；接着又以X(1),作为下一个迭代的出发点，重复以上过程，直到把目标函数达到最优值f(X*)为止。在此过程中求λ(k)用到的方法叫一维搜索的优化方法。2020/1/722020/1/733.3.1单峰区间1.单峰区间在单峰区间内，在极小点左边，函数值随x的增加是严格减小的；在极小点右边，函数是严格增大的。因此在单峰区间内，函数值具有“高——低——高”的形态，可利用这一特征来确定初始单峰区间。2.确定单峰区间的进退算法一维搜索的各种方法的基本思想是“区间消去法”，而区间消去法的基本思想是：逐步缩小搜索的区间，直至最小点存在的范围小于给定的误差范围为止。2020/1/74基本思路：对单峰函数f(x)任选一个初始点x1及初始步长h，通过比较这两点函数值的大小，来决定第三点的位置，比较这三点的函数值的大小，确定是否为“高——低——高”的形态，依此确定向前或后退搜索。2020/1/75确定单峰区间的进退算法进退法：通过比较函数值大小来确定单峰区间的方法。给定的初始点和步长1xh1x2x3x4xhh2h44x3x2x1xhh2h4单峰区间：42,xx'2x2020/1/76进退步骤:(1)选定初始点x1、初始步长h(h0)。计算函数值f1=f(x1)和f2=f(x1+h)。比较f1和f2，可分三种情况：(a)若f1f2，则说明极小点x*必在x1的右方，应作前进运算，转(2);(b)若f1f2，则说明x*必在x1的左方，应作后退运算，转（3）；(c)若f1=f2，则说明极小点x*必在点x1和x1+h点之间，已形成“高—低—高”形态，则初始单峰区间为[x1,x1+h]。(2)当f1f2，将步长加倍，取下一个计算点为x=x1+2h，计算f(x1+2h),并令f1=f(x1+h),f2=f(x1+2h)。再比较f1和f2：(a)若f1f2，则相邻三点的函数值形成“高—低—高”形态，得到初始单峰区间[x1,x1+2h];(b)若f1f2，则应再作前进计算，步长加倍，取下一计算点为x=x1+4h，并比较f1=f(x1+2h)和f2=f(x1+4h)的函数值。如此反复循环，直到相邻三点的函数值形成“高—低—高”形态为止;(c)若f1=f2，则初始单峰区间为[x1+h,x1+2h]2020/1/77(3)当f1f2，做后退运算。步长改为负值，即从x1出发，向反方向搜索。取下一个计算点为x=x1-h，计算f(x1-h)，并令f2=f(x1),f1=f(x1-h)。此时：若f2f1，则可确定初始单峰区间为[x1-h,x1+h]。(a)若f2f1，将步长加倍，继续后退。再算出下一个点的函数值f(x1-2h)，…。如此反复循环，直到相邻三点的函数值出现“高—低—高”形态为止；(b)若f2=f1，则初始单峰区间为[x1-h,x1]。可自己画出进退法的程序框图。2020/1/78区间缩小的序列消去原理：是通过对区间分割点函数值的计算和比较，将初始区间逐次进行缩小，当区间缩小到给定的精度要求时，可求得一维极小点的近似解。若，则极小点必在区间若，则极小点在若，则归入上面任何一种情况。)()(21xfxf],[2xa],[1bx)()(21xfxf)()(21xfxf)(xfxa1x2xb区间消去法ab2020/1/79黄金分割法：黄金分割：将一线段分成两段，使得整段长度与较长段的比值等于较长段与较短段的比值llll)1(解得0.618lll1lllll1l1ab1x2x)(382.01abax)(618.02abax3.3.2黄金分割法2020/1/710两个原则：等比收缩原则：即区间每一次的缩短率λ不变；对称取点原则：即所插入两点在区间中位置对称。2020/1/7110.618法算法步骤为：(1)确定f(x)的初始搜索区间[a,b]及终止限ε。(2)计算x2=a+0.618(b-a),f2=f(x2);(3)计算x1=a+0.382(b-a),f1=f(x1);(4)若|x2-x1|ε，则输出x*=(x2+x1)/2，停机；否则，转(5);(5)若f1≤f2;，则置b=x2，x2=x1，f2=f1,然后转（3）；否则置a=x1，x1=x2，f1=f2,，然后计算x2=a+0.618(b-a),f2=f(x2)，转（4）。0.618法的计算框图见下图：3.3.2黄金分割法2020/1/7122020/1/713黄金分割法的特点：（1）函数不必可微（2）第一次计算取两点，以后每次只需计算一点（3）收缩速度均匀。搜索次数)(abN618.0lnlnabN3.3.2黄金分割法2020/1/7142.4618.0lnln2N499576.018.46cos18.46sin)(499576.082.43cos82.43sin)(18.46)4050(618.040)(618.082.43)4050(382.040)(382.0)1(2)1(1)1(2)1(1xfxfabaxabax)()()1(2)1(1xfxf][)1(2b,x],[)1(1xa],[)1(1xa]50,[43.82][][]50,0[4],[(1)(1))1(1b,ab,xba例3-4：minf(x)=-sinxcosx，已知初始区间[a,b]＝[40°,50°]，区间缩小的相对精度ε2=0.13。（1）区间缩短次数（迭代次数）取N=5（2）第1轮迭代。计算黄金分割点，并对其函数值比较，缩短区间因，可淘汰或，这里淘汰，新区间为2020/1/7152020/1/7162020/1/7172020/1/7182020/1/7193.3.3二次插值法基本思想：多项式是逼近函数的一种常用工具。利用插值多项式进行一维搜索的基本思想是构造一个较低的插值多项式p(x)来近似地代替原目标函数f(x)，并以函数p(x)的极值点xp*（即p/(x)=0的根）作为目标函数f(x)的近似极值点。再通过比较各插值点和xp*的函数值及其所在位置，设法缩减搜索区间。从而最终逼近函数f(x)的极值点。如果p(x)是二次多项式，则称为二次插值法，若p(x)是三次多项式，则称为三次插值法。一般来说，三次插值的收敛性要好一些，但要计算函数导数；而二次插值计算较简单且具有一定的精度，故应用广泛。二次插值又称为抛物线法。2020/1/7201.设原目标函数f(x)的初始单峰搜索区间[x1,x3]已确定。函数f(x)在x1,x2,x3三点处函数值f1,f2,f3，其中x1x2x3，且f(x1)f(x2)f(x3)。即在三点处函数值为“高—低—高”形态，见图。作二次插值多项式p(x)=a+bx+cx2(A)2、p(x1)=a+bx1+cx12=f1p(x2)=a+bx2+cx22=f2(B)p(x3)=a+bx3+cx32=f33、对式（A）求导并令其等于零，得p/(x)=b+2cx=0由式（B）求待定系数a，b，c。得到多项式p(x)的极值点xp*。2020/1/721缩短区间：若f(x)本身为二次函数，则在理论上一次求值就可找到最优点，xp*即为所求。若f(x)为高于二次的函数或其它函数，则一般xp*不与原函数f(x)的极小点x*重合，如上图所示。为了求得满足一定精度要求的f(x)的极小点x*，可采用逐步缩小区间的办法。搜索区间的缩小可根据xp*和x2，f(xp*)和f(x2)的相互关系，分六种不同的情况。2020/1/7222020/1/7232020/1/7242020/1/725二次插值法计算步骤为：（1）确定初始搜索区间[x1,x3]，并给定ε。在初始区间[x1,x3]内选定一点x2，应满足条件：x1x2x3,f(x1)f(x2)f(x3)，即函数值具有“高—低—高”形态。（2）以x1,x2,x3三点构造新插值曲线p(x)，并求出xp*。（3）检验∣x2-xp*∣ε?若是，终止迭代，以x2,xp*中函数值较小的点作为最优点x*；若否，转下一步。（4）判别x2和xp*,f(x2)和f(xp*)的相互关系属于何种情况。舍去函数值较大的点x1（或x3），缩小区间，用x2,xp*,x3（或x1）作为新的三点（在这三点处函数值仍保持“高—低—高”形态），转向（2）重新构造新插值曲线p(x)。2020/1/726与0.618法相比较，二次插值法利用函数在已知几个近似点的值来确定新的近似点位置。而0.618法仅对几点函数值的大小进行比较，没有充分的利用函数本身的性质。因此，当函数f(x)具有较好的性质（如连续可微性）时，插值法往往比0.618法效果好，但它的程序要比0.618法稍复杂些。2020/1/7272020/1/7282020/1/7292020/1/7302020/1/7312020/1/7323.4多维无约束优化方法2020/1/7333.4多维无约束优化方法2020/1/7343.4.2最速下降法（梯度法）在求解无约束极值问题的解析法中，最速下降法简单易懂，迭代过程简单，对初始点的要求不严格。特别是，一些更有效的方法也常是在对它的改进后或在它的启发下而获得的。基本思想：在每个迭代点均沿着使目标函数值下降最快的方向前进，即负梯度方向，逐步走向最优点。搜索方向取为：S(k)=-▽F(X(k))或S(k)=-▽F(X(k))/||▽F(X(k))||则下一个迭代点为:X(k+1)=X(k)-λ(k)S(k)2020/1/735最速下降法以负梯度方向（函数值下降最快方向）作为搜索方向)()()()()(kkkXFXFS0x1x2x3x2020/1/7362020/1/737梯度法（最速下降法）的特点：1）初始点选取没有要求2）相邻两点的搜索方向正交缺点：迭代开始时下降幅度较大；在接近极小值点的时候，目标函数下降得很慢总结：负梯度方向仅是局部下降最快，不是最好的下降方向最优步长λ(k)的选取采用一维搜索：F(X(k)+λ(k)S(k))=minF(X(k)+λS(k))2020/1/738最速下降法的迭代步骤：(1)给定初始点X(0)及收敛精度ε,令k=0;(2)求目标函数的梯度向量▽F(X(k));(3)若||▽F(X(k)||≤ε，停止迭代；否则转下步。(4)用一维搜索方法确定步长λ(k)。(5)按X-λ▽f(X)求得下一个点，且k=k+1；转（2）。2020/1/7392020/1/7402020/1/7412020/1/7423.4.3共轭梯度法梯度法在迭代点远离极小点时，收敛速度较快，当迭代点接近极小点时，收敛速度变慢，其与共轭方向法结合可构成高效的混合算法。2020/1/743共轭梯度法第一步的搜索方向：负梯度方向第二步及以后各步的搜索方向为上一步搜索方向的共轭方向kgXFS)()0()0()(1)1(kkkSgS22111kkkTkkTkgggggg2020/1/744共轭方向（1）定义：为n阶正定矩阵，若两个矢量满足则称和对矩阵共轭。共轭矢量方向为共轭方向。（2）共轭方向与函数极小值点的关系考察正定二次函数A021ASST1S2SAAST1AST22S1SAXXXbaXFTT21)(2020/1/74511110)(SAXbSXFT12120)(SAXbSXFT两式相减，得012112ASSASXXTT1X2X*X1S1S2S)(1XF沿的共轭方向可搜索到正定二次函数极小值点。沿共轭方向的搜索具有二次收敛性1S2S2020/1/