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

2023/2/213.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)用到的方法叫一维搜索的优化方法。

2023/2/222023/2/233.3.1单峰区间

1.单峰区间在单峰区间内，在极小点左边，函数值随x的增加是严格减小的；在极小点右边，函数是严格增大的。因此在单峰区间内，函数值具有“高——低——高”的形态，可利用这一特征来确定初始单峰区间。2.确定单峰区间的进退算法一维搜索的各种方法的基本思想是“区间消去法”，而区间消去法的基本思想是：逐步缩小搜索的区间，直至最小点存在的范围小于给定的误差范围为止。2023/2/24基本思路：对单峰函数f(x)任选一个初始点x1及初始步长h，通过比较这两点函数值的大小，来决定第三点的位置，比较这三点的函数值的大小，确定是否为“高——低——高”的形态，依此确定向前或后退搜索。2023/2/25确定单峰区间的进退算法进退法：通过比较函数值大小来确定单峰区间的方法。给定的初始点和步长

单峰区间：2023/2/26进退步骤:(1)

选定初始点x1、初始步长h(h>0)。计算函数值f1=f(x1)和f2=f(x1+h)。比较f1和f2，可分三种情况：若f1>f2，则说明极小点x*必在x1的右方，应作前进运算，转(2);若f1<f2，则说明x*必在x1的左方，应作后退运算，转（3）；若f1=f2，则说明极小点x*必在点x1和x1+h点之间，已形成“高—低—高”形态，则初始单峰区间为[x1,x1+h]。

(2)

当f1>f2，将步长加倍，取下一个计算点为x=x1+2h，计算f(x1+2h),并令f1=f(x1+h),f2=f(x1+2h)。再比较f1和f2：若f1<f2，则相邻三点的函数值形成“高—低—高”形态，得到初始单峰区间[x1,x1+2h];若f1>f2，则应再作前进计算，步长加倍，取下一计算点为x=x1+4h，并比较f1=f(x1+2h)和f2=f(x1+4h)的函数值。如此反复循环，直到相邻三点的函数值形成“高—低—高”形态为止;若f1=f2，则初始单峰区间为[x1+h,x1+2h]

2023/2/27(3)

当f1<f2，做后退运算。步长改为负值，即从x1出发，向反方向搜索。取下一个计算点为x=x1-h，计算f(x1-h)，并令f2=f(x1),f1=f(x1-h)。此时：若f2<f1，则可确定初始单峰区间为[x1-h,x1+h]。若f2>f1，将步长加倍，继续后退。再算出下一个点的函数值f(x1-2h)，…。如此反复循环，直到相邻三点的函数值出现“高—低—高”形态为止；若f2=f1，则初始单峰区间为[x1-h,x1]。

可自己画出进退法的程序框图。2023/2/28区间缩小的序列消去原理：是通过对区间分割点函数值的计算和比较，将初始区间逐次进行缩小，当区间缩小到给定的精度要求时，可求得一维极小点的近似解。若，则极小点必在区间若，则极小点在若，则归入上面任何一种情况。区间消去法ab2023/2/29黄金分割法：黄金分割：将一线段分成两段，使得整段长度与较长段的比值等于较长段与较短段的比值解得3.3.2黄金分割法2023/2/210两个原则：

等比收缩原则：即区间每一次的缩短率λ不变；

