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

第七节 变尺度法（拟牛顿法） 变尺度法是无约束最优化方法发展过程中非常有影响的重要研究成果，它的基本思想是基于有很好收敛速度的牛顿法。但又避免了计算二阶导数矩阵及其求逆计算，又比共轭梯度法有更好的收敛速度，被认为是求最优化问题的最有效的算法之一。 牛顿法的缺点：计算复杂（一阶、二阶偏导数）、对数的性态要求高（对海赛矩阵要求、对初始点的选择要求） 一、变尺度法的基本原理 一）范数和尺度 函数图象联系了函数和几何，表达两个数之间的变化关系，映射推广了函数的概念，使得自变量不再仅仅局限于一个数，也不再局限于一维，任何事物都可以拿来作映射，维数可以是任意维，传统的函数图象已无法直观地表达高维对象之间的映射关系，这就要求我们在观念中，把三维的几何空间推广到抽象的n维空间。 由于映射的对象可以是任何事物，为了便于研究映射的性质以及数学表达，我们首先需要对映射的对象进行“量化”，取定一组“基”，确定事物在这组基下的坐标，事物同构于我们所熟悉的抽象几何空间中的点，事物的映射可以理解为从一个空间中的点到另一个空间的点的映射，而映射本身也是事物，自然也可以抽象为映射空间中的一个点。 范数是把一个事物映射到非负实数，且满足非负性、齐次性、三角不等式，符合以上定义的都可以称之为范数，所以，范数的具体形式有很多种（由内积定义可以导出范数，范数还也可以有其他定义，或其他方式导出）。 从一个线性空间到另一个线性空间的线性映射，可以用一个矩阵来表达，矩阵被看线性作映射，线性映射的性质可以通过研究矩阵的性质来获得。 平面解析几何中一个向量 的长度的定义： 它具有非负性、齐次性和三角不等式三个基本性质。 向量范数定义 一个从到的非负函数叫做上的向量范数，如果满足： （1） 正定性：对所有的有，而且当且仅当； （2） 齐次性：对所有的和有； （3） 三角不等式：对所有的有. 向量x与y之间的距离可定义为的x-y范数，即 常用范数 　　最常用的范数就是p-范数。若x=[x1,x2,...,xn]^T，那么 　　║x║p=(|x1|p+|x2| p +...+|xn| p) 1/p 　　可以验证p-范数确实满足范数的定义。 　　当p取1，2，∞的时候分别是以下几种最简单的情形： 　　1-范数：║x║1=│x1│+│x2│+…+│xn│ 　　2-范数：║x║2=(│x1│^2+│x2│^2+…+│xn│^2)^1/2 　　∞-范数：║x║∞=max(│x1│,│x2│,…,│xn│) 　　其中2-范数就是通常意义下的距离。 　　 1-范数意义下的“单位圆”和第一象限的“单位球” 2-范数意义下的“单位圆”和第一象限的“单位球” ∞-范数意义下的“单位圆”和第一象限的“单位球” 若 ，它的欧式范数（或模）定义为 向量X和Y的差X-Y的范数 是X和Y两个向量终点的距离，而 和 也表示它们自身始点到终点的距离，因此可以用距离来解释范数。这个概念和尺度空间中尺度概念是一致的，故范数可以成为尺度。 这个概念可以推广，如A是任何一个n×n阶实对称正定矩阵，定义 也是一种向量范数（非欧式范数）。 梯度法沿最速下降方向 进行搜索，收敛性不好 牛顿方向 进行搜索，可以直接指向极小点。这种改进的实质是：牛顿法是对二次函数 进行了变换，使其在新坐标系中减小偏心率。 例 原坐标中的尺度（范数）是 新坐标系尺度是 牛顿法是改变范数（尺度）之后的最速下降法。 二）变尺度矩阵的概念 梯度法迭代公式为 牛顿迭代公式为 原坐标中的尺度（范数）是 新坐标系尺度是 尺度的改变决定于A。 梯度法和牛顿法的迭代公式可以统一写成 式中 为迭代方向， ，若 为单位矩阵，则表示梯度法，若 ，则表示阻尼牛顿法。 牛顿法虽然收敛速度快，但在多数情况下，求二阶偏导数 及其逆矩阵 是相当的繁复困难，为了克服这一缺点，希望新的度量公式去产生搜索方向，于是引入了变尺度的思想，并在1957年以后提出和发展了一类搜索方法，称之为变尺度法。 它的基本思想是：利用牛顿法的迭代形式，用一个对称正定矩阵 来代替 ，并在迭代过程中，使其逐渐逼近 。在这个过程中，尺度的改变决定于矩阵A，故 为变尺度矩阵。 是逐渐逼近 的一个序列，它的值依赖于迭代次数，故美确定一个搜索方向，度量即改变一次，这是变尺度方法名称的由来。 三）构造 的原则 1、下降性 也就是说方向 必须是函数值下降的方向，所以它与 方向的夹角必须小于90°，即 ， 构造的矩阵 必须是正定矩阵。 2、收敛性 产生的迭代方向 是关于矩阵 相互共轭的，这样算法才具有二次收敛性。 3、方便性 希望矩阵 具有以下递推形式： 式中 —校正矩阵，要求它计算简便，只依赖于本次迭代的 、 和相应的梯度向量 、 。 三）构造 的途径 先一下海赛矩阵和梯度之间的关系，以便寻求构造近似矩阵 的途径。 函数 梯度 式中 （ ） 则有： 令 这是海赛矩阵 应当满足的相关公式，而对于第K次迭代，要求 趋近于 。所以 也应满足： 这是在构造 时应当满足的条件，称为变尺度条件，也称为拟牛顿条件。 二、DFP变尺度法 Davidon 1959年首先提出 Fletcher、Powell 1963年对之进行改进 DFP 一）迭代公式 式中 —校正矩阵 由于 为上一迭代点，已知，因此转为求校正矩阵的问题。 要求它计算简便，只依赖于本次迭代的 、 和相应的梯度向量 、 ，即依赖于 和 。 、 为两个待定向量，且满足以下条件 ** 、 可以表示为 、 和 的线性组合， *** 因为 是对称正定的，因而 也应是一个对称正定的， 也要是对称正定的。 其中 和 互为装置矩阵，要使 对称，必须 ，以二阶矩阵P为例说明： 代入** ** 解出 当 取不同的值时，会得到不同的校正矩阵。 取 ： 代入 ***式 代入求校正矩阵 DFP公式 然后求 产生新的迭代方向： 二）算法 三）程序框图 四）算例 DFP法在函数 的梯度向量容易求出的情况下，是非常有效的。它具有超线性收敛速度，但是计算 程序复杂，所需存储量大，在有舍入误差的情况下，算法的稳定性较差，有时 趋向奇异。 三、BFGS变尺度法 当 取不同的值时，会得到不同的校正矩阵。 BFGS法方法与DFP法的主要区别在于 取值不同， DFP法 BFGS法： _1353134610.unknown _1353136987.unknown _1353141298.unknown _1353143208.unknown _1353143598.unknown _1353143709.unknown _1353144146.unknown _1353145751.unknown _1353145779.unknown _1353145325.unknown _1353143738.unknown _1353143699.unknown _1353143238.unknown _1353143256.unknown _1353142370.unknown _1353143002.unknown _1353143018.unknown _1353143098.unknown _1353142948.unknown _1353143000.unknown _1353142392.unknown _1353141591.unknown _1353142353.unknown _1353141533.unknown _1353140511.unknown _1353141030.unknown _1353141187.unknown _1353141257.unknown _1353141102.unknown _1353140707.unknown _1353137731.unknown _1353138705.unknown _1353138894.unknown _1353139029.unknown _1353138758.unknown _1353138573.unknown _1353138638.unknown _1353138650.unknown _1353138333.unknown _1353138318.unknown _1353137689.unknown _1353137035.unknown _1353137576.unknown _1353136116.unknown _1353136544.unknown _1353136749.unknown _1353136779.unknown _1353136595.unknown _1353136407.unknown _1353136490.unknown _1353136302.unknown _1353134945.unknown _1353135000.unknown _1353134980.unknown _1353134835.unknown _1353134920.unknown _1353134639.unknown _1353134777.unknown _1353103759.unknown _1353131856.unknown _1353134017.unknown _1353134198.unknown _1353134292.unknown _1353134510.unknown _1353134087.unknown _1353132958.unknown _1353133930.unknown _1353132307.unknown _1353132377.unknown _1353131880.unknown _1353132225.unknown _1353131247.unknown _1353131478.unknown _1353131844.unknown _1353131386.unknown _1353104613.unknown _1353131130.unknown _1353130304.unknown _1353130575.unknown _1353103894.unknown _1353103036.unknown _1353103516.unknown _1353102748.unknown _1353102944.unknown _1353103018.unknown _1353102834.unknown _1353101020.unknown _1353101552.unknown _1353100897.unknown _1135004804.unknown