第四章无约束优化方法

第四章无约束优化方法1第一页，共五十九页，2022年，8月28日若存在则称X*点为无约束最优点，F(X)为无约束最优值。

直接搜索法：坐标轮换法、鲍威尔法方法

间接法：梯度法、牛顿法、变尺度法

直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长对于无约束优化问题:2第二页，共五十九页，2022年，8月28日4.1坐标轮换法基本思想：把一个n维无约束最优化问题转化为依次沿n个坐标轴方向的一维最优化问题。即迭代方向依次为:第一轮:任取一初始点X(0)

一维搜索求得一维搜索求得第二轮:3第三页，共五十九页，2022年，8月28日终止准则:上式点距准则中的两点应是一轮迭代的始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即:min{F(X(k)+αS(k))}=F(X(k)+α(k)S(k))迭代步长α的确定:4第四页，共五十九页，2022年，8月28日坐

标

轮

换

法

的

流

程

图

5第五页，共五十九页，2022年，8月28日坐标轮换法的特点:具有程序结构简单，易于掌握等优点。但收敛慢，适用于n<10的低维优化问题。另收敛速度与等值线的形状有关6第六页，共五十九页，2022年，8月28日例题4.1用坐标轮换法求目标函数的无约束最优解。给定初始点精度要求ε=0.1

解：作第一轮迭代计算。沿e1方向进行一维搜索

按最优步长原则确定步长α1，即极小化此问题可用某种一维优化方法求出α1。在这里，我们暂且借用微分学求导解出，令其一阶导数为零，α1=5

以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即极小化得α2=4.5，对于第一轮按终止条件检验7第七页，共五十九页，2022年，8月28日例题4.1对于第一轮按终止条件检验:继续第二轮迭代计算。以下各轮的计算结果列于表4.1。8第八页，共五十九页，2022年，8月28日例题4.1计算五轮后有故近似优化解为F*＝F(x*)=7.950259第九页，共五十九页，2022年，8月28日例题4.1用解析法验证

解:令正定10第十页，共五十九页，2022年，8月28日4.2鲍威尔(Powell)法鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设S1、S2、…、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数的极小点，从任意初始点出发，依次沿Si

（i=1，2，…，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点．11第十一页，共五十九页，2022年，8月28日2.5关于优化方法中搜寻方向的理论基础

2.5.2共轭方向(见第二章)一、共轭方向的基本概念若有两个n维矢量S1、S2，对n×n阶对称正定矩阵A能满足:称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。正交:可以看作是共轭的特例例:(1)共轭并正交12第十二页，共五十九页，2022年，8月28日例:(2)共轭但不正交设A为n×n阶实对称正定矩阵，有一组非零的n维矢量S1、S2、…、Sq，若满足

i≠j则称矢量系Si(i＝1，2，…，q≤n)对于矩阵A共轭

13第十三页，共五十九页，2022年，8月28日以二维函数为例:

二维正定二次函数具有两个重要特性：1）二维正定二次函数的等值线是同心的椭圆族，且椭圆中心就是正定二元二次函数的极小点。2)过同心椭圆族中心x*作任意直线，此直线与诸椭圆交点处的切线相互平行。或者说：两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中心。可以证明上诉S1和S2方向是关于矩阵A的共轭方向。14第十四页，共五十九页，2022年，8月28日S1与S2是对A共轭的一对矢量证明：设直线方程为代入F(X),并关于α求极值即结论:两个平行方向的极小点构成的新方向与原方向相互共轭即S1与S2对A共轭也即对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.15第十五页，共五十九页，2022年，8月28日与此类似，可以推出对于n维正定二次函数，共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，…Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。共轭矢量之所以引起优化研究者的重视，就是因为它的这些性质对提高优化方法的收敛速率极为有用。

16第十六页，共五十九页，2022年，8月28日例设二维目标函数，给定方向S1＝e2，初始点，求与S1相共轭的S2，并求函数的极小点。解：(1)第一个搜索方向(2)函数的海赛矩阵对称正定(3)从点沿S1方向求极小点x(1)，即

17第十七页，共五十九页，2022年，8月28日例解：(4)任取另初始点沿S1方向一维搜索求得该方向极小点x(2)

X(2)=

(5)求与S1相共轭的方向S2S2=X(2)-X(1)=

核验计算

矢量S1与S2确为对A矩阵共轭。

(6)从x(1)点出发，沿S2方向作一维搜索，得极小点X*=[00]T

18第十八页，共五十九页，2022年，8月28日4.2.1鲍威尔基本算法（共轭方向的原始构成）19第十九页，共五十九页，2022年，8月28日4.2.1鲍威尔基本算法任取一初始点X(0)→

