之前文章 最速下降法、Newton法、修正Newton法 介绍的最速下降法存在锯齿现象,Newton法需要计算目标函数的二阶导数。接下来介绍的 共轭方向法 是介于最速下降法和Newton法之间的一种方法,它克服了最速下降法的锯齿现象,从而提高了收敛速度;它的迭代公式也比较简单,不必计算目标函数的二阶导数,与Newton法相比,减少了计算量和存储量。它是比较实用而有效的最优化方法。
我们先将其在正定二次函数 上研究,然后再把算法用到更一般的目标函数上。首先考虑二维的情形。
任选初始点 ,沿它的某个下降方向,例如向量 的方向,作直线搜索,如上图所示。由下面这个定理:
定理 :设目标函数 具有一阶连续偏导数,若 ,则 。
知 。如果按照最速下降法选择的就是负梯度方向为搜索方向(也就是 方向),那么将要发生锯齿现象。于是一个设想是,干脆选择下一个迭代的搜索方向 就从 直指极小点 ,也就是找到上图所示的 方向。
因为 从 直指极小点 ,所以 可以表示为: 其中 是最优步长因子。显然,当 时, 。到这里,我们还有一个已知条件没用,就是目标函数为二次正定,所以我们对目标函数求导,得到: 因为 是极小点,所以有: 将 带入上述方程式,有: 上式两边同时左乘 ,并注意到 和 ,得到 。这就是为使 直指极小点 , 所必须满足的条件。并且我们将两个向量 和 称为 共轭向量 或称 和 是 共轭方向 。
由上面共轭梯度法那张图可以设: 上式两边同时左乘 ,得: 由此解出: 代回 得: 从而求到了 的方向。
归纳一下,对于正定二元二次函数,从任意初始点 出发,沿任意下降方向 做直线搜索得到 再从 出发,沿 的共轭方向 作直线搜索,所得到的 必是极小点 。到目前为止的共轭梯度法依旧是假设了目标函数是二次正定矩阵。
上面的结果可以推广到 维空间中,即在 维空间中,可以找出 个互相共轭的方向,对于 元正定二次函数从任意初始点出发,顺次沿着这 个共轭方向最多作 次直线搜索,就可以求到目标函数的极小点。
对于 元正定二次目标函数,如果从任意初始点出发经过 有限次迭代 就能够求到极小点,那么称这种算法具有 二次终止性 。例如,Newton法对于二次函数只须经过一次迭代就可以求到极小点,因此是二次终止的;而最速下降法就不具有二次终止性。共轭方向法(如共轭梯度法、拟Newton法等)也是二次终止的。
一般说来,具有二次终止性的算法,在用于一般函数时,收敛速度是较快的。
定义:设 是 对称正定矩阵。若 维向量空间中的非零向量 满足 , 则称 是 共轭向量或称向量 是 共轭的(简称共轭)。
当 (单位矩阵)时 变为 , 。即向量 互相正交 。由此看到,“正交”是“共轭”的一种特殊情形,或说,“共轭”是“正交”的推广。
下面介绍几个定理:
定理 :若非零向量 是 共轭的,则线性无关。
推论 :在 维向量空间中, 非零的共轭向量的个数不超过 。
定义 设 是 中的线性无关向量, 。那么形式为: 的向量构成的集合,记为 。称为由点 和向量 所生成的 线性流形 。
共轭方向法的理论基础是下面的定理。
定理 假设
(1) Q为 对称正定矩阵;
(2) 非零向量 是 共轭向量;
(3) 对二次目标函数 顺次进行 次直线搜索: 其中 是任意选定的初始点,则有:
i) , ;
ii) 是二次函数 在线性流形 上的极小点。
这个定理看来较繁,但可借用直观的几何图形来帮助理解。 , 的情形为例,如图示。
和 是Q共轭向量,张成了二维空间 ,这是过坐标原点的一个平面。 现在,过点 沿 方向作直线搜索得到 ,再过点 沿 方向作直线搜索得到 过点 由向量 和 张成的平面就是线性流形 。它是 的平行平面。
定理的论断是,最后一个迭代点 处的梯度 必与 和 垂直。并且 是三元二次目标函数 在线性流形 (即过 由 和 张成的平面)上的极小点。
共轭方向法算法的大体流程 就是:选定初始点 和下降方向向量 ,做直线搜索 。提供的梯度方向 使得 , 。提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名。
那么这里做直线搜索 中的 是如何确定的呢?这里我们先回顾一下在最速下降法中是如何计算这个 的。最速下降法:
依据定理 设目标函数 具有一阶连续偏导数,若 ,则 。,我们可以得到 。由此有: 由此,可求解出 : 这里还可以采用另外一种种方式计算 ,下面对另外一种方式进行公式推导:
由 ,用 左乘上式两边,然后再同时加上 ,利用 能够得到: 左乘 有 由此解出: 在最速下降法中 ,在共轭方向法中 。
在共轭方向法中,如果初始共轭向量 恰好取为初始点 处的负梯度 ,而其余共轭向量 由第 个迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定,那么这个共轭方向法就称为 共轭梯度法 。
针对目标函数是正定二次函数来讨论:
(1) 第一个迭代点的获得 :
选定初始点 ,设 (否则迭代终止),因此 。取 ,(以下用 表示 )从 出发沿 方向做直线搜索,得到第1个迭代点 ,其中 可由下式确定: 显然
(2) 第二个迭代点的获得 :
设 ,因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令: 由此解出 并代回确定 ,并获得第2个迭代点。 由公式 可以求得 ,带入公式 可进一步优化得到: (3) 第三个迭代点的获得 :
设 ,因此 。由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令: 由此解出 并代回确定 ,并获得第3个迭代点。 其中 上述过程仅表明 与 , 与 共轭,现在问, 与 也共轭吗? (4) 第 个迭代点的获得 :
由 知 与 线性无关。取 其中 是使 与 共轭的待定系数,令: 由此解出 并代回确定 ,并获得第k+1个迭代点。 其中 以上就是共轭梯度法得核心内容。
为使共轭梯度算法也适用于非二次函数,需要消去算法中的 对于正定二次函数,有 代入到 中,得: 此式中已不再出现矩阵 ,将 两端转置运算,并同时右乘 得: 将共轭方向法中的定理带入得到 ,由直线搜索的性质有 ,带入上式有 。此外: 带入 ,得到: 此式称为Fletcher-Reeves公式(1964年)。