无约束优化方法(最速下降法

《无约束优化方法(最速下降法》由会员分享，可在线阅读，更多相关《无约束优化方法(最速下降法（10页珍藏版）》请在装配图网上搜索。

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

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

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

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

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

6、| (X( k)|为搜索方向。如此最速下降法的迭代公式为X（K+1）= X（K 7 K 誌 I）当第k次的迭代初始点4.3X (k) 和搜索方向d (k) 已经确定的情况下，原目标函数成为关于步长G的一维函数。即申（a） = f （X（ k）+a S（ k）最优步长a可以利用一维搜索的方法求得Kmin申（a） = f （X（k+1） = f （X（k）+a d（k） = minf （X（k）+ad（k） aka根据一元函数极值的必要条件和多元复合函数的求导公式，得0（a） = -Vf （X（ k）+a d（ k） T Vf （X（ k） = 0Vf （X（ K+1 ）T Vf（ x（ K）二

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

8、 0,1,2,)4.4K将其与式4.3相比拟，可知，此处J X( k)点导数的模|Vf (X (训，而此时的搜索方 向d伙)=vf( x伙)也不再是个单位向量。1) 给定初始点X(0)，收敛精度并令计算次数k u 0 ；2) 计算X点的梯度Vf (X(k)与梯度的模|Vf (X(k)|，并令d (k )Vf (X (k)|Vf (X (k)|3)判断是否满足精度指标|Vf(X(k)|8，不满足精度指标，转下一步计算。3确定搜索方向V/ (X(0)|Vf (X(0)|4计算新的迭代点由公式4.2可得X(i) = X(0) +a d(0)代入目标函数f (X(i)=-1)2 +-1)2沿d(k)方

9、向进展一维搜索或对a求导，并令其为零df (X dda-1) +-1)令df (X(1) = 0，求得最优步长a =迈da05计算新迭代点aX (1)逋a於J6计算新迭代点的梯度与梯度的模Vf (X (1)=2(x -1)12(x -1)2|Vf (X (0)卜 0 8因已满足精度要求，停止迭代，得最优解为f (X *) = 0可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点X *。这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3所示。通过上面的分析可知最速下降法具有以下特点：1理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储 量也较小，适用于计

10、算机计算。2对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是 指某点的一局部性质。3最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯 齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。4最速下降法的收敛速度与目标函数的性质以与初始点的选择密切相关。对于 等值线（面）为同心圆球的目标函数，一次搜索即可达到极小点。假如目标函数为 二次函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值 点。最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估 计式上看出来。在适当条件下，有w X H (丄-矇)II - II

11、式中的海赛矩阵最大特征值上界；M 其最小特征值下界。word当相邻两个迭代点之间满足上式时右边的系数为小于等于1 的正的常数，我们称 相应的迭代方法是具有线性收敛速度的迭代法。因此，最速下降法是具有线性收敛速 度的选代法。鉴于应用最速下降法可以使目标函数在开头几步下降很快，所以它可与其它无约束优 化方法配合使用。即在开始阶段用梯度法求得一个较优的初始点，然后用其它收敛快的方法继续寻找极小点。42牛顿法牛顿法是根据目标函数的等值线在极值点附近为同心椭圆族的特点，在极值点X* 邻域内用一个二次函数申(X)来近似代替原目标函数f (X)，并将申(X)的极小值点作 为对目标函数f (X)求优的下一个迭

12、代点，经屡次迭代，使之逼近原目标函数f (X)的 极小值点。设目标函数是连续二阶可微的，将函数在X (k)点按泰勒级数展开，并保存到二次 项，得f (X)(X) = /(X(K 呵(X(K 川 X - X(K ：(X - X(K )t 呵(X(K)(X - X(K)此式是个二次函数，设X(k+1)为P (X)的极小值点，如此Vv ( X (k+1) = 0即Vf (X(k) +V 2f (X(k)(X(k+1) - X(k)二 0X(K+1) = X(K) -V2f (X(K)1Vf (X(K)(k = 0,1,2,.)4.5这就是多元函数求极值的牛顿法迭代公式。式中取d (k) =-V2 f

13、 ( X (K )-1 Vf ( X (K)称为牛顿方向，为常数。式中没有步长d，或者可以k看成步长恒等于 1，所以牛顿法是一种定步长的迭代。例题4.4用牛顿法求目标函数f (X) = x2 + 25x2的极小值。12解1取初始点X(0)二2 2t2计算梯度、二阶偏导数矩阵与其逆矩阵3计算新的迭代点Vf （X（0）=2 x150x2410005050X =X（o）- V2f （X（o）-i Vf （X（o）=04 1_100 _0_50 _经过一次迭代即可求得极小值点X * = 0 0T，函数极小值f (X *) = 0。4.2.2 阻尼牛顿法由以上的两个例题可以看出，对于二次函数，用牛顿法迭

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

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

16、，达到同样的精度，要经过25 次的迭代，越靠近极小值点收敛速度越慢，使牛顿法 收敛速度快的优势损失殆尽。阻尼牛顿法的迭代过程： 阻尼牛顿法的计算步骤如下：1给定初始点X(0)，收敛精度5并令计算次数k u 0 ；2计算X(k)点的梯度Yf (X(k)和梯度的模|vf (X(k)| ；3判断是否满足精度指标|pf(X(k)|S ；假如满足，X(k)为最优点，迭代停止, 输出最优解X* = X(k)和f (X*)二f (X(k)，否如此进展下一步计算；5计算X(k)点的牛顿方向d (k)d (k) =V2f (X (K)-1 vf (X (K)6以X(k)为出发点，沿d(k)进展一维搜索，求能使函

17、数值下降最多的步长Qp,即Kminf(X(k) +ad(k) = f(X(k) +a d(k)QK令X(k+1)= X(k) +q d(k) ,k = k+1，转到步骤2)。K阻尼牛顿法的程序框图如图4.7 所示：牛顿法的总结牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的最大优点是收敛速度快。也 就是说，它的迭代次数相对其他方法来说少得多。特别是对于一些性态较好的目标函 数，例如二次函数，只需保证求梯度和二阶偏导数矩阵时的精度，不管初始点在何 处，均可一步就找出最优点。可是这类方法也有很大的缺点。首先，在每次迭代决定 选用原如此和条件： 该方法适用于目标函数具有一阶、二阶偏导数，海森矩阵非奇 异，维数不太高的场合。