无约束优化方法

第四章无约束优化方法

4-1

最速下降法4-2牛顿类方法4-3坐标轮换法4-4

共轭方向法4-5

鲍威尔方法

为什么要研究无约束优化问题?

（1）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。（2）约束优化问题的求解可以通过一系列无约束优化方法来达到。第四章无约束优化方法

无约束优化问题标准形式：求n维设计变量使目标函数无约束优化问题极值存在的必要条件：目标函数（1）间接法（2）直接法搜索方向的构成问题乃是无约束优化方法的关键。无约束优化问题标准形式：§4-1

最速下降法

基本思想：函数的负梯度方向是函数值在该点下降最快的方向。利用负梯度作为搜索方向，故称最速下降法或梯度法。（梯度法）搜索方向s取该点的负梯度方向(最速下降方向)，使函数值在该点附近的范围内下降最快。§4-1

最速下降法为了使目标函数值沿搜索方向能够获得最大的下降值，其步长因子应取一维搜索的最佳步长。即有§4-1

最速下降法步长因子求解方法：解析法：根据极值点必要条件。黄金分割法牛顿法抛物线法§4-1

最速下降法最速下降法的搜索路径相邻两个搜索方向互相垂直§4-1

最速下降法

根据一元函数极值的必要条件及复合函数求导公式得在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。

图最速下降法的搜索路径§4-1

最速下降法图最速下降法的收敛过程§4-1

最速下降法方法特点（1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。（2）任意相邻两点的搜索方向正交，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。§4-1

最速下降法αα沿负梯度方向进行一维搜索，有例4－1求目标函数的极小点。取初始点解：初始点处梯度：沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

例4－1求目标函数的极小点。取初始点第一次迭代设计点位置和函数值

因此，迭代终止：

沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件

例4－2求目标函数的极小点。解取初始点则初始点处梯度：如何求？坐标轮换算出一维搜索最佳步长

第一次迭代设计点位置和函数值

继续作下去，经10次迭代后，得到最优解

坐标轮换这个问题的目标函数的等值线为一簇椭圆,迭代点从走的是一段锯齿形路线，见图。§4-1

最速下降法例4－3用梯度法求下面无约束优化问题：例4－3用梯度法求下面无约束优化问题：例4－3用梯度法求无约束优化问题：例4－3用梯度法求下面无约束优化问题：例4－3用梯度法求下面无约束优化问题：例4－3用梯度法求下面无约束优化问题：梯度法的特点（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，远快近慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。(b)(c)(a)优化前后图形对比梯度法应用的一个实例：4-2

牛顿类方法

基本思想：在xk邻域内用一个二次函数来近似代替原目标函数，并将的极小点作为对目标函数求优的下一个迭代点。经多次迭代，使之逼近目标函数的极小点。牛顿法是求函数极值的最古老算法之一。4-2

牛顿类方法设为的极小点

这就是多元函数求极值的牛顿法迭代公式。

例4－4求目标函数的极小点。解取初始点4-2

牛顿类方法例4－4求目标函数的极小点。解取初始点经过一次迭代即求得极小点函数极小值4-2

牛顿类方法例5、用牛顿法求解函数的极小值初始起始点[1，1]T。4-2

牛顿类方法对于正定二次函数，该方法可以直达极小点。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升。4-2

牛顿类方法阻尼牛顿法阻尼因子，沿牛顿方向进行一维搜索的最佳步长，由下式求得：

阻尼牛顿法程序框图（1）初始点应选在X*附近，有一定难度；（2）尽管每次迭代都不会是函数值上升，但不能保证每次下降；（3）若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向；

（4）

不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。特定条件下它具有收敛最快的优点阻尼牛顿法方法特点一般迭代式：梯度法：牛顿法：阻尼牛顿法：梯度法与牛顿法牛顿法和变尺度法§3.5牛顿法和变尺度法1.变尺度的基本思想：

发扬梯度法和牛顿法各自的优点，避免两者各自的缺点，将两者结合起来，形成变尺度法。§3.5牛顿法和变尺度法§3.5牛顿法和变尺度法构造变尺度矩阵的递推公式：修正矩阵:

变尺度法

