第三章 无约束最优化方法2.doc

第七节 变尺度法（拟牛顿法）变尺度法是无约束最优化方法发展过程中非常有影响的重要研究成果，它的基本思想是基于有很好收敛速度的牛顿法。但又避免了计算二阶导数矩阵及其求逆计算，又比共轭梯度法有更好的收敛速度，被认为是求最优化问题的最有效的算法之一。牛顿法的缺点：计算复杂（一阶、二阶偏导数）、对函数的性态要求高（对海赛矩阵要求、对初始点的选择要求）一、变尺度法的基本原理一）范数和尺度函数图象联系了函数和几何，表达两个数之间的变化关系，映射推广了函数的概念，使得自变量不再仅仅局限于一个数，也不再局限于一维，任何事物都可以拿来作映射，维数可以是任意维，传统的函数图象已无法直观地表达高维对象之间的映射关系，这就要求我们在观念中，把三维的几何空间推广到抽象的n维空间。由于映射的对象可以是任何事物，为了便于研究映射的性质以及数学表达，我们首先需要对映射的对象进行“量化”，取定一组“基”，确定事物在这组基下的坐标，事物同构于我们所熟悉的抽象几何空间中的点，事物的映射可以理解为从一个空间中的点到另一个空间的点的映射，而映射本身也是事物，自然也可以抽象为映射空间中的一个点。范数是把一个事物映射到非负实数，且满足非负性、齐次性、三角不等式，符合以上定义的都可以称之为范数，所以，范数的具体形式有很多种（由内积定义可以导出范数，范数还也可以有其他定义，或其他方式导出）。从一个线性空间到另一个线性空间的线性映射，可以用一个矩阵来表达，矩阵被看线性作映射，线性映射的性质可以通过研究矩阵的性质来获得。平面解析几何中一个向量的长度的定义：它具有非负性、齐次性和三角不等式三个基本性质。向量范数定义 一个从到的非负函数叫做上的向量范数，如果满足：（1） 正定性：对所有的有，而且当且仅当；（2） 齐次性：对所有的和有；（3） 三角不等式：对所有的有.向量x与y之间的距离可定义为的x-y范数，即常用范数最常用的范数就是p-范数。若x=x1,x2,.,xnT，那么 xp=(|x1|p+|x2| p +.+|xn| p) 1/p 可以验证p-范数确实满足范数的定义。当p取1，2，的时候分别是以下几种最简单的情形： 1-范数：x1=x1+x2+xn 2-范数：x2=(x12+x22+xn2)1/2 -范数：x=max(x1,x2,xn) 其中2-范数就是通常意义下的距离。 1-范数意义下的“单位圆”和第一象限的“单位球”2-范数意义下的“单位圆”和第一象限的“单位球”-范数意义下的“单位圆”和第一象限的“单位球”若，它的欧式范数（或模）定义为向量X和Y的差X-Y的范数是X和Y两个向量终点的距离，而和也表示它们自身始点到终点的距离，因此可以用距离来解释范数。这个概念和尺度空间中尺度概念是一致的，故范数可以成为尺度。这个概念可以推广，如A是任何一个nn阶实对称正定矩阵，定义也是一种向量范数（非欧式范数）。梯度法沿最速下降方向进行搜索，收敛性不好牛顿方向进行搜索，可以直接指向极小点。这种改进的实质是：牛顿法是对二次函数进行了变换，使其在新坐标系中减小偏心率。例 原坐标中的尺度（范数）是新坐标系尺度是牛顿法是改变范数（尺度）之后的最速下降法。二）变尺度矩阵的概念梯度法迭代公式为牛顿迭代公式为原坐标中的尺度（范数）是新坐标系尺度是尺度的改变决定于A。梯度法和牛顿法的迭代公式可以统一写成式中为迭代方向，若为单位矩阵，则表示梯度法，若，则表示阻尼牛顿法。牛顿法虽然收敛速度快，但在多数情况下，求二阶偏导数及其逆矩阵是相当的繁复困难，为了克服这一缺点，希望新的度量公式去产生搜索方向，于是引入了变尺度的思想，并在1957年以后提出和发展了一类搜索方法，称之为变尺度法。它的基本思想是：利用牛顿法的迭代形式，用一个对称正定矩阵来代替，并在迭代过程中，使其逐渐逼近。在这个过程中，尺度的改变决定于矩阵A，故为变尺度矩阵。是逐渐逼近的一个序列，它的值依赖于迭代次数，故每确定一个搜索方向，度量即改变一次，这是变尺度方法名称的由来。三）构造的原则1、下降性也就是说方向必须是函数值下降的方向，所以它与方向的夹角必须小于90，即，构造的矩阵必须是正定矩阵。2、收敛性产生的迭代方向是关于矩阵相互共轭的，这样算法才具有二次收敛性。3、方便性希望矩阵具有以下递推形式：式中校正矩阵，要求它计算简便，只依赖于本次迭代的、和相应的梯度向量、。三）构造的途径先分析一下海赛矩阵和梯度之间的关系，以便寻求构造近似矩阵的途径。函数梯度 式中 （）则有：令 这是海赛矩阵应当满足的相关公式，而对于第K次迭代，要求趋近于。所以也应满足：这是在构造时应当满足的条件，称为变尺度条件，也称为拟牛顿条件。二、DFP变尺度法Davidon 1959年首先提出Fletcher、Powell 1963年对之进行改进 DFP一）迭代公式式中校正矩阵由于为上一迭代点，已知，因此转为求校正矩阵的问题。要求它计算简便，只依赖于本次迭代的、和相应的梯度向量、，即依赖于和。、为两个待定向量，且满足以下条件 *、可以表示为、和的线性组合， *因为是对称正定的，因而也应是一个对称正定的，也要是对称正定的。其中和互为装置矩阵，要使对称，必须，以二阶矩阵P为例说明： 代入* *解出当取不同的值时，会得到不同的校正矩阵。取：代入 *式 代入求校正矩阵 DFP公式然后求产生新的迭代方向：二）算法三）程序框图四）算例DFP法在函数的梯度向量容易求出的情况下，是非常有效的