对称取点原则：即所插入两点在区间中位置对称。2023/2/2110.618法算法步骤为：确定f(x)的初始搜索区间[a,b]及终止限ε。计算x2=a+0.618(b-a),f2=f(x2);计算x1=a+0.382(b-a),f1=f(x1);若|x2-x1|<ε，则输出x*=(x2+x1)/2，停机；否则，转(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黄金分割法2023/2/2122023/2/213黄金分割法的特点：（1）函数不必可微（2）第一次计算取两点，以后每次只需计算一点（3）收缩速度均匀。搜索次数3.3.2黄金分割法2023/2/214例3-4：minf(x)=-sinx

cosx，已知初始区间[a,b]＝[40°,50°]，区间缩小的相对精度ε2=0.13。（1）区间缩短次数（迭代次数）

取N=5

（2）第1轮迭代。计算黄金分割点，并对其函数值比较，缩短区间因，可淘汰或，这里淘汰，新区间为2023/2/2152023/2/2162023/2/2172023/2/2182023/2/2193.3.3二次插值法基本思想：多项式是逼近函数的一种常用工具。利用插值多项式进行一维搜索的基本思想是构造一个较低的插值多项式p(x)来近似地代替原目标函数f(x)，并以函数p(x)的极值点xp*（即p/(x)=0的根）作为目标函数f(x)的近似极值点。再通过比较各插值点和xp*的函数值及其所在位置，设法缩减搜索区间。从而最终逼近函数f(x)的极值点。

如果p(x)是二次多项式，则称为二次插值法，若p(x)是三次多项式，则称为三次插值法。一般来说，三次插值的收敛性要好一些，但要计算函数导数；而二次插值计算较简单且具有一定的精度，故应用广泛。二次插值又称为抛物线法。

2023/2/220设原目标函数f(x)的初始单峰搜索区间[x1,x3]已确定。函数f(x)在x1,x2,x3三点处函数值f1,f2,f3，其中x1<x2<x3，且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*。2023/2/221缩短区间：

若f(x)本身为二次函数，则在理论上一次求值就可找到最优点，xp*即为所求。若f(x)为高于二次的函数或其它函数，则一般xp*不与原函数f(x)的极小点x*重合，如上图所示。为了求得满足一定精度要求的f(x)的极小点x*，可采用逐步缩小区间的办法。搜索区间的缩小可根据xp*和x2，f(xp*)和f(x2)的相互关系，分六种不同的情况。

2023/2/2222023/2/2232023/2/2242023/2/225二次插值法计算步骤为：（1）确定初始搜索区间[x1,x3]，并给定ε。在初始区间[x1,x3]内选定一点x2，应满足条件：x1<x2<x3,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)。

2023/2/226

与0.618法相比较，二次插值法利用函数在已知几个近似点的值来确定新的近似点位置。而0.618法仅对几点函数值的大小进行比较，没有充分的利用函数本身的性质。因此，当函数f(x)具有较好的性质（如连续可微性）时，插值法往往比0.618法效果好，但它的程序要比0.618法稍复杂些。2023/2/2272023/2/2282023/2/2292023/2/2302023/2/2312023/2/2323.4多维无约束优化方法2023/2/2333.4多维无约束优化方法2023/2/2343.4.2最速下降法（梯度法）在求解无约束极值问题的解析法中，最速下降法简单易懂，迭代过程简单，对初始点的要求不严格。特别是，一些更有效的方法也常是在对它的改进后或在它的启发下而获得的。基本思想：在每个迭代点均沿着使目标函数值下降最快的方向前进，即负梯度方向，逐步走向最优点。搜索方向取为：S(k)=-▽F(X(k))

或S(k)=-▽F(X(k))/||▽F(X(k))||则下一个迭代点为:X(k+1)=X(k)-λ(k)S(k)

2023/2/235最速下降法以负梯度方向（函数值下降最快方向）作为搜索方向2023/2/2362023/2/237梯度法（最速下降法）的特点：1）初始点选取没有要求2）相邻两点的搜索方向正交缺点：迭代开始时下降幅度较大；在接近极小值点的时候，目标函数下降得很慢总结：负梯度方向仅是局部下降最快，不是最好的下降方向最优步长λ(k)的选取采用一维搜索：

F(X(k)+λ(k)S(k))=minF(X(k)+λS(k))2023/2/238最速下降法的迭代步骤：(1)给定初始点

