《优化设计2——一维优化及牛顿法解读》由会员分享，可在线阅读，更多相关《优化设计2——一维优化及牛顿法解读（82页珍藏版）》请在金锄头文库上搜索。
1、113.33.3一维优化问题一维优化问题优化问题的数值解法优化问题的数值解法：XX(k+1)(k+1)=X=X(k)(k)+(k)(k)SS(k)(k)FFXX(k)(k)+(k)(k)SS(k)(k)=min=minFFXX(k)(k)+(k)(k)SS(k)(k)从一个初始点从一个初始点XX(0)(0)出发，按一定规则确定一个出发，按一定规则确定一个搜索方向搜索方向SS(0)(0)然后在然后在SS(0)(0)上搜索到目标函数的极小值上搜索到目标函数的极小值XX(1)(1)；接着又以；接着又以XX(1)(1)作为下一个迭代的出发点，重复作为下一个迭代的出发点，重复以上过程，直到把目标函数达到
2、最优值以上过程，直到把目标函数达到最优值f(X)f(X)为止。为止。在此过程中求在此过程中求(k)(k)用到的方法叫一维搜索的优用到的方法叫一维搜索的优化方法。化方法。22333.3.13.3.1单峰区间单峰区间1.1.单峰区间单峰区间在单峰区间内，在极小点在单峰区间内，在极小点左左边，函数值随边，函数值随xx的的增加增加是严是严格格减小减小的；在极小点的；在极小点右右边，边，函数是严格函数是严格增大增大的。因此在的。因此在单峰区间内，函数值具有单峰区间内，函数值具有“高高低低高高”的形态，的形态，可利用这一特征来确定初始单峰区间。可利用这一特征来确定初始单峰区间。2.2.确定单峰区间的进退算
3、法确定单峰区间的进退算法一维搜索的各种方法的基本思想是一维搜索的各种方法的基本思想是“区间消去法区间消去法”，而区，而区间消去法的基本思想是：逐步缩小搜索的区间，直至最间消去法的基本思想是：逐步缩小搜索的区间，直至最小点存在的范围小于给定的误差范围为止。小点存在的范围小于给定的误差范围为止。44ll基本思路基本思路：对对单峰函数单峰函数f(x)f(x)任选一个初始点任选一个初始点xx11及初始步长及初始步长hh，通过，通过比较这两点函数值的大小，来决定第三点的位置，比较这比较这两点函数值的大小，来决定第三点的位置，比较这三点的函数值的大小，确定是否为三点的函数值的大小，确定是否为“高高低低高高
4、”的形的形态，依此确定向前或后退搜索。态，依此确定向前或后退搜索。55确定单峰区间的进退算法确定单峰区间的进退算法进退法：进退法：通过比较函数值大小来确定单峰区间的方法。通过比较函数值大小来确定单峰区间的方法。给定的初始点给定的初始点和步长和步长单峰区间：66ll进退步骤进退步骤:(1)(1)选定初始点选定初始点x1x1、初始步长、初始步长h(h0)h(h0)。计算函数值计算函数值ff11=f(x=f(x11)和和ff22=f(x=f(x11+h)+h)。比。比较较ff11和和ff22，可分三种情况：，可分三种情况：(a)(a)若若ff11ff22，则说明极小点则说明极小点xx必在必在xx11
5、的右方，应作前进运算，转的右方，应作前进运算，转(2)(2)(b)(b)若若ff11f22，将步长加倍，取下一个计算点为，将步长加倍，取下一个计算点为x=xx=x11+2h+2h，计算，计算f(xf(x11+2h)+2h)并并令令ff11=f(x=f(x11+h)f2=f(x+h)f2=f(x11+2h)+2h)。再比较。再比较ff11和和ff22：(a)(a)若若ff11f22，则应再作前进计算，步长加倍，取下一计算点为，则应再作前进计算，步长加倍，取下一计算点为x=xx=x11+4h+4h，并比较，并比较ff11=f(x=f(x11+2h)+2h)和和ff22=f(x=f(x11+4h)+
6、4h)的函数值。如此反复的函数值。如此反复循环，直到相邻三点的函数值形成循环，直到相邻三点的函数值形成“高高低低高高”形态为止形态为止ll若若ff11=f=f22，则初始单峰区间为，则初始单峰区间为xx11+hx+hx11+2h+2h77(3)(3)当当ff11f11，将步长加倍，继续后退。再算出下一个点的，将步长加倍，继续后退。再算出下一个点的函数值函数值f(xf(x11-2h)-2h)，。如此反复循环，直到相邻三点的。如此反复循环，直到相邻三点的函数值出现函数值出现“高高低低高高”形态为止；形态为止；(b)(b)若若ff22=f=f11，则初始单峰区间为，则初始单峰区间为xx11-hx-h
7、x11。可自己画出进退法的程序框图可自己画出进退法的程序框图。88区间缩小的序列消去原理：区间缩小的序列消去原理：是通过对区间分割点函数值的计算和比较，将初始区间是通过对区间分割点函数值的计算和比较，将初始区间逐次进行缩小，当区间缩小到给定的精度要求时，可逐次进行缩小，当区间缩小到给定的精度要求时，可求得一维极小点的近似解。求得一维极小点的近似解。若若，则极小点必在区间，则极小点必在区间若若，则极小点在，则极小点在若若，则归入上面任何一种情况。，则归入上面任何一种情况。区间消去法区间消去法ab99黄金分割法：黄金分割：将一线段分成两段，使得整段长度与较长段的比值等于较长段与较短段的比值解得3.
8、3.23.3.2黄金分割法黄金分割法1010两个原则：两个原则：等比收缩原则等比收缩原则：即区间每一次的缩短率：即区间每一次的缩短率不变；不变；对称取点原则对称取点原则：即所插入两点在区间中位置对称。：即所插入两点在区间中位置对称。11110.6180.618法算法步骤为：法算法步骤为：(1)(1)确定确定f(x)f(x)的初始搜索区间的初始搜索区间aabb及终止限及终止限。(2)(2)计算计算xx22=a+0.618(b-a)f=a+0.618(b-a)f22=f(x=f(x22)(3)(3)计算计算xx11=a+0.382(b-a)f=a+0.382(b-a)f11=f(x=f(x11)(
9、4)(4)若若|xx22-x-x11|f(x22)f(x22)0令令K=0.K=0.（22）计算计算f(Xf(X(k)(k).).（33）若若ff(X(X(k)(k)停止停止X=XX=X(k)(k)否则转（否则转（44）.（44）计算计算H(XH(X(k)(k)-1-1令令SS(k)(k)=-H=-H-1-1f(Xf(X(k)(k).).（55）求求(k)(k)使使ff(X(X(k)(k)+(k)(k)SS(k)(k)=min)=minff(X(X(k)(k)+(k)(k)SS(k)(k).).（66）令令XX(k+1)(k+1)=X=X(k)(k)+(k)(k)SS(k)(k)K=K+1K=
10、K+1转转(2)(2)ll牛顿法和阻尼牛顿法虽具有收敛快的优点，但它们最牛顿法和阻尼牛顿法虽具有收敛快的优点，但它们最大的缺点是每次迭代都要计算二阶导数矩阵大的缺点是每次迭代都要计算二阶导数矩阵HessianHessian矩阵矩阵及其逆阵及其逆阵HH-1-1，此计算量比较繁琐。此外，牛顿法还要求，此计算量比较繁琐。此外，牛顿法还要求H(X)H(X)正定，否则正定，否则H(X)H(X)为奇异阵，无法计算为奇异阵，无法计算HH-1-1所以对于多所以对于多变量复杂目标函数的优化问题，故此法不可用。变量复杂目标函数的优化问题，故此法不可用。53533.4.53.4.5变尺度法变尺度法优化迭代的一般公式
11、可以表达为优化迭代的一般公式可以表达为XX(k+1)(k+1)=X=X(k)(k)-(k)(k)AAkkff(X(X(k)(k)变尺度法：变尺度法：AAkk是需要构造的一个是需要构造的一个nnnn对称方阵对称方阵即尺度矩阵。即尺度矩阵。5454ll尺度矩阵尺度矩阵AA(k)(k)的构造，可从初始矩阵的构造，可从初始矩阵AA(k)(k)=E=E（单（单位矩阵）开始，它通过对公式位矩阵）开始，它通过对公式AA(k+1)(k+1)=A=A(k)(k)+A+A(k)(k)中的修正矩阵中的修正矩阵AA(k)(k)的不断修正，在迭代中逐步的不断修正，在迭代中逐步逼近于逼近于H(XH(X(K)(K)-1-1
12、。由于修正矩阵的不同，就构成。由于修正矩阵的不同，就构成了种种不同的变尺度法。了种种不同的变尺度法。5555llDFPDFP法中的修正矩阵法中的修正矩阵AA(k)(k)为为：式中：式中：gg(k)(k)=g=g(k+1)(k+1)-g-g(k)(k)=f(Xf(X(k+1)(k+1)-)-f(Xf(X(k)(k)XX(k)(k)=X=X(k+1)(k+1)-X-X(k)(k)另一种另一种变尺度法为变尺度法为BFGSBFGS，计算公式见书中表述。，计算公式见书中表述。5656例：例：用用DFPDFP法解法解minf(X)=60-10 xminf(X)=60-10 x11-4x-4x22+x+x1
13、122+x+x2222-x-x11xx22。初。初始点为始点为XX(0)(0)=(00)T=0.0001=(00)T=0.0001.解：解：（11）令）令K=0K=0（22）计算目标函数的梯度）计算目标函数的梯度f(Xf(X(0)(0)（33）搜索方向为）搜索方向为虽然此时搜索方向为负梯度方向。沿此方向进行一维搜虽然此时搜索方向为负梯度方向。沿此方向进行一维搜索，求得最优步长因子索，求得最优步长因子kk5757将将XX(1)(1)=X=X(0)(0)+SS(0)(0)代入目标函数得代入目标函数得f(Xf(X(1)(1)=60-10(10)=60-10(10)-4(4)-4(4)+(10)+(1
14、0)22+(4+(4)22-(10-(10)(4)(4)=60-116=60-116+76+7622=q(=q()为求极小值，将上式对为求极小值，将上式对求导，并令求导，并令qq()=0)=0，即，即dqddqd=-116+152=-116+152=0=0解得解得(0)(0)=0.7631=0.7631得得XX(1)(1)=X=X(0)(0)+(0)(0)SS(0)(0)=00=00TT+0.7631104+0.7631104TT=7.6313.052=7.6313.052TT（44）收敛性判别）收敛性判别5858(5(5）因此时）因此时K0，令，令k=1k=1。（）令（）令ii=1X=1Xi
15、-1i-1(k)(k)=XX(0)(0)。（33）一维搜索求在一维搜索求在eeii方向的最优步长方向的最优步长ii，使，使f(Xf(Xi-1i-1(k)(k)+ii(k)k)eeii)=minf(X)=minf(Xi-1i-1(k)(k)+e+eii)XXii(k)(k)=X=Xi-1i-1(k)(k)+ii(k)k)eeii（44）若若i=ni=n，则转（，则转（55）；否则，则）；否则，则ii=ii+1+1，转，转(3)(3)。（55）检验检验XXnn(k)(k)-X-X00(0)(0)？若满足收敛准则，停止迭代，若满足收敛准则，停止迭代，X=XX=Xnn(k)(k)；否则，令；否则，令XX(0)(0)=X=Xnn(k)(k)，k=k+1k=k+1，转，转(2)(2)。6666例：用坐标轮换法求例：用坐标轮换法求minf(X)=60-10 xminf(X)=60-10 x11-4x-4x22+x+x1122+x+x2222-x-x11xx22，取，取XX(0)(0)=00=00TT。ll解：其搜索过程如图解：其搜索过程如图：ll第一次迭代：第一次迭代：令令xx11=0=0，则，则f(xf(x22)=60-4x)=60-4x22+x+x2222对