DFP变尺度法现代公认的较好的算法之一。

DFP法、BFGS算法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。间接法：梯度法；牛顿法；变尺度法§4-3

坐标轮换法共同点：求导数直接法：直接用函数值搜索方向如何定？由于直接搜索是通过大量试验结果相比较而得最优解，因此计算时间比较长，且随着设计变量的增多，计算时间增加得很快。§4-3

坐标轮换法实践证明，在变量不超过10个的情况下，直接搜索法由于方法本身直观明确，易于被人所理解与掌握，虽然计算时间格长，但从使用者的角度来看，却比解析法更为个人满意。将一个多维的无约束最优化问题转化为一系列沿坐标轴方向的一维易优化间题央求解，因此也称降维法。§4-3

坐标轮换法基本原理

坐标轮换法的基本思想：是将一个n维优化问题转化为依次沿n个坐标方向反复进行一维搜索问题。

每次一维搜索时，只允许n个变量的一个改动，其余(n-1)个变量固定不变。

故坐标轮换法也常称单变量法或变量交错法。

§4-3

坐标轮换法§4-3

坐标轮换法例4－1求目标函数的极小点。取初始点分别用1）最速下降法

2）牛顿类方法

3）坐标轮换法求上题的最优点1）对于n个变量的函数，若在第k轮沿着第i个坐标方向进行搜索，其迭代公式为：2）求最优搜索步长计算步骤：3）本轮所有方向搜索完毕，判断迭代终止条件：4）满足上式：否则，进行下一轮迭代。例4－2求目标函数的极小点。取初始点梯度法解：第一轮迭代：求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：判断终止条件，不满足，进行第二轮迭代：求最优搜索步长求最优搜索步长沿着第二个坐标方向搜索：梯度法例3:用坐标轮换法求下面问题的最优解，给定初始点X0=[00]T,精度要求ε=0.1解:第一轮迭代求最优步长，即极小化：以X1(1)为新起点，沿e2方向进行一维搜索：仍以最优步长原则确定α2：继续进行第二轮迭代计算，等等。从坐标轮换法的迭代过程可以看出其搜索路线较长，计算效率低。因此，一般认为此法仅适宜n＜10的小型优化问题的求解。另外，此法的效能在很大程度上取决于目标函数的性质。按终止条件检验：坐标轮换法此法的效能在很大程度上取决于目标函数的性质。（1）计算量少，程序简单，不需要求函数导数的直接探索目标函数最优解的方法；（2）探索路线较长，问题的维数愈多求解的效率愈低。当维数n＞10时，则不应采用此法。仅适用于n较少（n<10）的目标函数求优；

（3）改变初始点重新迭代，可避免出现病态。方法特点

4-4共轭方向法1.共轭方向：设G为n×n阶实对称正定矩阵，如果有两个n维向量d0和d1满足，则称向量d0与d1

关于矩阵G共轭。当G为单位矩阵时，假设目标函数f(x)在极值点附近的二次近似函数为对二维情况任选取初始点x0沿某个下降方向d0作一维搜索，得x14-4共轭方向法因为是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有α0d0x0x1x*11α1d1d14-4共轭方向法如果按最速下降法，选择负梯度方向为搜索方向，则将发生锯齿现象。取下一次的迭代搜索方向d1直指极小点x*。α0d0x0x1x*11α1d1d14-4共轭方向法如果能够选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x*

，即有那么这样的d1方向应该满足什么条件呢?对于前述的二次函数:有4-4共轭方向法当时，x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘得：4-4共轭方向法就是使d1直指极小点x*

，d1所必须满足的条件。两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。4-4共轭方向法2.共轭方向的性质性质1

若非零向量系d0,d1,d2,…,dm-1是对G共轭，则这m个向量是线性无关的。性质2

在n维空间中互相共轭的非零向量的个数不超过n。

性质3

从任意初始点出发，顺次沿n个G的共轭方向d0,d1,d2,…,进行一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。

关键：新的共轭方向确定在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。

