无约束优化方法最速下降法牛顿法

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

2、搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。一:间接法一一要使用导数的无约束优化方法，如梯度法、(阻尼)牛顿法、变尺度法、共食梯度法等。二:直接法一一只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。无约束优化问题的一般形式可描述为：求n维设计变量X=IxiX2xjwRn使目标函数f(X)=min目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别无约束优化问题的求解：1、解析法可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程_*minf(X)=0的解。也就是求x*使其满足*、ffX2=0Xi_*fX2_0Xcx2

3、-0a_*IfX1=0Xn解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。但上式是一个含有n个未知量，n个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。2、数值方法数值迭代法的基本思想是从一个初始点X(0)出发，按照一个可行的搜索方向d搜索，确定最佳的步长a。使函数值沿d方向下降最大，得到X点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采用的基本迭代公式为X(KHt)=X(K)

4、+口加(K)(k=0,1,2,)(4.2)(K)在上式中，d是第是k+1次搜索或迭代方向，称为搜索方向(迭代方向)。由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点X(k)、搜索方向d(k)和迭代步长”k，称为优化方法迭代算法的三要素。第三章我们已经讨论了如何在搜索方向d(k)上确定最优步长ak的方法，本章我们将讨论如何确定搜索方向(k)d。最常用的数值方法是搜索方法，其基本思想如下图所示:无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共食梯度法。另一类是直接利用目标函数值确定搜索方向的方法

5、，称为直接法，如坐标轮换法、鲍威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向0d的方法不同。4.1最速下降法最速下降法是一个求解极值问题的古老算法，1847年由柯西(Cauchy)提出。4.1.1 最速下降法的基本原理由第二章优化设计的数学基础可知，梯度方向是函数增加最快的方向，负梯度方向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度法。由公式(4.2)X(K1)=X(K)=Kd(K)(k=0,1,2,)可知，若某次选代中己取得点X(k),从该点出发，取负梯度方向为搜索方向。则最

