《机械优化设计无约束优化方法.ppt》由会员分享，可在线阅读，更多相关《机械优化设计无约束优化方法.ppt（101页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 无约束优化方法无约束优化方法 4-14-1 最速下降法（梯度法）最速下降法（梯度法）4-2 4-2 牛顿类方法牛顿类方法4-3 4-3 变尺度法变尺度法4-4 4-4 共轭方向法共轭方向法4-54-5 鲍威尔方法鲍威尔方法4-64-6 其它方法（如坐标轮换法、单纯形法）其它方法（如坐标轮换法、单纯形法）第第1章章所所列列举举的的机机械械优优化化设设计计问问题题，都都是是在在一一定定的的限限制制条条件件下下追追求求某某一一指指标标为为最最小小，它它们们都都属属于于约约束束优优化化问题。工程问题大都如此。问题。工程问题大都如此。为什么要研究无约束优化问题为什么要研究无约束优化问题为什
2、么要研究无约束优化问题为什么要研究无约束优化问题?（1）有有些些实实际际问问题题，其其数数学学模模型型本本身身就就是是一一个个无无约约束束优化问题。优化问题。（2）通通过过熟熟悉悉它它的的解解法法可可以以为为研研究究约约束束优优化化问问题题打打下下良好的基础。良好的基础。（3）约约束束优优化化问问题题的的求求解解可可以以通通过过一一系系列列无无约约束束优优化化方方法法来来达达到到。所所以以无无约约束束优优化化问问题题的的解解法法是是优优化化设设计计方法的基本组成部分，也是优化方法的基础。方法的基本组成部分，也是优化方法的基础。（4）对对于于多多维维无无约约束束问问题题来来说说，古古典典极极值值
3、理理论论中中令令一一阶阶导导数数为为零零，但但要要求求二二阶阶可可微微，且且要要判判断断海海赛赛矩矩阵阵为为正正定定才才能能求求得得极极小小点点，这这种种方方法法有有理理论论意意义义，但但无无实实用用价价值值。和和一一维维问问题题一一样样，若若多多元元函函数数F(X)不不可可微微，亦亦无无法法求求解解。但但古古典典极极值值理理论论是是无无约约束束优优化方法发展的基础。化方法发展的基础。目前已研究出很多种无约束优化方法，它们的目前已研究出很多种无约束优化方法，它们的主要不同点在于主要不同点在于构造搜索方向构造搜索方向上的差别。上的差别。（1）间接法）间接法要使用导数，如梯度法、（阻尼）要使用导数
4、，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。牛顿法、变尺度法、共轭梯度法等。（2）直接法）直接法不使用导数信息，如坐标轮换法、不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。鲍威尔法单纯形法等。无约束优化问题是：无约束优化问题是：求求n维设计变量维设计变量使目标函数使目标函数 搜索方向的构成问题乃是无约束优化方法的关键。搜索方向的构成问题乃是无约束优化方法的关键。用直接法寻找极小点时，不必求函数的导数，只要计用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的算目标函数值。这类方法较适用于解决变量个数较少的（n20）问题，一般情况下比间接法效
5、率低。间接法除）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。还要计算其海赛矩阵。4-1 4-1 梯度法梯度法 基本思想基本思想：函数的负梯度方向是函数值在该点：函数的负梯度方向是函数值在该点下降最快的方向。将下降最快的方向。将n n维问题转化为一系列沿负梯度维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。搜索方向，故称最速下降法或梯度法。搜索方向搜索方向s取该点的负梯度方向取该点的负梯
6、度方向(最速下降方最速下降方向向)，使函数值在该点附近的范围内下降最快，使函数值在该点附近的范围内下降最快。为为了了使使目目标标函函数数值值沿沿搜搜索索方方向向 能能够够获获得得最最大大的的下下降降值值，其其步步长长因因子子 应应取取一一维维搜搜索索的的最最佳佳步长。即有步长。即有根据一元函数极值的必要条件和多元复合根据一元函数极值的必要条件和多元复合函数求导公式，得函数求导公式，得 在最速下降法中，在最速下降法中，相邻两个迭代点上的函相邻两个迭代点上的函数梯度相互垂直。而搜数梯度相互垂直。而搜索方向就是负梯度方向，索方向就是负梯度方向，因此相邻两个搜索方向因此相邻两个搜索方向互相垂直。这就是
7、说在互相垂直。这就是说在迭代点向函数极小点靠迭代点向函数极小点靠近的过程，走的是曲折近的过程，走的是曲折的路线。形成的路线。形成“之之”字字形的锯齿现象，而且越形的锯齿现象，而且越接近极小点锯齿越细。接近极小点锯齿越细。图图4-1最速下降法的搜索路径最速下降法的搜索路径方法特点方法特点（1 1）初始点可任选，每次迭代计算量小，存储）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。然后慢慢逼近局部极小点。（2 2）任意相邻两点
8、的搜索方向是正交的，它的）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。小点时，步长变得很小，越走越慢。s sk k沿负梯度方向进行一维搜索，有沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件为一维搜索最佳步长，应满足极值必要条件例例4 41 1 求目标函数求目标函数 的极小点。的极小点。解解 取初始点取初始点则初始点处函数值及梯度分别为则初始点处函数值及梯度分别为算出一维搜索最佳步长算出一维搜索最佳步长第一次迭代设计点位置和函数值第一次迭代设计点位置和函数值继续作下去，经继
9、续作下去，经1010次迭代后，得到最优解次迭代后，得到最优解 这个问题的目标函数的等值线为一簇椭圆这个问题的目标函数的等值线为一簇椭圆,迭代点从迭代点从走的是一段锯齿形路线，见图走的是一段锯齿形路线，见图4-2。1 1图图4-2将上例中目标函数将上例中目标函数引入变换引入变换其其等值线由椭圆变成一簇同心圆。等值线由椭圆变成一簇同心圆。仍从仍从即即出发进行最速下降法出发进行最速下降法寻优。此时：寻优。此时：沿负沿负梯度方向进行一维搜索：梯度方向进行一维搜索：则函数则函数f(f(X X)变为：变为：y1=x1,y2=5x2为一维为一维搜索最佳步长，可由极值条件：搜索最佳步长，可由极值条件：由由从而
10、算得一步计算后设计点的位置及其目标函数：从而算得一步计算后设计点的位置及其目标函数：经经变换后，只需一次迭代，就可找到最优解。变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换：这是因为经过尺度变换：等值线由椭圆变成圆。等值线由椭圆变成圆。梯度法的特点梯度法的特点l（1）理论明确，程序简单，对初始点要求不严格。）理论明确，程序简单，对初始点要求不严格。l（2）对一般函数而言，梯度法的收敛速度并不快，因）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个为最速下降方向仅仅是指某点的一个局部性质局部性质。l（3）梯度法相邻两次搜索方向的正交性，决定了迭代）梯度法相邻
11、两次搜索方向的正交性，决定了迭代全过程的搜索路线呈全过程的搜索路线呈锯齿锯齿状，在远离极小点时逼近速度状，在远离极小点时逼近速度较快，而在接近极小点时逼近速度较慢。较快，而在接近极小点时逼近速度较慢。l（4）梯度法的收敛速度与目标函数的性质密切相关。）梯度法的收敛速度与目标函数的性质密切相关。对于等值线对于等值线(面面)为同心圆（球）的目标函数，一次搜索为同心圆（球）的目标函数，一次搜索即可达到极小点。即可达到极小点。4-2 -2 牛顿法及其改进牛顿法及其改进设设 为为 的极小点的极小点基本思想基本思想：在在xk邻邻域内用一个二次函数域内用一个二次函数来近似代替原目来近似代替原目标标函数，并将
12、函数，并将的极小点作的极小点作为对为对目目标标函数函数求求优优的下一个迭代点的下一个迭代点。经经多次迭代，使之逼近目多次迭代，使之逼近目标标函数函数的极小点。的极小点。牛牛顿顿法是求函数极法是求函数极值值的最古老算法之一。的最古老算法之一。这就是多元函数求极值的牛顿法迭代公式。这就是多元函数求极值的牛顿法迭代公式。对于二次函数对于二次函数，海赛矩阵海赛矩阵H H是一个常矩阵，其是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。只需一步就可找到极小点。例例4 42 2 求目标函数求目标函数 的极小点。的极小点。解解 取初始
13、点取初始点 从牛顿法迭代公式的推演中可以看到，迭代点从牛顿法迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升用上述牛顿迭代公式，有时会使函数值上升。阻尼牛顿法阻尼牛顿法阻尼因子阻尼因子，沿牛顿方向进行一维搜索的最佳沿牛顿方向进行一维搜索的最佳步长，由下式求得：步长，由下式求得：经过一次迭代即求得极小点经过一次迭代即求得极小点函数极小值函数极小值阻尼牛顿法程序框图方法特点方法特点（1）初始点应选在初始
14、点应选在X*附近，有一定难度；附近，有一定难度；（2）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；不能构造牛顿法方向；（3）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的计算量和存储量大。此外，对于二阶不可微的F(X)也也不适用。不适用。虽然阻尼牛顿法有上述缺点，但在特定条件下它虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛最快的优点，并为其他的算法提供了思路和具有收敛最快的优点，并为其他的算法提供了思路和理论依据。理论依据。一般迭代式：一般迭代式：梯度
15、法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：梯度法与牛顿法：梯度法与牛顿法：4-3 变尺度法变尺度法DFP变尺度法首先有戴维顿（变尺度法首先有戴维顿（Davidon）与鲍维）与鲍维尔（尔（Powell）于）于1959年提出，又于年提出，又于1963年由弗莱彻年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。的较好的算法之一。DFP法是基于牛顿法的思想又作了重要改进。这法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛矩阵及其逆矩阵，种算法仅用到梯度，不必计算海赛矩阵及其逆矩阵，但又能使搜索方向逐渐
16、逼近牛顿方向，具有较快的收但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。敛速度。1.基本思想基本思想2.变量的尺度变换是放大或缩小各个坐标。通过变量的尺度变换是放大或缩小各个坐标。通过尺尺3.度变换可以把函数的偏心程度降到最低限度。度变换可以把函数的偏心程度降到最低限度。例如在用最速下降法求例如在用最速下降法求的极小的极小值时值时,需要需要进进行行10次迭代才能达到极小点次迭代才能达到极小点如作变换如作变换y1=x1,y2=5x2把把的尺度放大的尺度放大5倍，则目标函数等值线由一簇倍，则目标函数等值线由一簇椭圆变成一簇同心圆。椭圆变成一簇同心圆。x2消除了函数的偏心，用最速下降法只需一
17、次迭消除了函数的偏心，用最速下降法只需一次迭代即可求得极小点。代即可求得极小点。梯度法构造简单，只用到一阶偏导数，计算量小，梯度法构造简单，只用到一阶偏导数，计算量小，初始点可任选，且开始几次迭代，目标函数值下降很初始点可任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭代点接近快；其主要缺点是迭代点接近X*时，即使对二次正定时，即使对二次正定函数收敛也非常慢。函数收敛也非常慢。牛顿法收敛很快，对于二次函数只需迭代一次便牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点，对非二次函数也能较快迭代到最优点，达到最优点，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩阵及其逆阵，对维
18、数较高的优但要计算二阶偏导数矩阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太大。化问题，其计算工作和存储量都太大。能不能将两种算法的优点综合起来，扬长避短？能不能将两种算法的优点综合起来，扬长避短？Ak是需要构造是需要构造nn的一个对称方阵的一个对称方阵，如如Ak=I,则得到梯度法则得到梯度法；则得到阻尼牛顿法则得到阻尼牛顿法；如如当矩阵当矩阵Ak不断地迭代而能很好地逼近不断地迭代而能很好地逼近时，就可以不再需要计算二阶导数。时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵变尺度法的关键在于尺度矩阵Ak的产生的产生。对于二次函数对于二次函数:进行尺度变换进行尺度变换在在新的
19、坐标系中，函数新的坐标系中，函数f(x)的二次项变为：的二次项变为：目的：减少二次项的偏心目的：减少二次项的偏心如如G是正定，则总存在矩阵是正定，则总存在矩阵Q，使得：使得：用矩阵用矩阵Q-1右乘等式两边，得：右乘等式两边，得：用用矩阵矩阵Q左乘等式两边，得：左乘等式两边，得：所以所以上式上式说明：二次函数矩阵说明：二次函数矩阵G的逆阵，可以通过尺度变换的逆阵，可以通过尺度变换矩阵矩阵Q来求得。来求得。牛顿迭代公式：牛顿迭代公式：记：记：搜索方向：搜索方向：迭代公式：迭代公式：A A 称为变尺度矩阵称为变尺度矩阵在例在例42中中如取如取求得：求得：2.构造尺度矩阵构造尺度矩阵构造尺度矩阵构造尺
20、度矩阵A Ak k从初始矩阵从初始矩阵A0=I(单位矩阵单位矩阵)开始，通过对公式开始，通过对公式因此，一旦达到最优点附近，就可望达到牛顿法因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度的收敛速度。1）DFP法（法（Davidon-Fletcher-Powell)式中式中中修正矩阵中修正矩阵 的不断修正，在迭代中逐步逼近于的不断修正，在迭代中逐步逼近于。2 2）BFGSBFGS算法算法算法算法(BroydenBroydenBroydenBroyden-Fletcher-Gold-Fletcher-Gold-Fletcher-Gold-Fletcher-Gold frob-frob-fro
21、b-frob-ShannoShannoShannoShanno)lDFP算法由于舍入误差和一维搜索不精确，有可算法由于舍入误差和一维搜索不精确，有可能导致构造矩阵的正定性遭到破坏，以至算法不稳能导致构造矩阵的正定性遭到破坏，以至算法不稳定。定。BFGS算法对于维数较高问题具有更好的稳定算法对于维数较高问题具有更好的稳定性。性。例例4-3：用用DFP算法求下列问题的极值：算法求下列问题的极值：l解：解：1）取初始点）取初始点，为了按，为了按DFP法构造第法构造第一次搜寻方向一次搜寻方向d0，需计算初始点处的梯度需计算初始点处的梯度取初始变尺度矩阵为单位矩阵取初始变尺度矩阵为单位矩阵A0=I，则第
22、一次则第一次搜寻方向为搜寻方向为l沿沿d0方向进行一维搜索，得方向进行一维搜索，得为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足得得:,2）再按）再按DFP法构造点法构造点x1处的搜寻方向处的搜寻方向d1，需计算需计算代入校正公式代入校正公式=第二次搜寻方向为第二次搜寻方向为再沿再沿d1进行一维搜索，得进行一维搜索，得为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足,得得3）判断判断x2是否为极值点是否为极值点梯度梯度:海赛矩阵海赛矩阵:梯度为零向量梯度为零向量,海赛矩阵正定。可见点满足极值海赛矩阵正定。可见点满足极值充要条件，因此为极小点。充要条件，因此为极小点。4-4 共轭方向法
23、共轭方向法 l1.共共轭方向：轭方向：l设设G为为nn阶实对称正定矩阵，如果有两个阶实对称正定矩阵，如果有两个n维维向量向量d0和和d1满足满足，则称向量，则称向量d0与与d1关关于矩阵于矩阵G共共轭。轭。当当G为单位矩阵时为单位矩阵时，假设目标函数假设目标函数f(x)在极值点附近的二次近似函数为在极值点附近的二次近似函数为对二维对二维情况情况任选取初始点任选取初始点x0沿某个下降方向沿某个下降方向d d0 0作一维搜索，得作一维搜索，得x1 因因为为 是是沿沿d0方方向向搜搜索索的的最最佳佳步步长长，即即在在点点x1处处函函数数f（x）沿沿方方向向d0的的方方向向导导数数为为零零。考考虑虑到
24、到点点x1处方向导数与梯度之间的关系，故有处方向导数与梯度之间的关系，故有如果按最速下降法，选择负梯度方向如果按最速下降法，选择负梯度方向 为搜为搜索方向，则将发生锯齿现象索方向，则将发生锯齿现象。取下一次的迭代搜索方向取下一次的迭代搜索方向d1直指极小点直指极小点x*。0d0 x0 x1x*1 11d1d1l如如果果能能够够选选定定这这样样的的搜搜索索方方向向，那那么么对对于于二二元元二二次次函函数数只只需需顺顺次次进进行行d0、d1两两次次直直线线搜搜索索就就可可以以求求到到极小点极小点x*，即有即有那么这样的那么这样的d1方向应该满足什么条件呢方向应该满足什么条件呢?对于前述的二次函数对
25、于前述的二次函数:当当时，时，x*是是f(x)极小点，应满足极值必要条件，故有极小点，应满足极值必要条件，故有将等式两边同时左乘将等式两边同时左乘得得：有有 就是使就是使d1直指极小点直指极小点x*，d1所必须满足的条件所必须满足的条件。两两个个向向量量d0和和d1称称为为G的的共共轭轭向向量量，或或称称d0和和d1对对G是共轭方向。是共轭方向。2.2.共轭方向的性质共轭方向的性质性性质质1 1 若若非非零零向向量量系系d0,d1,d2,dm-1是是对对G共共轭轭，则这则这m个向量是线性无关的。个向量是线性无关的。性质性质2 2 在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量
26、的个数不超过不超过n。性质性质3 3 从任意初始点出发，顺次沿从任意初始点出发，顺次沿n个个G的共轭方的共轭方向向d0,d1,d2,进行一维搜索，最多经过进行一维搜索，最多经过n次迭代次迭代就可以找到的二次函数就可以找到的二次函数f(x)极小点。极小点。关键：新的共关键：新的共轭方向轭方向确定确定在无约束方法中许多算法都是以共轭方向在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方共轭方向的原理不同，可以形成不同的共轭方向法。向法。3.3.3.3.共轭梯度法共轭梯度法共轭梯度法共轭梯度法l
27、共轭梯度法是共轭方向法中的一种，该方法中共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。而构造出来。l 从从xk出发，沿负梯度方向作一维搜索出发，沿负梯度方向作一维搜索:设与设与dk共共轭的下一个方向轭的下一个方向dk+1由由dk和点和点xk+1的负的负梯梯度的线形组合构成，即：度的线形组合构成，即：共轭条件：共轭条件：l则：则：解解得：得：令令为为函数的泰勒二次展开式函数的泰勒二次展开式则则上两式相上两式相减，并代入减，并代入将式将式与式与式两边相乘，并应用两边相乘，并应用共轭条件共轭条件得：得：因此因此，已
28、知初始点，已知初始点1,11,1T T例题例题4-4求下列问题的极值求下列问题的极值l解：解：1）第一次沿负梯度方向搜寻）第一次沿负梯度方向搜寻l计算初始点处的梯度计算初始点处的梯度为一维搜索最佳步长，应满足为一维搜索最佳步长，应满足l迭代精度迭代精度 。得得:2）第二次迭代：）第二次迭代：代入代入目标函数目标函数得得因因收敛。收敛。由由从而有：从而有：一般迭代式：一般迭代式：梯度法：梯度法：牛顿法：牛顿法：阻尼牛顿法：阻尼牛顿法：优化方法的演化优化方法的演化变尺度法：变尺度法：变尺度法：变尺度法：0d0 x0 x1x*1 11d1d1共轭梯度法：共轭梯度法：共轭梯度法：共轭梯度法：梯度法：梯
29、度法：4-5鲍威尔方法鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。快的直接法之一，是一种十分有效的算法。1964年，鲍维尔提出这种算法，其基本思想年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践方向作一维搜索求极小点。并在以后的实践中进行了改进。中进行了改进。对函数：对函数：基本思想基本思想：在不用导数的前提下，在迭代中逐次构造：在不用导数的前提下，
30、在迭代中逐次构造G的共轭方向。的共轭方向。1.1.共轭方向的生成共轭方向的生成jjkkkdd ddjgg gk+1xxk+1设设xk,xk+1为从不同为从不同点出发，沿同一方向点出发，沿同一方向dj j进行一维搜索而到进行一维搜索而到的两个极小点。的两个极小点。l梯度和等值面相垂直的性质梯度和等值面相垂直的性质,dj j和和 xk,xk+1两点两点处的梯度处的梯度gk,gk+1之间存在关系之间存在关系:另另一一方方面面，对对于于上上述述二二次次函函数数，其其xk,xk+1两两点点处处的的梯度可表示为梯度可表示为:因而有因而有取取这这说说明明只只要要沿沿dj j方方向向分分别别对对函函作作两两次
31、次一一维维搜搜索索，得得到到两两个个极极小小点点xk和和xk+1 ，那那么么这这两两点点的的连连线线所所给出的方向给出的方向dk k就是与就是与dj j一起一起对对G共轭的方向。共轭的方向。2.2.2.2.基本算法基本算法基本算法基本算法l二维情况描述鲍威尔的基本算法二维情况描述鲍威尔的基本算法:1 1）任任选选一一初初始始点点x0，再再选选两两个个线线性性无无关关的的向向量量，如如坐坐标标轴轴单单位位 向向 量量 e1 1=1,0=1,0T T和和e e2 2=0,1=0,1T T作作 为为 初初 始始搜索方向。搜索方向。2 2）从从x0出出发发，顺顺次次沿沿e1 1，e2 2作一维搜索，得
32、作一维搜索，得 点点，两两点点连连线线得一新方向得一新方向d1 1x1x2x0oe1e2d1d2x*1x1x2x0o oe1e2d1d2x*1沿沿d2作一维搜索得点作一维搜索得点x2。即是二维问题的极即是二维问题的极小点小点x*。方法的基本迭代格式包括共方法的基本迭代格式包括共轭方向产生和方向替换两轭方向产生和方向替换两主要步骤。主要步骤。用用d1代替代替e1 1形成两个线性无关向量形成两个线性无关向量e2 2,d1 ，作为，作为下一轮迭代的搜索方向。再下一轮迭代的搜索方向。再 从出发，沿从出发，沿d1作一作一维搜索得点维搜索得点 ，作为下一轮迭代的初始点。，作为下一轮迭代的初始点。3 3）从
33、从出出发发 ，顺顺次次沿沿e2 2,d1作作一一维维搜搜索索，得得到到点点 ，两两点点连连线得一新方向线得一新方向:l 把二维情况的基本算法扩展到把二维情况的基本算法扩展到n维，则鲍威尔维，则鲍威尔基本算法的要点是：基本算法的要点是：l 在每一轮迭代中总有一个始点（第一轮的始点在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和是任选的初始点）和n个线性独立的搜索方向。从个线性独立的搜索方向。从始点出发顺次沿始点出发顺次沿n个方向作一维搜索得一终点，由个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。始点和终点决定了一个新的搜索方向。l 用这个方向替换原来用这个方向替换原来n
34、个方向中的一个，于是个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。组的第一个方向而将新方向排在原方向的最后。此外规定，从这一轮的搜索终点出发沿新的搜索此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。代的始点。这样就形成算法的循环。上述基本算法仅具有理论意义上述基本算法仅具有理论意义上述基本算法仅具有理论意义上述基本算法仅具有理论意义。l 因为在迭代中的因为在迭代中的n个搜索方向有时会变成
35、线性个搜索方向有时会变成线性相关而不能形成共轭方向。这时组不成相关而不能形成共轭方向。这时组不成n维空间，维空间，可能求不到极小点，所以上述基本算法有待改进。可能求不到极小点，所以上述基本算法有待改进。3.3.改进的算法改进的算法 在鲍威尔基本算法中，每一轮迭代都用连结始在鲍威尔基本算法中，每一轮迭代都用连结始点和终点所产生出的搜索方向去替换原向量组中的点和终点所产生出的搜索方向去替换原向量组中的第一个向量，而不管它的第一个向量，而不管它的“好坏好坏”，这是产生向量，这是产生向量组线性相关的原因所在。组线性相关的原因所在。在在改改进进的的算算法法中中首首先先判判断断原原向向量量组组是是否否需需
36、要要替替换换。如如果果需需要要替替换换，还还要要进进一一步步判判断断原原向向量量组组中中哪哪个个向向量量最最坏坏，然然后后再再用用新新产产生生的的向向量量替替换换这这个最坏的向量，以保证逐次生成共轭方向。个最坏的向量，以保证逐次生成共轭方向。l为此，要解决两个关键问题为此，要解决两个关键问题：l（1）dk1是否较好？是否应该进入新的方向组是否较好？是否应该进入新的方向组？即方向组是否进行更新？即方向组是否进行更新？l（2）如果应该更新方向组，）如果应该更新方向组，dk1不一定替换方不一定替换方向向，而是有选择地替换某一方向，而是有选择地替换某一方向。令在令在k次循环中次循环中（）分别称为一轮迭
37、代的始点、终点和反射点分别称为一轮迭代的始点、终点和反射点。l则在循环中函数下降最多的第则在循环中函数下降最多的第m次迭代是次迭代是记记：相应的方向为相应的方向为。为了构成共为了构成共轭性好的方向组，须遵循下列准则：轭性好的方向组，须遵循下列准则：在在k次循环中，若满足条件：次循环中，若满足条件：和和则则选用新方向选用新方向dk+1，并在第并在第k+1迭代中用迭代中用dk+1替换对应于替换对应于的方向的方向。否则，仍然用原方向组进行第。否则，仍然用原方向组进行第k+1迭代。迭代。因此因此l 这样重复迭代的结果，后面加进去的向量都这样重复迭代的结果，后面加进去的向量都彼此对彼此对G共轭，经共轭，
38、经n轮迭代即可得到一个由轮迭代即可得到一个由n个共轭个共轭方向所组成的方向组。对于二次函数，最多方向所组成的方向组。对于二次函数，最多n轮就轮就可找到极小点，而对一般函数，往往要超过可找到极小点，而对一般函数，往往要超过n轮才轮才能找到极小点（这里能找到极小点（这里“n”表示设计空间的维数）。表示设计空间的维数）。l例例4-5 4-5 用改进的鲍威尔法求目标函数用改进的鲍威尔法求目标函数解：（解：（1 1）第）第1 1轮迭代计算轮迭代计算，沿沿e1方向进行一维搜索方向进行一维搜索得得。l的最优解。已知初始点的最优解。已知初始点1,11,1T T，迭代精度迭代精度以以为起点，沿第二坐标轴方向为起
39、点，沿第二坐标轴方向e2进行一维进行一维搜索搜索得得确定此轮中的最大下降量及其相应方向确定此轮中的最大下降量及其相应方向 反射点及其函数值反射点及其函数值，检验检验PowellPowell条件条件由于满足由于满足PowellPowell条件，则淘汰函数值下降量最条件，则淘汰函数值下降量最大的方向大的方向e1，下一轮的基本方向组为下一轮的基本方向组为e2，。构成新的方向构成新的方向沿沿方向一维搜索得极小点和极小值方向一维搜索得极小点和极小值，此点为下轮迭代初始点。此点为下轮迭代初始点。按点距准则检验终止条件按点距准则检验终止条件需进行第二轮迭代机算。需进行第二轮迭代机算。l（2 2）第）第2 2
40、轮迭代计算轮迭代计算此此轮轮基基本本方方向向组组为为e2，分分别别相相当当于于，起始点为起始点为。沿沿e2方向进行一维搜索得方向进行一维搜索得以以 为起点沿为起点沿方向一维搜索得方向一维搜索得确定此轮中函数值最大下降量及其相应方向确定此轮中函数值最大下降量及其相应方向l反射点及其函数值反射点及其函数值检验检验Powell条件，淘汰函数值下降量最大的方向条件，淘汰函数值下降量最大的方向d d1 1即即e2，下一轮的基本方向组应为，下一轮的基本方向组应为 ，。构成新的方向构成新的方向沿沿方向进行一维搜索得方向进行一维搜索得l检验终止条件检验终止条件（3 3）第）第3 3轮迭代计算轮迭代计算此此轮轮
41、基基本本方方向向组组为为 ，起起始始点点为为，先先后沿后沿，方向，进行一维搜索，得方向，进行一维搜索，得，故最优解故最优解检验终止条件检验终止条件l 实实际际上上，前前两两轮轮迭迭代代的的 ，为为共共轭轭方方向向，由由于于本本例例目目标标函函数数是是二二次次函函数数，按按共共轭轭方方向向的的二二次次收收敛敛性性，故故前前两两轮轮的的结结果果就就是是问问题题的的最最优优解解，但但每每一一轮轮迭迭代代都都进进行行n+1次迭代。次迭代。前面介绍的许多优化方法，除鲍威尔（前面介绍的许多优化方法，除鲍威尔（Powell）法外，都需要计算目标函数的导数，而在实际工程的法外，都需要计算目标函数的导数，而在实
42、际工程的最优化问题中，目标函数的导数往往很难求出或者根最优化问题中，目标函数的导数往往很难求出或者根本无法求出。下面所介绍的方法只需要计算目标函数本无法求出。下面所介绍的方法只需要计算目标函数值，无需求其导数，因此计算比较简单，其几何概念值，无需求其导数，因此计算比较简单，其几何概念也比较清晰，属于直接法的无约束最优化方法。这类也比较清晰，属于直接法的无约束最优化方法。这类方法适用于不知道目标函数的数学表达式而仅知其具方法适用于不知道目标函数的数学表达式而仅知其具体算法的情况。这也是直接法的一个优点。体算法的情况。这也是直接法的一个优点。4-6其它方法（如坐标轮换法、单纯形法）其它方法（如坐标
43、轮换法、单纯形法）坐标轮换法坐标轮换法坐坐坐坐标标标标轮轮轮轮换换换换法法法法的的的的基基基基本本本本思思思思想想想想：是是将将一一个个n维维优优化化问问题题转转化化为为依依次次沿沿n个个坐坐标标方方向向反反复复进进行行一一维维搜搜索索问问题题。这这种种方方法法的的实实质质是是把把n维维问问题题的的求求优优过过程程转转化化为为对对每每个个变变量量逐逐次次进进行行一一维维求求优优的的循循环环过过程程。每每次次一一维维搜搜索索时时，只只允允许许n个个变变量量的的一一次次改改动动，其其余余(n-1)个个变变量量固固定定不不变变。故故坐坐标标轮轮换换法法也也常常称称单单变量法或变量交错法。变量法或变量
44、交错法。坐标轮换法坐标轮换法此法的效能在很大程度上取决于目标函数的性质。此法的效能在很大程度上取决于目标函数的性质。（1）计算量少，程序简单，不需要求函数导数的直接）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。）探索路线较长，问题的维数愈多求解的效率愈低。当维数当维数n10时，则不应采用此法。仅适用于时，则不应采用此法。仅适用于n较少（较少（n0，模矢加速搜索的加速步长，模矢加速搜索的加速步长因子为因子为a1（通常取（通常取a=2），迭代终止准则为），迭代终止准则为(为预先确定的正数）。为预先确
45、定的正数）。（1 1）（2 2）（3 3）若）若（2 2）；否则，转（）；否则，转（4 4）否则转（否则转（6 6）否则，令否则，令（6 6）否则，否则，转（，转（2 2）（5）（4 4）转（转（5 5）；）；0d0 x0 x1x*1 11d1d1共轭梯度法：共轭梯度法：共轭梯度法：共轭梯度法：梯度法：梯度法：鲍威尔鲍威尔(Powell)法法jjkkkdd ddjgg gk+1xxk+1共轭法共轭法共轭法共轭法直接法直接法直接法直接法鲍威尔法原理，鲍威尔法原理，如何构成共轭方向？如何构成共轭方向？！坐标轮换法坐标轮换法坐标轮换法坐标轮换法直接法直接法直接法直接法步长加速法（步长加速法（步长加速
46、法（步长加速法（Hook-ReevesHook-Reeves算法）算法）算法）算法）单纯形方法单纯形方法一、基本思想一、基本思想单纯形替换法也是一种不使用导数的求解无单纯形替换法也是一种不使用导数的求解无约束极小化问题的直接搜索方法，与前面几种方约束极小化问题的直接搜索方法，与前面几种方法不同的是，单纯形替换法不是利用搜索方向从法不同的是，单纯形替换法不是利用搜索方向从一个点迭代到另一个更优的点，而是从一个单纯一个点迭代到另一个更优的点，而是从一个单纯形迭代到另一个更优的单纯形。形迭代到另一个更优的单纯形。定义：单纯形定义：单纯形 n维空间中的恰好有维空间中的恰好有n+1个顶点（极点）的有界的
47、个顶点（极点）的有界的凸多面体称之为一个单纯形。凸多面体称之为一个单纯形。根据定义，可知，一维空间中的单纯形是线段，根据定义，可知，一维空间中的单纯形是线段，二维空间中的单纯形是三角形，而三维空间中的单纯二维空间中的单纯形是三角形，而三维空间中的单纯形则是四面体。形则是四面体。在单纯形替换算法中，从一个单纯形到另一个单在单纯形替换算法中，从一个单纯形到另一个单纯形的迭代主要通过反射、扩张、收缩和缩边这纯形的迭代主要通过反射、扩张、收缩和缩边这4个操个操作来实现。下面以二维问题为例来对作来实现。下面以二维问题为例来对4种操作进行说明种操作进行说明（参见下图）。（参见下图）。8（1 1）反射）反射
48、设除了最劣点设除了最劣点X X1 1以外的基余顶点的中心为以外的基余顶点的中心为X X4 4，作，作X X1 1关于点关于点X X4 4的对称点的对称点X X5 5，称，称X X5 5为为X X1 1的反射点。求反射点的过程称的反射点。求反射点的过程称之为反射。之为反射。（2 2）扩张）扩张在得到反射点在得到反射点X X5 5之后，如果之后，如果X X5 5优于原单纯形的最劣优于原单纯形的最劣点（即有点（即有 ），表明反射方向（），表明反射方向（X X5 5X X1 1）是有利方向，）是有利方向，反射成功。若进一步有反射成功。若进一步有 ，可沿反射方向前进适当，可沿反射方向前进适当的距离到点的
49、距离到点X X6 6。X X6 6称之为扩张点，求扩张点的过程称之为扩张。扩称之为扩张点，求扩张点的过程称之为扩张。扩张之后，若扩张点张之后，若扩张点X X6 6优于反射点优于反射点X X5 5，则扩张成功，以，则扩张成功，以X X6 6取代取代X X1 1，得，得新单纯形新单纯形XX6 6,X,X2 2,X,X3 3；否则，扩张失败，舍弃扩张点，以反射；否则，扩张失败，舍弃扩张点，以反射X X5 5点点取代取代X X1 1，得新单纯形，得新单纯形XX5 5,X,X2 2,X,X3 3。设当前的单纯形的顶点为设当前的单纯形的顶点为X X1 1，X X2 2，X X3 3，且有，且有如果出现如果
50、出现 。表示反射完全失败，应退回到介于。表示反射完全失败，应退回到介于X X4 4与与X X1 1之间的某个点之间的某个点X X8 8。（3 3）收缩）收缩在得到反射点在得到反射点X X5 5之后，如果有之后，如果有表示反射部分成功，方向（表示反射部分成功，方向（X X5 5X X1 1）虽然是有利方向，但）虽然是有利方向，但X X5 5前前进过远，应收缩到介于进过远，应收缩到介于X X4 4与与X X5 5之间的某个点之间的某个点X X7 7。上述两种从反射点向上述两种从反射点向X1方向后退的过程都称之为收缩。方向后退的过程都称之为收缩。如果收缩点优于原来的最劣点如果收缩点优于原来的最劣点X