4第四章-无约束优化方法new

第四章 无约束优化方法,最速下降法 牛顿型方法 共轭方向及共轭方向法 共轭梯度法 变尺度法 坐标轮换法 Powell法,无约束优化方法是优化技术中基本的也是非常重要的内容。无约束优化问题的数学模型 求上述问题最优解（x*,F*）的方法，称为无约束优化方法 使用无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的研究给约束优化方法建立明确的概念、提供良好的基础·某些优化设计方法就是先把约束优化设计问题转化为无约束问题后，再直接用无约束优化方法求解。,无约束优化理论研究开展得较早，构成的优化方法巳很多 ，也比较成熟，新的方法仍在陆续出现。本章的内容与目的 是讨论儿个常用无约束优化方法的基本思想、方法构成、迭 代步骤以及终止准则等方面问题。,在n维无约束优化方法的算法中，用函数的一阶、二价导数进行求解的算法，称为解析法，如最速下降法、共轭梯度法、牛顿法及变尺度法等;,无约束优化方法总体分成两大类型:解析法或称间接法、 直接搜索法或简称直接法；,对于n维优化问题，如果只利用函数值求最优值的解法，称 为直接搜索法，如坐标轮换法、单形替换法及Powell法等；,解析法的收敛速率较高，直接法的可靠性较高。,无约束优化方法算法的基本过程是:从选定的某初始点x(k)出发，沿着以一定规律产生的搜索方向d(k) ,取适当的步长a(k) ,逐次搜寻函数值下降的新迭代点x(k+1),使之逐步通近最优点x* 。可以把初始点x(k) 、搜索方向d(k) 、迭代步长a(k) 称为优化方法算法的三要素。其中以搜索方向d(k)更为突出和重要，它从根本上决定若一个算法的成败、收敛速率的快慢等。所以·一个算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向d(k)是研究优化方法的最根本的任务之一。各种无约束优化方法的区别就在于确定其搜索方向d(k) 的方法不同。,4.2 最速下降法 函数最速下降方向，在优化设计理论中占有重要地位。 函数负梯度方向f(x) 必为函数最速下降方向。按此规律， 可以形成以下的迭代算法 xk+1=xk kf(xk) (k = 0, 1, 2, ) 由于最速下降法是以负梯度方向作为搜索方向， 所以又称为梯度法。 步长k应取一维搜索的最佳步长。即有 求极值，得 因此，最速下降法中， 相邻两个迭代点上的函数梯 度互相垂直。 而搜索方向就是负梯度方向， 因此相 邻两个搜索方向互相垂直。,例4-1 求目标函数f(x)=x12+25x22的极小点。 解： 取初始点x0 = 2,2T 则初始点处函数值及梯度分别为 沿负梯度方向进行一维搜索， 有 0为一维搜索最佳步长， 应满足极值必要条件 从而 0 = 0.02003072,并得到第一次迭代设计点位置和函数值 到此完成最速下降法的第一次迭代。 如是经过10次迭代，可得到最优解 目标函数的等值线为一族椭圆， 迭代点从x0走到最优点经过的 是一段锯齿形路线。见图4-3.,将目标函数f(x)=x12+25x22引入变换 y1=x1, y2=5x2 则函数f(x1, x2)成为 (y1, y2)= y12+y22, 其等值线变为一族同心圆,见图4-4。 仍从x0 = 2,2T即y0 = 2,10T出发进行最速下降法寻优， 此时有 沿负梯度 方向进行一维搜索，有,0为一维搜索最佳步长，可由极值条件算出 0 =26/52= 0.5 从而算得第一次走步后设/计点的位置及其相应的 目标函数值为 仅一次迭代即获得最优解,可见上面两个二次型中间的对角形矩阵不同。即两个二次型函数的对角形矩阵刻画了椭圆的长短轴， 它们是表示度量的矩阵或者是表示尺度的矩阵。 而最速下降法的收敛速度和变量尺度关系很大。在适当条件下，有 M为目标函数的海赛矩阵最大特征值上界， m为最小特征值下界。 对于f(x)=x12+25x22，m = 2, M = 50 可见等值线为椭圆的长短轴相差越大， 收敛就越慢。 对于(y1, y2)= y12+y22， m = M = 2 即经过一次迭代可到达极值点,4.3 牛顿型方法 一维情况的牛顿迭代公式 k+1 = k f (k)/ f (k) k = 0, 1, 2, 对于多元函数f(x), 设xk为f(x)极小点x*的一个近似点， 在xk处将f(x)进行泰勒展开， 保留到二次项， 得到 式中-2f(xk)为函数在xk点处的海赛矩阵。 设xk+1为（x）的极小点， 它作为f(x)极小点x*的下一个近似点， 根据极值必要条件 此即多元函数求极值的牛顿法迭代公式。 对于二次函数f(x), 上述泰勒展开式是精确的，海赛矩阵为常矩阵，从任何点出发，只需一次迭代就可找到极小点，因此本方法是二次收敛的。,例4-2 用牛顿法求f(x)=x12+25x22的极小点。 解： 取初始点x0 = 2,2T 则初始点处函数梯度、海赛矩阵及其逆阵分别为 代入牛顿法迭代公式，得 从而经过一次迭代求得极小点x*=0 0T及函数极小值f(x*)=0. 同学们可以把初始点换成x0 = 4,5T计算一下看看结果。,阻尼牛顿法 从牛顿法迭代公式可以看出，迭代点的位置时按照极值条件确定，并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用牛顿法迭代公式，有时会使函数值上升，出现f(xk+1)f(xk)的现象。为此，提出“阻尼牛顿法”。 把d k = 2f(xk) 1 f(xk) 看作是一个搜索方向，称其为牛顿方向，则阻尼牛顿法采取如下的迭代公式 式中 k 为沿牛顿方向进行一维搜索的最佳步长，成为阻尼因子。 k可通过下述极小化过程求得 阻尼牛顿法每次迭代都在牛顿方向上进行一维搜索，避免了迭代后函数值上升的现象，从而保持了牛顿法的二次收敛性，而对初始点的选择没有要求。,阻尼牛顿法的计算步骤 1）给定初始点x0，收敛精度，置k0。 2）计算f(xk) 、 2f(xk) 、2f(xk) 1和d k = 2f(xk) 1 f(xk) 。 3）求xk+1=xk kdk, 其中 k为沿dk进行一维搜索的最佳步长。 4）检查收敛精度。若|xk+1-xk| 则x* = xk+1,停机；否则，置k k+1, 回到步骤2）继续进行搜索。,牛顿法和阻尼牛顿法统称为牛顿型方法。这类方法的优点是收敛快。缺点也很突出，表现在以下3个方面。 1）不能保证每次迭代都是函数值下降； 2）若目标函数在点x(k)处的海赛矩阵奇异，其逆阵不存在，就不能构成牛顿方向，迭代无法进行。 3）构造牛顿方向较困难。每次迭代需计算函数的梯度，海赛矩阵及其逆阵，这样计算和编制程序都很复杂，而且占用计算机内存也大。 因此需要找出一种方法，能像梯度法那样，只需计算目标函数，对初始点的要求不高，能较好地突破函数的非二次性而迅速趋近于极值点，同时又像牛顿法那样，一旦迭代点进入极值点的邻近区域时很快地收敛于最优点。,4.4 共轭方向和共轭方向法,为了克服最速下降法的锯齿现象以提高其收敛速度，发展了 一类共轭方向法。,一，共轭方向的基本概念,首先以二元二次函数为例予以说明共轭方向概念，设函数,式中,2*2阶对称 正定矩阵,二元二次函数的等值线为一组椭圆，任选初始点x0沿某个下降方向d0作一维搜索，得x1 = x0 + 0d0。0是沿d0方向搜索的最佳步长，即在x1点处函数f(x)沿d0方向的方向导数为零。故有 d0与某一等值线相切于x1点。为了避免按最速下降法出现的锯齿现象，可取下一次的迭代搜索方向d1直指极小点x*，如图所示。既有x* = x1+ 1d1 1为d1方向上的最佳步长。,二次函数f(x)在x1点的梯度为f(x1)=Gx1 + b 当x1 x*时1 0，由于x*是函数f(x)的极小点，应有 f(x*) = Gx*+b = 0 即 f(x*) = G(x1 + 1d1)+b = f(x1) + 1Gd1 = 0 等式两边同时左乘(d0)T, 整理，得 (d0)TGd1=0 这就是为使 d1 直指极小点x*, d1所必须满足的条件。满足上式得两个向量d0, d1称为G的共轭向量，或者说d0, d1对G是共轭的。,二、共轭方向的性质 定义 设G是nn阶对称正定矩阵，若维空间中有m个非零向量d0， d1， dm-1满足 (di)TGdj = 0 (i, j = 0, 1, 2, ,m-1) (ij) （4-11） 则称d0， d1， dm-1对G共轭，或称它们是G的共轭方向。 当G = I(单位矩阵）时，式（4-11）变成 (di)Tdj = 0 (ij) 即向量d0， d1， dm-1互相正交。由此知，共轭概念是正交概念的推广，正交是共轭的特例。 性质1 若非零向量d0， d1， dm-1对G共轭，则这m个向量线性无关。 性质2 在n维空间中相互共轭的非零向量的个数不超过n。 性质3 从任意初始点x0出发，顺此沿n个G的共轭方向d0， d1， dm-1进行一维搜索，最多经过n次迭代就可以找到二次函数 的极小点。此性质表明本迭代方法具有二次收敛性。,三、共轭方向法 建立在性质3的基础上，提供了求二次函数极小点的原则方法。 1）选定初始点x0, 下降方向d0和收敛精度，置k0。 2）沿d k 方向进行一维搜索，得xk+1 = xk + kd k. 3) 判断|f(xk+1)| 是否满足，满足则打印xk+1，停机，否则转4。 4）提供新的共轭方向dk+1, 使(dj)T Gdk+1 = 0, j = 0, 1, 2, ,k. 5) 置kk+1, 转2。,共扼方向法程序框图如图4-8所示。,格拉姆-斯密特（Gram-Schmidt）向量系共轭化方法 设已选定线性无关向量系v0, v1, , vn-1 (例如，它们是n个坐标轴上的单位向量），首先 取d0 = v0 令 d1 = v1 + 10d0 其中10 是待定系数，它根据d1与d0共轭条件来确定，即 从而求得与d0共轭的 设已求得共轭向量d0, d1, ,dk， 现求dk+1。 令,为使dk+1与dj (j = 0, 1, 2, , k) 共轭，应有 得 于是,例4-3 求 的一组共轭向量d0, d1, d2。 解：选三个坐标轴上的单位向量e0、e1、e2作为一组线性无关向量系,取,设,得,设,得,计算表明,说明d0, d1, d2对G共轭。,上述算法是针对二次函数的，对于非二次函数，在极小点可以用二次函数来近似 上式中的海赛矩阵相当于二次函数中的矩阵G，但x*未知。当迭代点x0充分靠近x*时，可用G(x0)构造共轭向量系。 下一节将讨论构造共轭向量系时如何避开海赛矩阵。,4.5 共轭梯度法,共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。 对于二次函数,4.5 共轭梯度法 共轭梯度法是共轭方向法的一种，因为该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称作共轭梯度法。 对于二次函数 从xk点出发，沿G的某一个共轭方向dk作一位搜索，到达dk+1点，即 xk+1 = xk + kdk 在 xk、 xk+1点处的梯度gk、gk+1分别为 所以有 (a) 若dj和dk对G是共轭的，则有 (dj)TGdk = 0 利用式(a)对两端左乘(dj)T，有 (b) 此即共轭方向与梯度之间的关系。,此式表示沿方向dk进行一维搜索，其终点xk+1与始点xk的梯度之差gk+1 gk 与dk的共轭方向dj正交。共轭梯度法就是利用这个性质做到不必计算矩阵G就能求得共轭方向的。此性质的几何说明如图4-9所示。,共轭梯度法的计算过程如下