6、速下降法的迭代公式为X(Kd)=X(K)-：Kf(X(k)'|f(X(k)|(k=0,1,2,)(4.3)当第k次的迭代初始点X的和搜索方向d(k)已经确定的情况下，原目标函数成为关于步长«的一维函数。即(：)=f(X(K):S(K)最优步长«K可以利用一维搜索的方法求得min(：)=f(X(k1)=f(X(K)二kd(k)=minf(X(K):d(k)ota根据一元函数极值的必要条件和多元复合函数的求导公式，得T(：)-'f(X(K)：d(k)”(X(K)=0”(X(K1)一f(X(K)=0或写成d(K1)Td(k)=0由此可知，在最速下降法中相邻两个搜索

7、方向互相正交。也就是说在用最速下降法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直，形成“之”字形的锯齿现象，如图4.1所示。最速下降法刚开始搜索步长比较大，愈靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线是较扁的椭圆时，这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目标函数的最快搜索方向。KrXl图4.1最速下降法的搜索路径此外，最速下降法的迭代公式也可以写成下面的形式X(K书)=X(K)_uKVf(X(k)(k=0,1,2,)(4.4)将其与式4.3相比较，可知，此处aK

8、等于4.3式中步长除以函数在X(K)点导数的模|f(X(k)|,而此时的搜索方向d(k)=Vf(X(k)也不再是个单位向量。4.1.2 最速下降法的迭代过程1) 给定初始点X(0),收敛精度J并令计算次数ku0;2) 计算X-点的梯度$f(X(K)及梯度的模|Vf(X(k)|,并令d(k)_"(X(k)h(X(k)|3) )判断是否满足精度指标|Vf(X(k)|<ax若满足，X(k)为最优点，迭代停止,输出最优解X*=X(k、Df(X*)=f(X(k),否则进行下一步计算；4) 以X为出发点，沿d(k)进行一维搜索，求能使函数值下降最多的步长口即minf(X(k)：d的);f(

9、X(k)：Kd的)5) 令X(k+)=X(k)+o(Kd(k),k=k+1,转到步骤2)。最速下降法的程序框图如图4.2所示。4.2最速下降法的程序框图例题4.1用最速下降法求目标函数f(X)=(%-1)2+(x2-1)2的极小值，设初始点X(0)=00T,计算精度8=10立。解(1)计算初始点X处目标函数的梯度和梯度的模汗(X)Vf(X-)J二四一1)-2-X)匕(X2-1)1-2J一改2一|"f(X(0)-2.2(2)由于|Vf(X(0)|=2页名，不满足精度指标，转下一步计算。(3)确定搜索方向d(0)士Vf(X(0)_1-2_72vf(x(0)|"272，2-11(

10、4)计算新的迭代点由公式(4.2)可得1X=x(0)d(0)=00一一我一、一rr,9代入目标函数f(X(1)=(-1)2(_-1)22.2V2=>/21a沿d的方向进行一维搜索(或对久求导，并令其为零)用(二一1)一2一(二一1)d：2222令3=0,d：(5)计算新迭代点2")=0_2(X2-1)_0(6)计算新迭代点的梯度及梯度的模“(X(1)二pf(X)=0名因已满足精度要求，停止迭代，得最优解为*11I*X=i,f(X)=0_1可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。图4.3例

11、题4.1目标函数极小值的搜索过程通过上面的分析可知最速下降法具有以下特点：(1)理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储量也较小，适用于计算机计算。(2)对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。(3)最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。(4)最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于等值线(面)为同心圆(球)的目标函数，一次搜索即可达到极小点。若目标函数为二次函数，等值线为椭圆，当初始点选在长轴或短轴上时

12、，一次搜索也可达到极小值点。最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。在适当条件下，有(一勒八门式中的海赛矩阵最大特征值上界;其最小特征值下界。当相邻两个迭代点之间满足上式时(右边的系数为小于等于1的正的常数)，我们称相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速度的选代法。鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优化方法配合使用。即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极小点。4.2牛顿法一.一，.*牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特

13、点，在极值点X邻域内用一个二次函数中(X)来近似代替原目标函数f(X),并将平(X)的极小值点作为对目标函数f(X)求优的下一个迭代点，经多次迭代，使之逼近原目标函数f(X)的极小值点。4.2.1 牛顿法的基本原理设目标函数是连续二阶可微的，将函数在X(k)点按泰勒级数展开，并保留到二次项，得f(X)：(X)=f(X(K)f(X(K)T(X-X(K)：(X-X(K)2f(X(K)(X-X(K)此式是个二次函数，设X(k却为平(X)的极小值点，则'(X(k1)=0即'f(X(k),2f(X(k)(X(k-X(k)=0X(K")=X(K)-2f(X(K)Tvf(X(K)(

14、k=0,1,2；)(4.5)_这就是多元函数求极值的牛顿法迭代公式。式中取d(k)=_V2f(X(K),Vf(X(K)称为牛顿方向，为常数。式中没有步长尊k,或者可以看成步长恒等于1,所以牛顿法是一种定步长的迭代。例题4.4用牛顿法求目标函数f(X)=x2+25x2的极小值。解(1)取初始点X(0)=22T(2)计算梯度、二阶偏导数矩阵及其逆矩阵f(X(0)=520；=l40；22'、f(X)=015012f(X),=一121500(3)计算新的迭代点X=X(0)一“2f(X)、f(X)=；250经过一次迭代即可求得极小值点X=00T,函数极小值f(X)=0。4.2.2阻尼牛顿法由以上

15、的两个例题可以看出，对于二次函数，用牛顿法迭代一次即可得到最优点；对于非二次函数，若函数的迭代点已进入极小点的邻域，则其收敛速度也是很快的。但是从牛顿法迭代公式的推导可以看出，迭代点是由近似二次函数中(X)的极值条件确定的，该点可能是9(X)极小值点，也可能是中(X)的极大值点。因此在用牛顿法迭代时，可能会出现函数上升的现象，即f(X(k*)Af(X(k),使迭代不能收敛于最优点。例如上例中若取初始点X(0)=01T,第一次迭代点的函数值就增大。这表明牛顿法不能保证函数值稳定地下降，在严重的情况下甚至不能收敛而导致计算失败。可见，牛顿法对初始点的要求是比较苛刻的，所选取的初始点离极小值点不能太

16、远。而在极小值点位置未知的情况下，上述要求很难达到。为了消除牛顿法的上述这些弊病，需要对其做一些修改。将牛顿法定步长的迭代，(k)改为变步长的迭代，引入步长1a，在X的牛顿方向进行一维搜索，保证每次迭代点的函数值都是下降的。这种方法称为阻尼牛顿法，其迭代公式为X(K1)=X(K)-二k2f(X(K)-1'f(X(K)(k=0,1,2,)(4.6)式中，ak为牛顿方向的最优步长。这种方法对初始点的选取不再苛刻，从而提高了牛顿法的可靠度。但采用阻尼牛顿法，每次迭代都要进行一维搜索，使收敛速度大大降低。例如，对于例4.6所示的目标函数，取同样的初始点，采用阻尼牛顿法进行迭代，达到同样的精度，

17、要经过25次的迭代，越靠近极小值点收敛速度越慢，使牛顿法收敛速度快的优势损失殆尽。阻尼牛顿法的迭代过程：阻尼牛顿法的计算步骤如下：1)给定初始点X(0),收敛精度£,并令计算次数ku0；2)计算X(kL的梯度Vf(X(K)和梯度的模|Vf(X(k)|;3)判断是否满足精度指标|pf(X(k)|;若满足，X(k)为最优点，迭代停止，输出最优解X*=X(k)和f(X*):f(X(k),否则进行下一步计算；5)计算X(k)点的牛顿方向d(k)d的2f(X(K)Af(X(K)6)以X的为出发点，沿d(k)进行一维搜索，求能使函数值下降最多的步长口即minf(X(k)：d的);f(X(k);Kd的)Ct令X=X(k)+口Kd(k),k=k+l,转到步骤2)。阻尼牛顿法的程序框图如图4.7所示:4.7