无约束条件下多变量函数寻优方法ppt课件

1、5-1 5-1 梯度法梯度法5-2 5-2 牛顿法牛顿法5-3 5-3 坐标轮换法坐标轮换法5-4 5-4 单纯形方法单纯形方法 1工程问题大都为有约束优化问题。为什么要研讨无约束优化问题? 1有些实践问题，其数学模型本身就是一个无约束优化问题。 2经过熟习它的解法可以为研讨约束优化问题打下良好的根底。 3约束优化问题的求解可以经过一系列无约束优化方法来到达。所以无约束优化问题的解法是优化设计方法的根本组成部分，也是优化方法的根底。2 目前已研讨出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 min( )nfRxx1间接法要运用导数，如梯度法、阻尼牛顿法、变尺度法、共轭梯度

2、法等。2直接法不运用导数信息，如坐标轮换法、鲍威尔法单纯形法等。无约束优化问题是：无约束优化问题是：12Tnx xxx求求n n维设计变量维设计变量( )minfx使目的函数使目的函数 31(0,1,2,)kkkkskxx搜索方向的构成问题乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。 用直接法寻觅极小点时，不用求函数的导数，只需计算目的函数值。这类方法较适用于处理变量个数较少的n 20问题，普通情况下比间接法效率低。间接法除要计算目的函数值外，还要计算目的函数的梯度，有的还要计算其海赛矩阵。 41(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkx

3、xx 根本思想：函数的负梯度方向是函数值在该点根本思想：函数的负梯度方向是函数值在该点下降最快的方向。将下降最快的方向。将n n维问题转化为一系列沿负梯度维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。搜索方向，故称最速下降法或梯度法。 ( )fx 搜索方向搜索方向s s取该点的负梯度方向取该点的负梯度方向 ( (最速下降方最速下降方向向) ) ，使函数值在该点附近的范围内下降最快，使函数值在该点附近的范围内下降最快 。5 为了使目的函数值沿搜索方向为了使目的函数值沿搜索方向 可以获可以获得最大

4、的下降值，其步长因子得最大的下降值，其步长因子 应取一维搜索的最应取一维搜索的最正确步长。即有正确步长。即有()kf xk1()()min ()min ( )kkkkkkaaffaffa f xxxxx根据一元函数极值的必要条件和多元复合函数求导公式，得根据一元函数极值的必要条件和多元复合函数求导公式，得 ( )()()0Tkkkkfff xxx1()()0kTkffxx1()0kTkss6 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。而搜数梯度相互垂直。而搜索方向就是负梯度方向，索方向就是负梯度方向，因此相邻两个搜索方向因此相邻两个搜索方向相互垂直

5、。这就是说在相互垂直。这就是说在迭代点向函数极小点接迭代点向函数极小点接近的过程，走的是曲折近的过程，走的是曲折的道路。构成的道路。构成“之字之字形的锯齿景象，而且越形的锯齿景象，而且越接近极小点锯齿越细。接近极小点锯齿越细。 图图5-2 5-2 最速下降法的搜索途径最速下降法的搜索途径78方法特点方法特点1 1初始点可任选，每次迭代计算量小，初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的存储量少，程序简短。即使从一个不好的初始点出发，开场的几步迭代，目的函数初始点出发，开场的几步迭代，目的函数值下降很快，然后渐渐逼近部分极小点。值下降很快，然后渐渐逼近部分极小点。 2

6、2恣意相邻两点的搜索方向是正交的，恣意相邻两点的搜索方向是正交的，它的迭代途径为绕道逼近极小点。当迭代它的迭代途径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越点接近极小点时，步长变得很小，越走越慢。慢。 9程序程序编写编写1000102()10424()50100 xfxfxxx沿负梯度方向进展一维搜索，有沿负梯度方向进展一维搜索，有01000024()2 100fxxx0为一维搜索最正确步长，应满足极值必要条为一维搜索最正确步长，应满足极值必要条件件 122()min (24 )25(2 100 )min ( )f x例例5 51 1 求目的函数求目的函数 的极小点。的极小点

7、。解解 取初始点取初始点那么初始点处函数值及梯度分别为那么初始点处函数值及梯度分别为02,2Tx2212( )25fxxx1100( )8(24)5 000(2 100)0 算出一维搜索最正确步长算出一维搜索最正确步长 06260.020 030 7231 252第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值 0120241.919 8772 1000.307178 5 10 x1()3.686164fx继续作下去，经继续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 00Tx()0fx12 这个问题的目的函数的等值线为一簇椭圆这个问题的目的函数的等值线为一簇椭圆, ,迭

8、代点从迭代点从 走的是一段锯齿形道路，见图走的是一段锯齿形道路，见图 。0 x13将上例中目的函数将上例中目的函数 引入变换引入变换2212( )25fxxx221212(,)y yyy其等值线由椭圆变成一簇同心圆。其等值线由椭圆变成一簇同心圆。 仍从仍从 即即 出发进展最速下降法寻优。此时：出发进展最速下降法寻优。此时：02,2Tx02,10Ty00102()10424()220yyyyy沿负梯度方向进展一维搜索：沿负梯度方向进展一维搜索：那么函数那么函数f(X)f(X)变为：变为：y1=x1, y2=5x2y1=x1, y2=5x2141000000()242410201020yyy 0

9、0为一维搜索最正确步长，可由极值条为一维搜索最正确步长，可由极值条件：件：10022()min ()min( )( )(24 )(1020 ) yyy0()0由由0260.552从而算得一步计算后设计点的位置及其目的函数：从而算得一步计算后设计点的位置及其目的函数：15010124010200()0 yy经变换后，只需一次迭代，就可找到最优解。经变换后，只需一次迭代，就可找到最优解。这是由于经过尺度变换：这是由于经过尺度变换：11225yxyx等值线由椭圆变成圆。等值线由椭圆变成圆。161 1实际明确，程序简单，对初始点要求不严厉。实际明确，程序简单，对初始点要求不严厉。2 2对普通函数而言，

10、梯度法的收敛速度并不快，由对普通函数而言，梯度法的收敛速度并不快，由于最速下降方向仅仅是指某点的一个部分性质。于最速下降方向仅仅是指某点的一个部分性质。3 3梯度法相邻两次搜索方向的正交性，决议了迭代梯度法相邻两次搜索方向的正交性，决议了迭代全过程的搜索道路呈锯齿状，在远离极小点时逼近速度全过程的搜索道路呈锯齿状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。较快，而在接近极小点时逼近速度较慢。4 4梯度法的收敛速度与目的函数的性质亲密相关。梯度法的收敛速度与目的函数的性质亲密相关。对于等值线对于等值线( (面面) )为同心圆球的目的函数，一次搜索为同心圆球的目的函数，一次搜索即可

11、到达极小点。即可到达极小点。172( )( )()() ()1()()()2kkTkkTkkffffxxxxxxxxxxx设设 为为 的极小点的极小点 1kx( )x1()0kx( )x( )x( )f x1kx( )f x21()()()0kkkkffxxxx18这就是多元函数求极值的牛顿法迭代公式。这就是多元函数求极值的牛顿法迭代公式。 对于二次函数对于二次函数 ，海赛矩阵，海赛矩阵 H H 是一个常矩阵，是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。只需一步就可找到极小点。 例例5 52 2 求目的函数求目的

12、函数 的极小点。的极小点。解：取初始点解：取初始点2212( )25fxxx02,2Tx102010102402()()121000050ff xxxx121()()(0,1,2,)kkkkffk xxxx1900 x()0fx 从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜索的概念。因此对于非二次函数，假设采用上的，其中并未含有沿下降方向搜索的概念。因此对于非二次函数，假设采用上述牛顿迭代公式，有时会使函数值上升述牛顿迭代公式，有时会使函数值上升 。阻尼牛顿法阻尼牛顿法 121()(

13、)(0,1,2,)kkkkkkkksffkxxxxxk阻尼因子阻尼因子 ，沿牛顿方向进展一维搜索的最，沿牛顿方向进展一维搜索的最正确步长，由下式求得：正确步长，由下式求得： 1()()min()kkkkkkkffsfsxxx经过一次迭代即求得极小点经过一次迭代即求得极小点函数极小值函数极小值20开始给定结束0,x21()()kkkff dxx1:min()kkkkkkkfxxdxd1kkxx*1kxx否是1kk0k 阻尼牛顿法程序框图21方法特点方法特点 1 1 初始点应选在初始点应选在X X* *附近，有一定难度；附近，有一定难度； 2 2 不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计

14、算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的计算量和存储量大。此外，对于二阶不可微的F(X)F(X)也不也不适用。适用。 虽然阻尼牛顿法有上述缺陷，但在特定条件下它虽然阻尼牛顿法有上述缺陷，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思绪和实具有收敛最快的优点，并为其他的算法提供了思绪和实际根据。际根据。221(0,1,2,)kkkkskxx1() (0,1,2,)kkkkafkxxx121()()(0,1,2,)kkkkffk xxxx121()()(0,1,2,)kkkkkffkxxxx普通迭代式：普通迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛

15、顿法：阻尼牛顿法：梯度法与牛顿法：梯度法与牛顿法：1()kkkkkfxxAx23 前面引见的优化方法，都需求计算目的函数的前面引见的优化方法，都需求计算目的函数的导数，而在实践工程的最优化问题中，目的函数的导导数，而在实践工程的最优化问题中，目的函数的导数往往很难求出或者根本无法求出。下面所引见的方数往往很难求出或者根本无法求出。下面所引见的方法只需求计算目的函数值，无需求其导数，因此计算法只需求计算目的函数值，无需求其导数，因此计算比较简单，其几何概念也比较明晰，属于直接法的无比较简单，其几何概念也比较明晰，属于直接法的无约束最优化方法。这类方法适用于不知道目的函数的约束最优化方法。这类方法

16、适用于不知道目的函数的数学表达式而仅知其详细算法的情况。这也是直接法数学表达式而仅知其详细算法的情况。这也是直接法的一个优点。的一个优点。2425 此法的效能在很大程度上取决于目的函数的性质。此法的效能在很大程度上取决于目的函数的性质。 261 1计算量少，程序简单，不需求求函数导数的直接计算量少，程序简单，不需求求函数导数的直接探求目的函数最优解的方法；探求目的函数最优解的方法；2 2探求道路较长，问题的维数愈多求解的效率愈低。探求道路较长，问题的维数愈多求解的效率愈低。当维数当维数n n1010时，那么不应采用此法。仅适用于时，那么不应采用此法。仅适用于n n较少较少n 10n 10的目的

17、函数求优；的目的函数求优； 3 3改动初始点重新迭代，可防止出现病态。改动初始点重新迭代，可防止出现病态。 2728一、根本思想一、根本思想 单纯形交换法也是一种不运用导数的求解单纯形交换法也是一种不运用导数的求解无约束极小化问题的直接搜索方法，与前面几种无约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形交换法不是利用搜索方向方法不同的是，单纯形交换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单从一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。纯形迭代到另一个更优的单纯形。29定义：单纯形定义：单纯形 n n 维空间中的恰好有维空间中的恰好有n+

18、1n+1个顶点极点的有个顶点极点的有界的凸多面体称之为一个单纯形。界的凸多面体称之为一个单纯形。 根据定义，可知，一维空间中的单纯形是线段，根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯二维空间中的单纯形是三角形，而三维空间中的单纯形那么是四面体。形那么是四面体。 在单纯形交换算法中，从一个单纯形到另一个在单纯形交换算法中，从一个单纯形到另一个单纯形的迭代主要经过反射、扩张、收缩和缩边这单纯形的迭代主要经过反射、扩张、收缩和缩边这4 4个操作来实现。下面以二维问题为例来对个操作来实现。下面以二维问题为例来对4 4种操作进种操作进展阐明参见以下图。展阐明

19、参见以下图。301 1反射反射设除了最劣点设除了最劣点X1X1以外的基余顶点的中心为以外的基余顶点的中心为X4X4，作作X1X1关于点关于点X4X4的对称点的对称点X5X5，称，称X5X5为为X1X1的反射点。求反射点的过的反射点。求反射点的过程称之为反射。程称之为反射。)()()(321XfXfXf2 2扩张扩张在得到反射点在得到反射点X5X5之后，假设之后，假设X5X5优于原单纯形的最劣优于原单纯形的最劣点即有点即有 ，阐明反射方向，阐明反射方向X5X1X5X1是有利方是有利方向，反射胜利。假设进一步有向，反射胜利。假设进一步有 ，可沿反射方向前，可沿反射方向前进适当的间隔到点进适当的间隔

20、到点X6X6。X6X6称之为扩张点，求扩张点的过程称之为称之为扩张点，求扩张点的过程称之为扩张。扩张之后，假设扩张点扩张。扩张之后，假设扩张点X6X6优于反射点优于反射点X5X5，那么扩张胜利，那么扩张胜利，以以X6X6取代取代X1X1，得新单纯形，得新单纯形X6,X2,X3X6,X2,X3；否那么，扩张失败，舍弃；否那么，扩张失败，舍弃扩张点，以反射扩张点，以反射X5X5点取代点取代X1X1，得新单纯形，得新单纯形X5,X2,X3X5,X2,X3。)()(15XfXf)()(25XfXf设当前的单纯形的顶点为设当前的单纯形的顶点为X1X1，X2X2，X3X3，且有，且有31)()()(251XfXfXf假设出现假设出