非凸函数的Broyden族算法研究.pdfVIP

因此优化 问题 (L I)可 以近似地视为求解如下二次规划 问题： m m fk + gld + (1.3) 其 中 d X — Xk- 当iffc为正定矩阵时，容易得到 (1.3)式的最小值点为 X k -  (1.4) 将其作为 问题 (1.1)极值点的新 的近似点，即令 Xk+ I Xk - (1.5) 这 就 是牛顿迭 代 法 . 从 公式 (1.5)不难 看 出，牛顿 法希 望每 一个丑 都 是正 定 的，否则 (1.4)式 不一 定 是 (1.3)的极小值点. 注意到负梯度方 向- 办为函数在:? 点的最速下降方 向，因而7? 正定 保证 了所产生 的方 向- 供是沿办 的下降方 向. 然而 ，牛顿法需要计算迭代 点的二阶导数 ，对于大规模 问题其运算量相 当惊人 ，甚 至无法计算.拟牛顿法提 出的 目的在于克服这些缺 点，其基本方法是在 牛顿法 中用某个 矩阵 来近似取代H esse矩 阵/ffc. 算法 的基本步骤如下： 算法 1.1 初始化 ：确 定初值 :ci G R 及 G R x， 为对称正定麵 阵，k 1，确 疋精 度 e 0 . 第1步：计算梯度供 V / (xfc),如果 e，算法停止；否则令 作为搜 索 方 向. 弟2步：通过线搜 索技木确定_步长Ofc，令T;f+ci x/c + 第3 步 ：根据 拟 牛 顿 法 的迭 代 公 式计 算 第4 步：令fc k + l,转 第1步. 通 常万fc应具有 下面三 个特 点 ： 1. 满 足拟 牛 顿 方 程 B k+ iSk — Vk ? (1-6) 2 由(1.2)式，函数/ (X)在rrf+ci点的两次近似为 fix) ^ fk+i + gl+A 工-Xk+i) + ]^x[ - Xk+ifHk+ix{ — Xk+i). 对 :E求梯 度 得 9 {x ) ^ Qk+ i + H k+ i{x - Xk+ i), 再令 r; ? 即得 H k+ iSk - Vk- (1-7) 由此可见，拟牛顿方程 (1.6)使得矩 阵 可作为H esse矩 阵丑fc的近似，从而使相应 的算法 产生 的方 向近似于牛顿方 向，以确保算法具有较快 的收敛速度 . 2. 对所有 的 是对称正定的，从而使得算法所产生 的方 向是函数/ (rr)在0? 处的 下 降方 向. 3.矩阵 更新规则 (修正公式)较为简单. 第一个拟牛顿法 由D avidon [2]提出，后经F letcher和Pow ell修改整理，故称为D FP 方 法，它 的修正公式为 D D B kSkvl + ykslB k I 广 1 I slB kSk\ ynvl ,i 。、 h k+ 1 ~  T ^ 丄  T ~ T ? U -O j Vk 外 \ Vk ^k J yi Sk 另一个非常著名的拟牛顿法是B FG S方