X0(1)第一环:

e1,e2,e3→

S1第二环:

e2,e3,S1→

S2第三环:

e3,S1,

S2→S3第一轮

S1,

S2

,S3

两两共轭由前结论:两个平行方向的极小点构成的新方向与原方向相互共轭20第二十页，共五十九页，2022年，8月28日4.2.1鲍威尔基本算法第一环:

e1,e2,e3→

S1第二环:

e2,e3,S1→

S2第三环:

e3,S1,

S2→S3第一轮S1是e1,e2,e3的线性组合S2是e2,e3,S1的线性组合S3是e3,S1,

S2的线性组合新一环方向组:e2,e3,S1线性相关!降维21第二十一页，共五十九页，2022年，8月28日鲍威尔法的基本思想:

对原始共轭方向法进行修正,即在某环已取得的n+1个方向中,选取n个线性无关,共轭程度尽可能高的方向作为下一环的基本方向组,从而避免出现“退化”现象.鲍威尔法与原始共轭方向法的主要区别是：在构成K+1环基本方向组时，不再总是淘汰前一环(K环)中的第一个方向，而是根据条件式是否得到满足分两种情况来处理。4.2.1鲍威尔修正算法22第二十二页，共五十九页，2022年，8月28日映射点一、Powell

修正算法的搜索方向

Powell

判别式23第二十三页，共五十九页，2022年，8月28日情况一：

Powell

判别式中若至少有一个不等式成立，则第K+1环的方向组仍用老方向组

初始点:当F2<F3时,当F2≥F3时,情况二：

Powell

判别式中若两个不等式均不成立，则第K+1环的方向组去掉函数值下降最大的方向,补上新增的方向初始点:24第二十四页，共五十九页，2022年，8月28日

以二维为例:两条件式至少有一成立且F2<F3两条件式至少有一成立且F2>F3

25第二十五页，共五十九页，2022年，8月28日两条件式均不成立且m=1

两条件式均不成立且m=226第二十六页，共五十九页，2022年，8月28日终止准则:采用了上述产生基本方向组的新方式后，除了第一环以单位坐标矢量系为基本方向组外，以后每轮开始就不必重置单位坐标矢量系，只要一环接一环继续进行即可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。因此，这个修正了的鲍威尔算法，虽然已不再像基本算法那样具有二次收敛的性质，但修正算法确实克服了退化的不利情形，同时仍能够有效地、越来越快地收敛于无约束最优点x*。二、修正算法的迭代步骤及流程图映射点27第二十七页，共五十九页，2022年，8月28日28第二十八页，共五十九页，2022年，8月28日试用鲍尔修正算法求目标函数

的最优解。迭代精度ε=0.001。

已知初始点解：第一环迭代计算

沿第一坐标方向e1进行一维搜索沿第二坐标轴方向e2进行一维搜索

29第二十九页，共五十九页，2022年，8月28日例题沿s1方向一维搜索得极小点与极小值

需进行第二环迭代计算。第二环迭代计算：首先确定上环中的最大函数下降量及其相应方向

映射点及其函数值30第三十页，共五十九页，2022年，8月28日检验鲍尔条件鲍威尔条件两式均不成立。第二环基本方向组和起始点为沿e2方向作一维搜索得沿S1方向一维搜索得

构成新生方向沿S2方向一维搜索得去掉函数值下降最大的方向,补上新增的方向初始点取新增方向的极小点31第三十一页，共五十九页，2022年，8月28日例题4.2检查迭代终止条件需再作第三环迭代计算。根据具体情况来分析，S1、S2实际上为共轭方向的（见图4.9）。本题又是二次函数，按共轭方向的二次收敛性质，上面的结果就是问题的最优解。可以预料，如果作第三环迭代，则一定各一维搜索的步长为零，必有故得最优解32第三十二页，共五十九页，2022年，8月28日解:令正定

用解析法验证

得:33第三十三页，共五十九页，2022年，8月28日鲍威尔法的特点:

是到目前为止求解无约束优化问题的最有效的方法。不需求导数,只需计算目标函数值。适用中、小型问题。34第三十四页，共五十九页，2022年，8月28日梯度法的基本思想:利用函数在其负梯度方向函数值下降最快这一局部性质，将n维无约束优化问题转化为一系例的沿目标函数负梯度方向的一维寻优问题。4.3梯度法终止准则:取：所以：35第三十五页，共五十九页，2022年，8月28日例题4.3用梯度法求目标函数F(x)=+25的最优解。已知初始点x(0)＝[22]T，迭代精度取ε=0.005。解：函数的梯度第一次迭代：以x(0)为起点沿-g(0)方向作一维搜索初始点函数梯度值:第一点函数梯度值:36第三十六页，共五十九页，2022年，8月28日37第三十七页，共五十九页，2022年，8月28日解:令正定得:

