无约束优化方法

第四章无约束优化方法——最速下降法，牛顿型方法概述在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。问学问学题模型本身就（1）有些实际问题，其是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。

梯度法等。所以无约束优化问题的解法是方法的基本组成部分，也是优基础。根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。一：间接法——要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。梯度法等。二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。无约束优化问题的一般形式可描述为：求n维设计变量X=[x xX=[x x12LERn使目标函数目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。无约束优化问题的求解：1、解析法

可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程minf(X*)二0的解。也就是fX!=的解。也就是fX!=o

dxif(X*)=0求X*使其满足dx2Mdxn解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有n个未知量，n个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，

要用数值计算的方法。由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。2、数值方法数值迭代法的基本思想是从一个初始点X出发，按照一个可行的搜索方向dX(0) d(0)搜索，确定最佳的步长使函数值沿d方向下降最大，得到点。依此一步一步X(K+i)=XX(K+i)=X(K)+ad(k)(k二0丄2,人)„、搜索方向比和迭代步长—，，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向P上确定最优步长的方法，本章我们将讨论如何确定搜索方向dd(k)。最思常想用最思常想用如的下图数值所示方法：是搜索方法，其基本护d1xk+l无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共轭梯度法。另一类是直接利用目标函数值确定搜索方向的方法，称为直接法，如坐标轮换法、鲍威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d的方法不同。

4．1最速下降法最速下降法是一个求解极值问题的古老算法，1847年由柯西（Cauchy）老算法，1847年由柯西（Cauchy）提!A!出。4.1.1最速下降法的基本原理由第二章优化设计的数学基础可知，梯度方向是函数增加最快的方向，负梯度方向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度法。由公式X(k+X(k+1)=X(k)+ad(K)(k=0,1,2,A)可知，若某次选代中己取得点X，从该X(k)点出发，取负梯度方向d(kd(k)W(X(k))为搜索方向。则最速下降法的迭代公式X(KX(K+1)Vf(X(k))

||vf(X(k))||(k=0,1,2,L)O当第k次的迭代初始点x和搜索方向d已X(k) d(k)经确定的情况下，原目标函数成为关于步长的一维函数。即a甲(a)二f(X(K)+aS(K))最优步长可以利用一维搜索的方法求得aKrrmin申(a)=f(X伙+d)=f(X(k+ad伙))=minf(X(k+ad伙))k根据一元函数极值的必要条件和多元复合函数的求导公式，得r0（a）=—[yf（X（K）+ad（k））丁Vf（X（k））=0[Vf（X（k+i））]TVf（X（k））=0或写成rr[d（K+1）]Td（k）=0由此可知，在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直，形成“之”字形的锯齿现象，如图所示。最速下降法刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线是较扁的椭圆时，这种缺陷更加明显。因此所谓最速

下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方向。此外，最速下降图法最速的下降法迭的搜索代路径公式也可以写成下面的形式L()X(K+i)=X(K)-aK将其与式相比较，可知，此处 等于式中aX(K)此时的搜索方向X(K)此时的搜索方向rd(k)=Vf(X(k))向量。4.1.2最速下降法的迭代过程给定初始点(0),收敛精度£,并X(0)令计算次数;ku0计算x点的梯度vf(x)及梯度的模X(k) vf(X(K))|vf(X(k))1，并令号“、=Vf(X(k))

=||Yf(X(k))||||vf(X(||vf(X(k))1<8若满足，X为最优点，迭代停止，输出X(k)最优解XX和^(X)f(X/否则进行下一X*=X(k)f(X*)=f(X(k))步计算；以X以X为出发点，沿P进行一维搜X(k) d(k)求能使函数值下降最多的步长,aK索即rr5)步骤2)最速下降法的程序框图如图所示。minf(X(k)+ad(k))=f(X(k)+ad(k)5)步骤2)最速下降法的程序框图如图所示。令 r,k=k+l,转到X(k+1)=X(k)+ad(k)K

最速下降法的程序框图最速下降法的程序框图例题用最速下降法求目标函数o£=10-2X（0）=[00]tf(X的极小值，设初始点f(o£=10-2X（0）=[00]t解(1)计算初始点(0处目标函数X(0)的梯度和梯度的模

Vf(X(0))=dx I 2(x-1)奇(X)「|_Vf(X(0))=dx I 2(x-1)奇(X)「|_2(x；-1)dx I2||Vf(X(0))1=2迈-2-2指标(转下由步计算)。2迈，不满足精度指标，转下一步计算。(3)确定搜索方向rd(0)Vf(X(0))||Vf(X(0))(4)计算新的迭代点由公式()可得rX(1)二X(0)+ad(0)二代入目标函数f(X(1))=-1)2+(1a忑aU21-1)2沿p方向进行一维搜索(或对求导，并TOC\o"1-5"\h\zd(k) a令其为零)= -1)+ -1)da令df(X(n)=0，，求得最优步长a=迈。da 0'

(5)计算新迭代点X(1)(6)的模(6)的模计算新迭代点的梯度及梯度2(x-1)12(x-1)2冋(X(0))||=0<£因已满足精度要求，停止迭代，得最优解为f(X*)二0可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点*。这是因为圆周上任意一点的负梯度X*方向总是指向圆心的，如图所示。通过上面的分析可知最速下降法具有以下特点：（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储量也较小，适用于计算机计算。（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。

（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。若目标函数为二次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速iHW（1— II护一打丨度的估计式上看出来。在适当条件下，⑺卄m「的海赛矩阵最大特—・匚—其最小特征值下界。邻两个迭代点之间满足上式时（右系数为小于等于1的正的常数），我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的选代法。鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极小点。4．2牛顿法牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点*邻域内用一个二次函数(X、来近似代替原目标函数”(X、，并将(X)的极小值点f(X) 申(X)作为对目标函数f(X)求优的下一个迭代点，经多次迭代，使之逼近原目标函数f(X)的极小值点。f(X)4.2.1牛顿法的基本原理设目标函数是连续二阶可微的，将函数在()点按泰勒级数展开，并保留到X(k)二次项，得f(X)〜申(X)=f(X(K))+[Vf(X(K))]T(X-X(K))+2(X-X(K))TV2f(X(K))(X-X(K))此式是个二次函数，设X为(X、的极小值X(k+1) (X)点，则 (X)V(X(k+1))=0

Vf(X(k))+v2f(X(k))(X(k+1)-X(k))二0X(K+l)=X(K)-[V2f(X(K))]1Vf(X(K)) (k=0，1，2L)()这就是多元函数求极值的牛顿法迭代公式。式中取r 称为牛顿d(k)二一[V2f(X(K))]-1Vf(X(K))方向，为常数。式中没有步长，或者可a以看成步长恒等于1所以牛顿法是一种定步长的迭代。例题用牛顿法求目标函数f(X、 25的极f(X)=x2+25x2小值。12解(1)取初始点X[22]X(0)=[22]t(2)计算梯度、二阶偏导数矩阵及其逆矩阵Vf(XVf(X(0))=2x150x4100-20_V2f(X)=0502001501[V2f(X)]-1=20(3)计算新的迭代点

X⑴=X（0）-[V2f（X（o））]-iVf（X（o））=0「4—-0_0「4—-0_1_100__0_50_12220X*二[00]T9函数极小值f(X*)=0。4.2.2阻尼牛顿法由以上的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数(X)的极值条件确定的，该点可能是(X)极小值点，也可能是(X)的极大值点。9(X) 甲(X)因此在用牛顿法迭代时，可能会出现函数上升的现象，即f(X)f(X)，使迭代不f(X(k+1))>f(X(k))能收敛于最优点。例如上例中若取初始X[01]，第一次迭代点的函数值就增X（o）=[01]t大。这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。可见，牛顿法对初始点的要求是比较苛刻的，所选取的初始点离极小值点不能太远。而在极小值点位置未知的情况下，上述要求很难达到。为了消除牛顿法的上述这些弊病，需要对其做一些修改。将牛顿法定步长的迭代，改为变步长的迭代，引入步长°，在x⑷的牛顿方向进行一维搜索，保证每次迭代点的函数值都是下降的。这种方法称为阻尼牛顿法，其迭代公式为X(K+1)=X(K)-a[V2f(X(K))]-1Vf(X(K)) (k=0,1,2,L)k()式中，为牛顿方向的最优步长。这种方aK法对初始点的选取不再苛刻，从而提高了牛顿法的可靠度。但采用阻尼牛顿法，每次迭代都要进行一维搜索，使收敛速度大大降低。例如，对于例所示的目标函数，取同样的初始点，采用阻尼牛顿法进行迭代，达到同样的精度，要经过25次的迭代，越靠近极小值点收敛速度越慢，使牛顿法收敛速度快的优势损失殆尽。阻尼牛顿法的迭代过程：阻尼牛顿法的计算步骤如下：1)给定初始点(0),收敛精度5并令X(0)计算次数k0；2)计算x点的梯度vf(x)和