Question

5.1 原理

1. 在牛顿法的迭代中，需要计算海森矩阵的逆矩阵 $ MathJax-Element-323 $ ，这一计算比较复杂。

   可以考虑用一个 $ MathJax-Element-372 $ 阶矩阵 $ MathJax-Element-238 $ 来近似代替 $ MathJax-Element-239 $ 。

2. 先看海森矩阵满足的条件： $ MathJax-Element-240 $ 。

   • 令 $ MathJax-Element-241 $ 。则有： $ MathJax-Element-242 $ ，或者 $ MathJax-Element-243 $ 。

     这称为拟牛顿条件。

   • 根据牛顿法的迭代： $ MathJax-Element-244 $ ，将 $ MathJax-Element-433 $ 在 $ MathJax-Element-246 $ 的一阶泰勒展开：

     $ f(\mathbf {\vec x}^{})=f(\mathbf {\vec x}^{})+f'(\mathbf {\vec x}^{})(\mathbf {\vec x}^{}-\mathbf {\vec x}^{})\\ =f(\mathbf {\vec x}^{})+\mathbf {\vec g}_k^{T}(-\mathbf H_k^{-1}\mathbf {\vec g}_k)=f(\mathbf {\vec x}^{})-\mathbf {\vec g}_k^{T}\mathbf H^{-1}_k\mathbf {\vec g}_k $

     当 $ MathJax-Element-247 $ 是正定矩阵时，总有 $ MathJax-Element-248 $ ，因此每次都是沿着函数递减的方向迭代。

3. 如果选择 $ MathJax-Element-322 $ 作为 $ MathJax-Element-250 $ 的近似时， $ MathJax-Element-322 $ 同样要满足两个条件：

   • $ MathJax-Element-322 $ 必须是正定的。

   • $ MathJax-Element-322 $ 满足拟牛顿条件： $ MathJax-Element-254 $ 。

     因为 $ MathJax-Element-304 $ 是给定的初始化条件，所以下标从 $ MathJax-Element-328 $ 开始。

   按照拟牛顿条件，在每次迭代中可以选择更新矩阵 $ MathJax-Element-257 $ 。

4. 正定矩阵定义：设 $ MathJax-Element-278 $ 是 $ MathJax-Element-279 $ 阶方阵，如果对任何非零向量 $ MathJax-Element-449 $ ，都有 $ MathJax-Element-261 $ ，就称 $ MathJax-Element-278 $ 正定矩阵。

   • 正定矩阵判定：

     • 判定定理1：对称阵 $ MathJax-Element-278 $ 为正定的充分必要条件是： $ MathJax-Element-278 $ 的特征值全为正。
     • 判定定理2：对称阵 $ MathJax-Element-278 $ 为正定的充分必要条件是： $ MathJax-Element-278 $ 的各阶顺序主子式都为正。
     • 判定定理3：任意阵 $ MathJax-Element-278 $ 为正定的充分必要条件是： $ MathJax-Element-278 $ 合同于单位阵。

   • 正定矩阵的性质：

     • 正定矩阵一定是非奇异的。奇异矩阵的定义：若 $ MathJax-Element-279 $ 阶矩阵 $ MathJax-Element-278 $ 为奇异阵，则其的行列式为零，即 $ MathJax-Element-271 $ 。
     • 正定矩阵的任一主子矩阵也是正定矩阵。
     • 若 $ MathJax-Element-278 $ 为 $ MathJax-Element-279 $ 阶对称正定矩阵，则存在唯一的主对角线元素都是正数的下三角阵 $ MathJax-Element-274 $ ，使得 $ MathJax-Element-275 $ ，此分解式称为 正定矩阵的乔列斯基（Cholesky）分解。
     • 若 $ MathJax-Element-278 $ 为 $ MathJax-Element-279 $ 阶正定矩阵，则 $ MathJax-Element-278 $ 为 $ MathJax-Element-279 $ 阶可逆矩阵。

   • 正定矩阵在某个合同变换下可化为标准型， 即对角矩阵。

   • 所有特征值大于零的对称矩阵也是正定矩阵。

5. 合同矩阵：两个实对称矩阵 $ MathJax-Element-447 $ 和 $ MathJax-Element-281 $ 是合同的，当且仅当存在一个可逆矩阵 $ MathJax-Element-285 $ ，使得 $ MathJax-Element-283 $

   • $ MathJax-Element-447 $ 的合同变换：对某个可逆矩阵 $ MathJax-Element-285 $ ，对 $ MathJax-Element-447 $ 执行 $ MathJax-Element-287 $ 。

5.2 DFP 算法