用解析法验证

38第三十八页，共五十九页，2022年，8月28日梯度法的特点:

几何概念直观,方法和程序简单,远离极小点时收敛速度快。但越接近极小点收敛速度越慢。39第三十九页，共五十九页，2022年，8月28日原始牛顿法基本思想：

在点x(k)

领域内用一个二次函数Φ（x)去近似代替原目标函数F(x)，然后求出这个二次函数的极小点，以该点作为对原目标函数求优的下一个选代点x(k+1），这样通过重复若干次迭代，使迭代点逐步逼近原目标函数的极小点X*

。

4.5牛顿法

40第四十页，共五十九页，2022年，8月28日注意：与一维优化方法的二次插值法的不同每次迭代所用的二次函数就是在迭代点展开的泰勒二次多项式

41第四十一页，共五十九页，2022年，8月28日4.5.1原始牛顿法一元函数f(x)在x(k)点的泰勒展开式：n元函数F(X)在X(k)点的泰勒展开式：42第四十二页，共五十九页，2022年，8月28日即:牛顿方向:(定步长)等号两边左乘为求极小点,令一阶导数等于零由前：即迭代方向：:43第四十三页，共五十九页，2022年，8月28日牛顿法具有二次收敛性。对于二次正定函数，迭代一次即可到达最优点；对于非二次函数，若函数的二次性态较强或迭代点已进入最优点的较小邻域，则其收敛速度也是很快的。但原始牛顿法还存在一个问题：由于在全部迭代过程中，取步长α(k)≡1，这种定步长有时造成函数值反而有所增大。44第四十四页，共五十九页，2022年，8月28日

阻尼牛顿法基本思想:阻尼牛顿法的迭代方向仍是上述牛顿方向，但每次迭代需沿此方向作一维搜索，求其最优步长因子,即迭代公式为：

4.5.2阻尼牛顿法45第四十五页，共五十九页，2022年，8月28日46第四十六页，共五十九页，2022年，8月28日例题4.5用牛顿法求函数F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10的最优解。初始点x(0)＝[00]T，ε＝10－5。解：函数的梯度海赛矩阵及其逆在x(0)点处47第四十七页，共五十九页，2022年，8月28日沿S(0)方向一维搜索求最优步长得代入函数解得：α(0)=1故新迭代点为该点的梯度满足终止条件，迭代即可结束48第四十八页，共五十九页，2022年，8月28日补充:求逆矩阵称作矩阵A的伴随方阵,中元素

是中元素的代数余子式

划去所在行列后余下的n-1阶子式例:49第四十九页，共五十九页，2022年，8月28日解:令正定

用解析法验证

F(x)＝4(x1＋1)2＋2(x2－1)2＋x1＋x2＋10

得:50第五十页，共五十九页，2022年，8月28日牛顿法的特点：牛顿法具有二次收敛性，对正定二次函数一次迭代即可达到极小点。对目标函数性态较好或当初始点取在极小点附近时收敛速度快。但对目标函数有较高的要求，必须存在一阶、二阶偏导数，H（x(k)）需正定且非奇异。计算复杂，计算量大。51第五十一页，共五十九页，2022年，8月28日梯度法和牛顿法对比方法梯度法牛顿法迭代公式迭代方向稳定下降性肯定能保证稳定下降须H(X)处处正定才能稳定下降收敛速度离X*远时下降速度较快,离近时下降很慢离X*近时收敛很快二次收敛性不具有二次收敛性具有二次收敛性52第五十二页，共五十九页，2022年，8月28日观察梯度法和牛顿法的迭代式：

变尺度法的基本思想：设法构造一个对称正定阵Ak代替,并在选代计算中，使其逐渐逼近。因此，一旦达到极值点附近，就可望达到牛顿法的收敛速度，同时又避免了矩阵的求逆计算。其选代公式：Ak是是根据需要构造的n×n阶对称矩阵，它是随着迭代点位置的变化而变化的。

梯度法:牛顿法:4.6DFP变尺度法53第五十三页，共五十九页，2022年，8月28日

4.6.2变尺度法构造矩阵的产生递推方法产生:校正矩阵

变尺度法采用构造矩阵来代替牛顿法中海赛矩阵的逆阵