4-4共轭方向法3.共轭梯度法共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。从xk出发，沿负梯度方向作一维搜索:设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：共轭条件：3.共轭梯度法则：解得：3.共轭梯度法令为函数的泰勒二次展开式则上两式相减，并代入3.共轭梯度法将式与式两边相乘，并应用共轭条件得：3.共轭梯度法因此3.共轭梯度法，已知初始点[1,1]T例题4-4求下列问题的极值解：1）第一次沿负梯度方向搜寻计算初始点处的梯度迭代精度。为一维搜索最佳步长，应满足得:2）第二次迭代：代入目标函数得因收敛。由从而有：课堂练习：求目标函数的极小点。

取初始点用共轭梯度法解上题。（只计算搜索两次）4-5鲍威尔方法鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。

基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。

1.共轭方向的生成设xk,xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。

梯度和等值面相垂直的性质,

dj和

xk,

xk+1两点处的梯度gk,gk+1之间存在关系:4-5鲍威尔方法另一方面，对于上述二次函数，其xk,

xk+1两点处的梯度可表示为:4-5鲍威尔方法因而有取这说明只要沿dj方向分别对函作两次一维搜索，得到两个极小点xk和xk+1

，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。2.基本算法二维情况描述鲍威尔的基本算法:

1）任选一初始点x0，再选两个线性无关的向量，如坐标轴单位向量e1=[1,0]T和e2=[0,1]T作为初始搜索方向。x1x2x0oe1e2d1d2x*12.基本算法2）从x0出发，顺次沿e1，e1作一维搜索，得点，两点连线得一新方向d1x1x2x0oe1e2d1d2x*1x1x2x0oe1e2d1d2x*1用

d1代替e1形成两个线性无关向量d1,e2

，作为下一轮迭代的搜索方向。再从出发，沿d1作一维搜索得点，作为下一轮迭代的初始点。

3）从出发，→

e2,→

d1

作一维搜索，得到点，两点连线得一新方向:2.基本算法x1x2x0oe1e2d1d2x*1沿d2作一维搜索得点x2

。即是二维问题的极小点x*

。方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。2.基本算法要点：在每一轮迭代中总有一个始点和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。鲍威尔基本算法替换的原则:去掉原方向组的第一个方向而将新方向排在原方向的最后。规定:

从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。

鲍威尔基本算法例1、用鲍威尔分析函数的极小值，起始点[0，0]T。（板书）鲍威尔基本算法

上述基本算法仅具有理论意义

:如果需要替换，还要进一步判断原向量组中哪个向量最坏，然后再用新产生的向量替换这个最坏的向量，以保证逐次生成共轭方向。3.改进的鲍威尔方法在改进的算法中首先判断原向量组是否需要替换。为此，要解决两个关键问题：（1）dk＋1是否较好？是否应该进入新的方向组？即方向组是否进行更新？（2）如果应该更新方向组，dk＋1不一定替换方向，而是有选择地替换某一方向。3.改进的鲍威尔方法令在k次循环中（）分别称为一轮迭代的始点、终点和反射点。3.改进的鲍威尔方法则在循环中函数下降最多的第m次迭代是记：相应的方向为。因此3.改进的鲍威尔方法为了构成共轭性好的方向组，须遵循下列准则,在k次循环中，若满足条件：和则选用新方向dk，并在第k+1迭代中用dk替换对应于的方向。否则，仍然用原方向组进行第k+1迭代。3.改进的鲍威尔方法例4-5用改进的鲍威尔法求目标函数解：（1）第1轮迭代计算，沿e1方向进行一维搜索。的最优解。已知初始点[1,1]T，迭代精度例4-5用改进的鲍威尔法求目标函数，沿e1方向进行一维搜索得以为起点，沿第二坐标轴方向e2

进行一维搜索得确定此轮中的最大下降量及其相应方向

反射点及其函数值，

，检验Powell条件由于满足Powell条件，则淘汰函数值下降量最大的方向e1，下一轮的基本方向组为e2，。构成新的方向

沿方向一维搜索得极小点和极小值，此点为下轮迭代初始点。

按点距准则检验终止条件

需进行第二轮迭代计算。（2）第2轮迭代计算此轮基本方向组为e2，，分别相当于，，起始点为＝。沿e2方向进行一维搜索得

以为起点沿方向一维搜索得构成新的方