《无约束优化方法(最速下降法》由会员分享，可在线阅读，更多相关《无约束优化方法(最速下降法（13页珍藏版）》请在金锄头文库上搜索。
1、第四章 无约束优化方法最速下降法，牛顿型方法概述在求解目标函数的极小值的过程中，若对设计变量的取值范围不加限制，则称这种最优化问题为无约束优化问题。尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的基本组成部分。因为约束最优化问题可以通过 对约束条件的处理，转化为无约束最优化问题来求解。为什么要研究无约束优化问题?（1）有些实际问题，其数学模型本身就是一个无约束优化问题。（2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（3）约束优化问题的求解可以通过一系列无约束优化方法来达到。 所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。
2、根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。 一：间接法要使用导数的无约束优化方法，如梯度法、（阻尼）牛顿法、变尺度 法、共轭梯度法等。二：直接法只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯 形法等。无约束优化问题的一般形式可描述为：求n维设计变量X =x x L x L e Rn12n使目标函数f （X） n min目前已研究出很多种无约束优化方法，它们的主要不同点在于 构造搜索方向上的差别 无约束优化问题的求解：1、解析法可以利用无约束优化问题的极值条件求得。即将求目标函数的极值问题变成求方程的解。也就是求X则吏其满足min f (X *) = 0f
3、 (X *)dx1芳(X *)dx2Mdxn解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值 点。但上式是一个含有n个未知量，n个方程的方程组，在实际问题中一般是非线性 的，很难用解析法求解，要用数值计算的方法。由第二章的讲述我们知道，优化问题 的一般解法是数值迭代的方法。因此，与其用数值方法求解非线性方程组，还不如用 数值迭代的方法直接求解无约束极值问题。2、数值方法p数值迭代法的基本思想是从一个初始点X(0)出发，按照一个可行的搜索方向d(0)p搜索，确定最佳的步长a使函数值沿d(0)方向下降最大，得到X点。依此一步一步地重复数值计算，最终达到最优点。优化计算所采
4、用的基本迭代公式为pX ( k+i)= X ( k)+a d ( k )(k 二 0,1,2, A )(4.2)Kr在上式中，d ( k )是第是k+1次搜索或迭代方向，称为搜索方向(迭代方向)。由上面的迭代公式可以看出，采用数值法进行迭代求优时，需要确定初始点X (k)、搜 p索方向d (k)和迭代步长a ，称为优化方法迭代算法的三要素。第三章我们已经讨论了pK如何在搜索方向d (k)上确定最优步长a的方法，本章我们将讨论如何确定搜索方向dp 。Kd(k)。最常用的数值方法是搜索方法，其基本思想如下图所示：d2df+1dk无约束优化方法可以分为两类。一类是通过计算目标函数的一阶或二阶导数值确
5、 定搜索方向的方法，称为间接法，如最速下降法、牛顿法、变尺度法和共轭梯度法。 另一类是直接利用目标函数值确定搜索方向的方法，称为直接法，如坐标轮换法、鲍 威尔法和单形替换法。各种无约束优化方法的区别在于确定其搜索方向Od的方法不 同。41最速下降法最速下降法是一个求解极值问题的古老算法，1847年由柯西(Cauchy )提出。4.1.1最速下降法的基本原理由第二章优化设计的数学基础可知，梯度方向是函数增加最快的方向，负梯度方 向是函数下降最快的方向，所以最速下降法以负梯度方向为搜索方向，每次迭代都沿 着负梯度方向进行一维搜索，直到满足精度要求为止。因此，最速下降法又称为梯度 法。由公式(4.2
6、)PX (K+1) = X (K) +a d (K)(k = 0,1,2,A )K可知，若某次选代中己取得点X(k)，从该点出发，取负梯度方向 Vf(X(k)为搜索方向。则最速下降法的迭代公式为X 心=X K 歯(k = 2 )2p当第k次的迭代初始点X(k)和搜索方向d(k)已经确定的情况下，原目标函数成为关于步长的一维函数。即甲(a)二 f (X (k)+a S ( k)rmin f(X (K) +ad (k) a最优步长a k可以利用一维搜索的方法求得rmin申(a) = f (X(k+1) = f (X(K)+a d(k)= aka根据一元函数极值的必要条件和多元复合函数的求导公式，得
7、0(a)=r(k) +ad(k) T Vf(X(k) = 0vf (X (K+1 )T Vf (X (K) = 0rr或写成d (K +1) t d (k) = 0由此可知，在最速下降法中相邻两个搜索方向互相正交。也就是说在用最速下降 法迭代求优的过程中，走的是一条曲折的路线，该次搜索方向与前一次搜索方向垂直， 形成“之”字形的锯齿现象，如图4.1 所示。最速下降法刚开始搜索步长比较大，愈 靠近极值点其步长愈小，收敛速度愈来愈慢。特别是对于二维二次目标函数的等值线 是较扁的椭圆时，这种缺陷更加明显。因此所谓最速下降是指目标函数在迭代点附近出现的局部性质，从迭代过程的全局来看，负梯度方向并非是目
8、标函数的最快搜索方向。图 4.1 最速下降法的搜索路径此外，最速下降法的迭代公式也可以写成下面的形式X(K+1)二 X(K)-a Vf (X(k)(k 二 0,1,2,L )(4.4)K将其与式4.3相比较，可知，此处a等于4.3式中步长除以函数在X(k)点导数的模 r k|Vf(X(k)|，而此时的搜索方向d(k)=Vf(X(k)也不再是个单位向量。4.1.2最速下降法的迭代过程1)2)给定初始点X (0)，收敛精度并令计算次数k u 0 ;计算X(k)点的梯度Vf (X(k)及梯度的模|Vf (X(k)|，并令Vf (X (k)3)判断是否满足精度指标|Vf(X(k)| ;若满足，X(k)
9、为最优点，迭代停止，输出最优解X* = X(k)和f (X*)二f (X(k),否则进行下一步计算； P)以X (k)为出发点，沿d (k)进行一维搜索，求能使函数值下降最多的步长minf(X(k) +ad(k) = f(X(k)+a d(k)r5)令X(k+i)= X(k)+a d(k),k = k + l,转到步骤 2)。K最速下降法的程序框图如图 4.2 所示。4.2 最速下降法的程序框图例题41用最速下降法求目标函数f(X) = (x -1)2 + (x -1)2的极小值，设初始点12X(0)= 0 0T，计算精度= 10-2。解(】)计算初始点X(0)处目标函数的梯度和梯度的模 芳(
10、X)dx1Of (X)dx2vf(X(0)=2(x -1)2(x -1)|vf (X (0)1 = 2 迈-2（2）由于|yf（X（0）| = 2迈e ,不满足精度指标，转下一步计算。（3）确定搜索方向yf（ x（0）|yf（ x（o）|rd (0)4）计算新的迭代点由公式（4.2）可得代入目标函数rX 二 X（0）+ad（o）二f (X )=_ 1 -a迈忑1aU2 M2P沿d（k）方向进行一维搜索（或对求导，并令其为零）df (X(1)da-1) +-1)令笛0巴=0，求得最优步长a 0 =；2。da0（5）计算新迭代点X（1）=11（6）计算新迭代点的梯度及梯度的模yf（ x（i）二2(
11、x -1)12(x -1)2因已满足精度要求，停止迭代，得最优解为f (X *)二 0可见，对于目标函数的等值线为圆的情况，只要一次迭代就能达到极小值点X *。这是因为圆周上任意一点的负梯度方向总是指向圆心的，如图4.3 所示。通过上面的分析可知最速下降法具有以下特点：（1）理论明确，程序简单，对初始点要求不严格，每次迭代所需的计算量和存储 量也较小，适用于计算机计算。（2）对一般函数而言，最速下降法的收敛速度并不快，因为最速下降方向仅仅是 指某点的一个局部性质。（3）最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯 齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度
12、较慢。（4）最速下降法的收敛速度与目标函数的性质以及初始点的选择密切相关。对于 等值线（面）为同心圆（球）的目标函数，一次搜索即可达到极小点。若目标函数为二次 函数，等值线为椭圆，当初始点选在长轴或短轴上时，一次搜索也可达到极小值点。 最速下降法的收敛速度和变量的尺度关系很大，这一点可从最速下降法收敛速度的估计式上看出来。在适当条件下，有W X II ) 此式是个二次函数，设X (k+1)为9 (X)的极小值点，则V申(X (k+1) = 0日nVf (X(k) + V2 f (X(k)(X(k+1) - X(k)二 0即X(K+l)= X(K) -V2f(X(K),1Vf (X(K)(k = 0,1,2L)(45)(4.5)这就是多元函数求极值的牛顿法迭代公式。式中取rd (k) = V 2 f ( X (K )-1 Vf ( X (K) )称为牛顿方向，为常数。式中没有步长a ，或者可以k看成步长恒等于1 ，所以牛顿法是一种定步长的迭代。例题4.4用牛顿法求目标函数f (X)二x2 + 25x2的极小值。12解(1)取初始点X(0)二2 2T(2)计算梯度、二阶偏导数矩阵及其逆矩阵Vf (X(o)=41002 x150x2(3)计算新的迭代点0501