1. DFP算法( Davidon-Fletcher-Powell) 选择 $ MathJax-Element-366 $ 的方法是：

   假设每一步迭代中 $ MathJax-Element-366 $ 是由 $ MathJax-Element-322 $ 加上两个附加项构成： $ MathJax-Element-291 $ ，其中 $ MathJax-Element-332 $ 是待定矩阵。此时有： $ MathJax-Element-293 $ 。

   为了满足拟牛顿条件，可以取： $ MathJax-Element-294 $ 。

   这样的 $ MathJax-Element-332 $ 不止一个。例如取 ：

   $ \mathbf P_k=\frac{\vec \delta_k\vec \delta_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k},\quad \mathbf Q_k=-\frac{\mathbf G_k\mathbf {\vec y}_k \mathbf {\vec y}_k^{T} \mathbf G_k}{\mathbf {\vec y}_k^{T}\mathbf G_k \mathbf {\vec y}_k} $

   则迭代公式为：

   $ \mathbf G_{k+1}=\mathbf G_k+\frac{\vec \delta_k\vec \delta_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k}-\frac{\mathbf G_k\mathbf {\vec y}_k \mathbf {\vec y}_k^{T} \mathbf G_k}{\mathbf {\vec y}_k^{T} \mathbf G_k \mathbf {\vec y}_k} $

   可以证明：如果初始矩阵 $ MathJax-Element-304 $ 是正定的，则迭代过程中每个矩阵 $ MathJax-Element-322 $ 都是正定的。

2. DFP算法：

   • 输入：

     • 目标函数 $ MathJax-Element-433 $
     • 梯度 $ MathJax-Element-337 $
     • 精度要求 $ MathJax-Element-300 $

   • 输出： $ MathJax-Element-433 $ 的极小值点 $ MathJax-Element-340 $

   • 算法步骤：

     • 选取初始值 $ MathJax-Element-341 $ , 取 $ MathJax-Element-304 $ 为正定对称矩阵，置 $ MathJax-Element-343 $ 。

     • 迭代，停止条件为：梯度收敛。迭代步骤为：

       • 计算 $ MathJax-Element-344 $ 。

       • 若 $ MathJax-Element-345 $ ， 则停止计算，得到近似解 $ MathJax-Element-358 $ 。

       • 若 $ MathJax-Element-347 $ ， 则：

         • 计算 $ MathJax-Element-310 $ 。
         • 一维搜索：求 $ MathJax-Element-363 $ ： $ MathJax-Element-354 $ 。
         • 设置 $ MathJax-Element-355 $ 。
         • 计算 $ MathJax-Element-356 $ 。若 $ MathJax-Element-357 $ ， 则停止计算，得到近似解 $ MathJax-Element-358 $ 。
         • 否则计算 $ MathJax-Element-366 $ ，置 $ MathJax-Element-360 $ ，继续迭代。

3. DFP算法中，每一次 $ MathJax-Element-449 $ 增加的方向是 $ MathJax-Element-320 $ 的方向。增加的幅度由 $ MathJax-Element-363 $ 决定，若跨度过大容易引发震荡。

   

5.2 BFGS 算法

1. BFGS是最流行的拟牛顿算法。 DFP算法中，用 $ MathJax-Element-322 $ 逼近 $ MathJax-Element-323 $ 。换个角度看，可以用矩阵 $ MathJax-Element-351 $ 逼近海森矩阵 $ MathJax-Element-325 $ 。此时对应的拟牛顿条件为： $ MathJax-Element-326 $ 。

   因为 $ MathJax-Element-342 $ 是给定的初始化条件，所以下标从 $ MathJax-Element-328 $ 开始。

2. 令： $ MathJax-Element-329 $ ，有： $ MathJax-Element-330 $ 。

   可以取 $ MathJax-Element-331 $ 。寻找合适的 $ MathJax-Element-332 $ ，可以得到 BFGS 算法矩阵的 $ MathJax-Element-359 $ 的迭代公式：

   $ \mathbf B_{k+1}=\mathbf B_k+\frac{\mathbf {\vec y}_k\mathbf {\vec y}_k^{T}}{\mathbf {\vec y}_k^{T}\vec \delta_k}-\frac{\mathbf B_k\vec \delta_k\vec \delta_k^{T}\mathbf B_k}{\vec \delta_k^{T}\mathbf B_k\vec \delta_k} $

   可以证明，若 $ MathJax-Element-342 $ 是正定的，则迭代过程中每个矩阵 $ MathJax-Element-351 $ 都是正定的。