X(0)及收敛精度ε,令k=0;(2)求目标函数的梯度向量▽F(X(k));(3)若||▽F(X(k)||≤ε，停止迭代；否则转下步。(4)用一维搜索方法确定步长λ(k)

。(5)按X-λ▽f(X)求得下一个点，且k=k+1；转（2）。2023/2/2392023/2/2402023/2/2412023/2/2423.4.3共轭梯度法

梯度法在迭代点远离极小点时，收敛速度较快，当迭代点接近极小点时，收敛速度变慢，其与共轭方向法结合可构成高效的混合算法。2023/2/243共轭梯度法第一步的搜索方向：负梯度方向第二步及以后各步的搜索方向为上一步搜索方向的共轭方向2023/2/244共轭方向（1）定义：为n阶正定矩阵，若两个矢量满足则称和对矩阵共轭。共轭矢量方向为共轭方向。（2）共轭方向与函数极小值点的关系考察正定二次函数2023/2/245两式相减，得沿的共轭方向可搜索到正定二次函数极小值点。沿共轭方向的搜索具有二次收敛性2023/2/246共轭梯度法的特点：（1）具有超线性收敛速度，计算效率高于梯度法，低于牛顿法（2）对初始点没有要求（3）不需计算二阶偏导及其逆矩阵，计算量小2023/2/2473.4.2牛顿法及其改进1、牛顿法基本思想：在X(k)邻域内用一个二次函数ф(X)来替代原目标函数f(X)，并将ф(X)的极小点Xp*作为对原目标函数f(X)求优的下一个迭代点X(k+1),经过多次迭代，使之逐步逼近f(X)的极小点X*。

f(X)≈f(X(k))+▽f(X(k))T(X–X(k))+

½(X-X(k))T▽2f(X(k))(X-X(k))=ф(X)

2023/2/248由于ф(X)是二次函数，求ф(X)的极小点即令其梯度为零▽ф(X)=▽f(X(k))+▽2f(X(k))(X-X(k))=0由此解得的X即为X(k+1)，即X(k+1)=X(k)-[▽2f(X(k))]-1▽f(X(k))=X(k)-H(X(k))-1▽f(X(k))

搜索方向为：

S(k)=-H(X(k))-1▽f(X(k))2023/2/249

如果f(X)本身为二次函数，则H(X)是一个常量矩阵，其元素均为常量，这时逼近式是准确的，因此从任一点出发，一次迭代即可达到极小值。对于非二次函数，若函数的二次性态较强或迭代点已进入最优点的邻域，则其收敛速度也是很快的。

2023/2/250例：试用牛顿法求函数f(X)=x12+25x22的极小点。2023/2/2512、阻尼牛顿法由于牛顿法中的步长λ(k)=1，会造成在迭代过程中函数值有所增大的情况。因此，对初始点的选取有严格要求，尽管用牛顿法收敛很快，但初始点不能离极小点太远，否则可能不收敛。极小点的位置又是事先未知的，这个要求难以达到。为了摆脱对初始点的苛刻要求，人们对牛顿法进行了改进，即阻尼牛顿法。阻尼牛顿法的迭代公式为

X(k+1)=X(k)-

λ(k)H(X(k))-1▽f(X(k))

阻尼牛顿法保持了牛顿法的特点，且对初始点无特别要求。虽然计算量多了些，但实用性较好。2023/2/2523、阻尼牛顿法迭代步骤如下：（1）取初始点X(0),ε>0,令K=0.（2）计算▽f(X(k)).（3）若║▽f(X(k))║≤ε,停止,X*=X(k);否则转（4）.（4）计算H(X(k))-1,令S(k)=-H-1▽f(X(k)).（5）

求λ(k),使f(X(k)+λ(k)S(k))=minf(X(k)+λ(k)S(k)).（6）令X(k+1)=X(k)+λ(k)S(k),K=K+1,转(2)

牛顿法和阻尼牛顿法虽具有收敛快的优点，但它们最大的缺点是每次迭代都要计算二阶导数矩阵Hessian矩阵及其逆阵H-1，此计算量比较繁琐。此外，牛顿法还要求H(X)正定，否则H(X)为奇异阵，无法计算H-1,所以对于多变量复杂目标函数的优化问题，故此法不可用。2023/2/2533.4.5变尺度法优化迭代的一般公式可以表达为

X(k+1)=X(k)-λ(k)Ak▽f(X(k))

变尺度法：Ak是需要构造的一个n×n对称方阵,即尺度矩阵。2023/2/254尺度矩阵A(k)的构造，可从初始矩阵A(k)=E（单位矩阵）开始，它通过对公式

A(k+1)=A(k)+ΔA(k)

中的修正矩阵ΔA(k)的不断修正，在迭代中逐步逼近于H(X(K))-1。由于修正矩阵的不同，就构成了种种不同的变尺度法。2023/2/255DFP法中的修正矩阵ΔA(k)为：

式中：Δg(k)=g(k+1)-g(k)=▽f(X(k+1))-▽f(X(k))△X(k)=X(k+1)-X(k)

另一种变尺度法为BFGS，计算公式见书中表述。2023/2/256例：用DFP法解minf(X)=60-10x1-4x2+x12+x22-x1x2。初始点为X(0)=(0,0)T,ε=0.0001.解：（1）令K=0,（2）计算目标函数的梯度▽f(X(0))

（3）搜索方向为

虽然此时搜索方向为负梯度方向。沿此方向进行一维搜索，求得最优步长因子λk2023/2/257将X(1)=X(0)+λS(0)代入目标函数得

f(X(1))=60-10(10λ)-4(4λ)+(10λ)2+(4λ)2-(10λ)(4λ)=60-116λ+76λ

2=q(λ)为求极小值，将上式对λ求导，并令q/(λ)=0，即

dq/dλ=-116+152λ=0解得λ(0)=0.7631得X(1)=X(0)+λ(0)S(0)=[0,0]T+0.7631[10,4]T=[7.631,3.052]T（4）收敛性判别2023/2/258(5）因此时K<n=2，所以计算△X(k)=△X(0)=X(1)-X(0)=[7.631,3.052]T△g(k)=△g(0)=▽f(X(1))-▽f(X(0))=[12.211,-1.526]T按公式计算尺度矩阵

A(k+1)=A(k)+ΔA(k)和ΔA(k)=(ΔX(k)ΔX(k)T)/(ΔX(k)TΔg(k))-(A(k)Δg(k)Δg(k)TA(k))/(Δg(k)TA(k)Δg(k))计算近似矩阵A(k+1)A(1)=A(0)+ΔA(0)=由此可见，它是一个对称正定矩阵。2023/2/259（6）K←k+1。构造新的搜索方向（拟牛顿方向）为:S(k+1)=S(1)=-A(1)▽f(X(1))=[0.646,5.169]T

沿S(1)方向作一维搜索求λ(1)，方法与求λ(0)相同，得λ(1)=0.5701，新的迭代点为:X(2)=X(1)+λ(1)S(1)=[7.9999,5.9999]T≈[8,6]T（7）收敛性差别：║▽f(X(2))║=(02+02)1/2<ε，停止迭代。输出最优解

X*=X(2)=[8,6]Tf(X*)=f(X(2))=8注意：DFP变尺度法属于共轭方向法。2023/2/260对比以二次函数为例：梯度法：每步以负梯度方向为搜索方向，要走很多步才能到达极值点附近。牛顿法：从初始点出发沿负梯度方向转移角度一步即可到达极值点。共轭梯度法：第一步负梯度方向，第二步梯度的共轭方向，两步达到最优。变尺度法：两步达到最优2023/2/261二元四次函数方法梯度法牛顿法共轭梯度法变尺度法次数100355极值2.5402.111.7次数7320极值002023/2/262直接解法2023/2/2633.4.5坐标轮换法坐标轮换法属于直接解法。坐标轮换法的基本思想是将n个变量的优化问题转化为一系列一维最优化问题来求解。设n维设计变量为

X=[x1,x2,…,xn]Tn维空间的坐标方向（坐标轴的单位向量）为：

e1=[1,0,0,……,0]Te2=[0,1,0,……,0]T……en=[0,0,0,……,0,1]T坐标轮换法就是分别（轮换地）沿各个坐标轴方向搜索最优解2023/2/264

简单地说，就是先将n-1个变量固定不变，只对第一个变量x1（即e1方向）进行一维搜索，得到最优解X(1)。然后再对第二个变量进行一维搜索，而保持其余n-1个变量不变，如此等等。每次均保持n-1个变量不变，只对一个变量进行一维搜索，如此一直得到X(n),即完成一次轮换计算。若满足收敛准则，则停止迭代；否则从前一轮的最末点X(n)开始，将X(n)赋值给X(0)，重复上述过程，作下一轮搜索。如此直到收敛为止。根据上述原理，对于第k轮计算，其迭代计算公式为

Xi(k)=Xi-1(k)+λSi(k)(i=1,2,…,n)

Si(k)=ei=1(i=1,2,…,n)2023/2/265坐标轮换法的迭代步骤如下：（１）取初始点X(0)及ε>0，令k=1。（２）令i=1,Xi-1(k)=

X(0)。（3）一维搜索求在ei方向的最优步长λi，使

f(Xi-1(k)+λi(k)ei)=minf(Xi-1(k)+λei)Xi(k)=Xi-1(k)+λi(k)ei（4）

若i=n，则转（5）；否则，则i=i+1，转(3)。（5）

检验‖Xn(k)-X0(0)‖≤ε？若满足收敛准则，停止迭代，X*=Xn(k)；否则，令X(0)=Xn(k)，k=k+1，转(2)。2023/2/266例：用坐标轮换法求minf(X)=60-10x1-4x2+x12+x22-x1x2，取X(0)=[0,0]T。解：其搜索过程如图：第一次迭代：令x1=0，则f(x2)=60-4x2+x22,对x2寻优得x2=2，此时f(X(1))=56，再固定x2=2，则f(x1)=56-12x1+x12，对x1寻优得x1=6，此时f(X(2))=20，即X(2)=[6,2]T，转下一轮。2023/2/267

第二轮迭代：

固定x1=6，则f(x2)=36-10x2+x22，对x2寻优得x2=5，此时f(X(3))=11，再固定x2=5，则f(x1)=65-15x1+x12，对x1寻优得x1=7.5，此时f(X(4))=8.75，即X(4)=[7.5,5]T，转下一轮。如此迭代下去，直至逼近实际极小点

X*=[8,6]T,f(X*)=82023/2/2683.4.6Powell（鲍威尔）法鲍威尔法是无约束最优化问题效果最佳的一种计算方法。在优化设计中，常使用鲍威尔法配合惩罚函数法，来处理有约束优化问题，它属于共轭方向法。鲍威尔法又分为初始鲍威尔法和改进的鲍威尔法2023/2/269改进鲍威尔法基本思想是：基于坐标轮换法的构思，在不使用导数的前提下，在迭代中逐次产生共轭方向组（以加快收敛速度）。在每轮迭代获得新的方向Sk(n+1)之后，在组成下一轮迭代的新方向组时，有选择地去掉其中某一个方向Skm（1≤m≤n），以避免新方向组中的各方向出现线性相关的情形。2023/2/270这种改进的具体方法是：（1）选择初始点X(0)作为X0(1)，选择计算精度ε，取n个单位坐标向量为初始方向组，即

Si(0)=ei

,(i=1,2,…,n)（2）从X0(1)出发，用坐标轮换法依次沿S1(0)

、S2(0)

、…、Sn(0)方向作一维搜索，可得各自方向上的