3. BFGS算法：

   • 输入：

     • 目标函数 $ MathJax-Element-433 $
     • 梯度 $ MathJax-Element-337 $
     • 精度要求 $ MathJax-Element-338 $

   • 输出： $ MathJax-Element-433 $ 的极小值点 $ MathJax-Element-340 $

   • 算法步骤：

     • 选取初始值 $ MathJax-Element-341 $ , 取 $ MathJax-Element-342 $ 为正定对称矩阵，置 $ MathJax-Element-343 $ 。

     • 迭代，停止条件为：梯度收敛。迭代步骤为：

       • 计算 $ MathJax-Element-344 $ 。

       • 若 $ MathJax-Element-345 $ ， 则停止计算，得到近似解 $ MathJax-Element-358 $ 。

       • 若 $ MathJax-Element-347 $ ， 则:

         • 由 $ MathJax-Element-348 $ 求出 $ MathJax-Element-349 $ 。

           这里表面上看需要对矩阵求逆。但是实际上 $ MathJax-Element-352 $ 有迭代公式。根据Sherman-Morrison 公式以及 $ MathJax-Element-351 $ 的迭代公式，可以得到 $ MathJax-Element-352 $ 的迭代公式。

         • 一维搜索：求 $ MathJax-Element-363 $ ： $ MathJax-Element-354 $ 。

         • 设置 $ MathJax-Element-355 $ 。

         • 计算 $ MathJax-Element-356 $ 。若 $ MathJax-Element-357 $ ， 则停止计算，得到近似解 $ MathJax-Element-358 $ 。

         • 否则计算 $ MathJax-Element-359 $ ，置 $ MathJax-Element-360 $ ，继续迭代。

4. BFPS 算法中，每一次 $ MathJax-Element-449 $ 增加的方向是 $ MathJax-Element-362 $ 的方向。增加的幅度由 $ MathJax-Element-363 $ 决定，若跨度过大容易引发震荡。

   

5.3 Broyden 类算法

1. 若记 $ MathJax-Element-364 $ ，则对式子：

   $ \mathbf B_{k+1}=\mathbf B_k+\frac{\mathbf {\vec y}_k\mathbf {\vec y}_k^{T}}{\mathbf {\vec y}_k^{T}\vec \delta_k}-\frac{\mathbf B_k\vec \delta_k\vec \delta_k^{T}\mathbf B_k}{\vec \delta_k^{T}\mathbf B_k\vec \delta_k} $

   使用两次Sherman-Morrison公式可得：

   $ \mathbf G_{k+1}=(\mathbf I-\frac{\vec \delta_k\mathbf {\vec y}_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k})\mathbf G_k(\mathbf I-\frac{\vec \delta_k\mathbf {\vec y}_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k})^{T}+\frac{\vec \delta_k\vec \delta_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k} $

2. 令 DFP 算法获得的 $ MathJax-Element-366 $ 的迭代公式记作：

   $ \mathbf G^{DFP}=\mathbf G_k+\frac{\vec \delta_k\vec \delta_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k}-\frac{\mathbf G_k\mathbf {\vec y}_k \mathbf {\vec y}_k^{T} \mathbf G_k}{\mathbf {\vec y}_k^{T} \mathbf G_k \mathbf {\vec y}_k} $

   由 BFGS 算法获得的 $ MathJax-Element-366 $ 的迭代公式记作 ：

   $ \mathbf G^{BFGS}=(\mathbf I-\frac{\vec \delta_k\mathbf {\vec y}_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k})\mathbf G_k(\mathbf I-\frac{\vec \delta_k\mathbf {\vec y}_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k})^{T}+\frac{\vec \delta_k\vec \delta_k^{T}}{\vec \delta_k^{T}\mathbf {\vec y}_k} $

   他们都满足拟牛顿条件，所以他们的线性组合： $ MathJax-Element-367 $ 也满足拟牛顿条件，而且是正定的，其中 $ MathJax-Element-368 $ 。

   这样获得了一族拟牛顿法，称为 Broyden 类算法。

3. Sherman-Morrison公式：假设 $ MathJax-Element-447 $ 是 $ MathJax-Element-372 $ 阶可逆矩阵， $ MathJax-Element-371 $ 是 $ MathJax-Element-372 $ 维列向量，且 $ MathJax-Element-373 $ 也是可逆矩阵，则：

   $ (\mathbf A+\mathbf {\vec u}\mathbf {\vec v}^{T})^{-1}=\mathbf A^{-1}-\frac{\mathbf A^{-1}\mathbf {\vec u}\mathbf {\vec v}^{T}\mathbf A^{-1}}{1+\mathbf {\vec v}^{T}\mathbf A^{-1}\mathbf {\vec u}} $

   .