利用正定矩阵关于向量的等内积分解算法^[1], 文[2]提出了由校正矩阵的等内积分解矩阵确定搜索方向的拟Newton算法.即对于无约束最优化问题

$ \begin{equation} \min~f(x), ~~x~\in~R^{n}, \end{equation} $

(1.1)

其中$f: R^{n}~\rightarrow~R^{1}$是连续可微函数, 通过建立Hesse近似矩阵$B$关于目标函数梯度向量的等内积分解矩阵的校正公式, 计算搜索方向的一种新算法.

以拟Newton算法中最有代表性的BFGS算法为例, 当记${x}^{k}$为迭代点, $s_k= {x}^{k+1}-{x}^{k}$, $y_k=g_{k+1}-g_k$, $g_k=\bigtriangledown f({x}^{k})$, 则对$B$和对$H$的BFGS校正公式分别为

$ B_{k+1}=B_{k}-\frac{B_{k}s_{k}s_{k}^{T}B_{k}}{s_{k}^{T}B_{k}s_{k}}+\frac{y_{k}y_{k}^{T}}{s_{k}^{T}y_{k}}, $

(1.2)

$ H_{k+1}~=(I-\frac{s_{k}y_{k}^{T}}{s_{k}^{T}y_{k}})H_{k}(I-\frac{y_{k}s_{k}^{T}}{s_{k}^{T}y_{k}})+\frac{s_{k}s_{k}^{T}}{s_{k}^{T}y_{k}}. $

(1.3)

在求迭代点$\textit{x}^{k+1}$处的搜索方向$\textit{d}^{k+1}$时, 一般是解方程组

$ \begin{equation} B_{k+1}\textit{d}^{k+1}=-g_{k+1}, \end{equation} $

(1.4)

而不是用(1.3)式直接计算.

$ \begin{equation} d^{k+1}~=~-H_{k+1}g_{k+1}. \end{equation} $

(1.5)

采用(1.4)式的计算量显然大于用(1.5) 式, “舍近求远”的原因是, 由于计算误差的存在, 实际计算时用(1.3)式可能出现$H_{k+1}$不正定甚至奇异的情况.而(1.2)式可以化为

$ \begin{equation} B_{k+1}~=~B_{k}+((d^{k})^{T}g_{k})^{-1}g_{k}g_{k}^{T}+(\alpha_{k}(d^{k})^{T}y_{k})^{-1}y_{k}y_{k}^{T}. \end{equation} $

(1.6)

据此, Gill与Murray提出了利用Cholesky分解技术解方程组(1.4) 的方法.即先对$B_{k+1}$作Cholesky分解: $B_{k+1}=L_{k+1}D_{k+1}L_{k+1}^{T}$, 其中$\textit{L}_{k+1}$为单位下三角阵, $D_{k+1}$为对角阵, 再依次解方程组

$ \begin{aligned} {L}_{k+1}v~=~-\textit{g}_{k+1}, ~~~~{L}_{k+1}^{T}d^{k+1}={D}_{k+1}^{-1}v. \end{aligned} $

(1.7)

同时利用(1.6) 式, 给出由${L}_{k}$, ${D}_{k}$求${L}_{k+1}$, ${D}_{k+1}$的迭代公式, 使实际计算时不必每次迭代都进行一次${B}_{k}$的Cholesky分解, 具体算法详见文[3-5].

而文[2]提出的改进算法, 则是运用了正定矩阵关于向量的等内积分解算法, 通过求${B}_{k+1}$关于$g_{k+1}=\bigtriangledown f({x}^{k+1})$的等内积分解矩阵.即满足条件

$ \begin{aligned} {B}_{k+1}~=~{C}_{k+1}{C}_{k+1}^{T}, ~{C}_{k+1}^{-1}{g}_{k+1}={a}_{k+1}e \end{aligned} $

(1.8)

的矩阵${C}_{k+1}^{-1}$, 其中${a}_{k+1}~\in~R^{1}$, ${e}=(1, 1, \cdots, 1)^{T}~\in~R^{n}$, 来计算点${x}^{k+1}$处的搜索方向

$ \begin{aligned} {d}^{k+1}~=~-{a}_{k+1}({d}_{1}^{k+1}\cdots{d}_{n}^{k+1})^{T}, \end{aligned} $

(1.9)

其中${d}_{j}^{k+1}$$({j}=1, 2\cdots, n)$是矩阵${C}_{k+1}^{-1}$第${j}$列元素之和.具体作法是替代校正公式(1.2), 直接建立$B$关于目标函数梯度向量的分解矩阵${C}_{k}^{-1}$到${C}_{k+1}^{-1}$的校正公式, 在计算出校正矩阵${C}_{k+1}^{-1}$的同时, 利用(1.9) 式求出搜索方向${d}^{k+1}$.

显然文[2]给出了求搜索方向的另一种路径, 但文[2]中的相关结论, 都是在精确线搜索条件下给出的, 所以理论意义大于实际应用.在拟Newton算法中BFGS算法是最有代表性的一个算法, 带Wofle搜索的BFGS算法具有全局收敛和超线性收敛性(参见文[4]), 与拟Newton算法中的其它算法比较其收敛速度和数值稳定性都是最好的.本文就以BFGS算法为研究对象, 通过建立不依赖搜索方式的用分解矩阵表达的校正公式, 给出用Hesse近似矩阵的等内积分解矩阵确定搜索方向BFGS新算法.

当记$u_k= {C}_{k}^{-1}{y}_{k}$, $v_k= {C}_{k}^{-1}{g}_{k+1}$, $w_k= {C}_{k}^{-1}{g}_{k}$.由文[2]定理2.2, 在精确线搜索条件下对于BFGS校正公式(1.2).若已求得${B}_{k}$关于${g}_{k}$的等内积分解矩阵${C}_{k}^{-1}$, 则${B}_{k+1}$关于${g}_{k+1}$的等内积分解矩阵

$ \begin{aligned} {C}_{k+1}^{-1}~=~{Q}_{k}{C}_{k}^{-1}[{I}-\frac{({y}_{k}-\sqrt{\lambda_{k}}{g}_{k}){s}_{k}^{T}} {{s}_{k}^{T}{y}_{k}}], \end{aligned} $

(2.1)

其中$\lambda_k=\frac{{S}_{k}^{T}{y}_{k}}{\| {w}_{k} \|^{2}}$, ${Q}_{k}={I}-\frac{2}{\| \sigma_{k} \|^{2}}\sigma_{k}\sigma_{k}^{T}$, $\sigma_{k}={w}_{k}+{t}_{k}{v}_{k}$, ${t}_{k}=\frac{\| {w}_{k} \|}{\| {v}_{k} \|}$.由文[2]定理2.3, 初始校正矩阵${B}_{0}={I}$关于${g}_{0}$的等内积分解矩阵

$ \begin{aligned} {C}_{0}^{-1}=\left\{ \begin{aligned} I, ~~~~~~~~~~~~~ g_{0}=-e, \\ I-\frac{2}{\| \sigma_{0} \|^{2}}\sigma_{0}\sigma_{0}^{T}, ~~~~~~~ g_{0}\neq-e, \end{aligned} \right. \end{aligned} $

(2.2)

其中$\sigma_{0}=\sqrt{n}g_{0}+ \|g_{0}\|e.$

由(2.1) 式定义的${C}_{k+1}^{-1}$只有在精确线搜索条件下.即${v}_{k}^{T}{w}_{k}=0$时, 有${B}_{k+1}={C}_{k+1}{C}_{k+1}^{T}$.若迭代点${x}^{k}$是经过非精确线搜索到${x}^{k+1}$, 则由(2.1) 式定义的矩阵${C}_{k+1}^{-1}$显然不再是(1.2) 式定义的${B}_{k+1}$的分解矩阵.下面给出的结论则与搜索方式无关, 仅依赖于BFGS校正矩阵的定义式.

引理2.1  设$u, $ $v~\epsilon~R^{n}$, 若$\beta\neq 0$, $\gamma\neq 0$, ${v}^{T}{u}=\beta^{-1}+\gamma^{-1}$, 则矩阵${I}-\beta uv^{T}$非奇异, 并且

$ \begin{aligned} ({I}-\beta uv^{T})^{-1}={I}-\gamma uv^{T}. \end{aligned} $

(2.3)

引理2.2  对于BFGS校正公式(1.2), 若${B}_{k}$关于${g}_{k}$的等内积分解矩阵为${C}_{k}^{-1}$.记

$ \begin{aligned} {N}_{k}=(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{s}_{k}^{T}-\frac{{g}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}){C}_{k}, \end{aligned} $

(2.4)

则${B}_{k+1}={N}_{k}{N}_{k}^{T}$, 并且

$ \begin{aligned} {N}_{k}^{-1}={C}_{k}^{-1}({I}-\frac{{y}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}+\frac{{g}_{k}{s}_{k}^{T}} {\| {w}_{k} \|\sqrt{{s}_{k}^{T}{y}_{k}}}). \end{aligned} $

(2.5)

证  注意到${s}_{k}={x}^{k+1}-{x}^{k}=\alpha_{k}{d}^{k}$, 其中$\alpha_{k}$为步长, 于是${B}_{k}{s}_{k}=-\alpha_{k}{g}_{k}$.直接计算得

$ {N}_{k}{N}_{k}^{T}=(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{s}_{k}^{T}-\frac{{g}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}){B}_{k}(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{s}_{k}{y}_{k}^{T}-\frac{{s}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}})\\ \;\;\;\;=({B}_{k}-\frac{\alpha_{k}\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{g}_{k}^{T}+\frac{\alpha_{k}{g}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}})(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{s}_{k}{y}_{k}^{T}-\frac{{s}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}})\\ \;\;\;\;={B}_{k}+\frac{\alpha_{k}{g}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}-\frac{\alpha_{k}\| {w}_{k} \|^{2}}{{s}_{k}^{T}{y}_{k}{s}_{k}^{T}{g}_{k}}{y}_{k}{y}_{k}^{T}\\ \;\;\;\;={B}_{k}+\frac{\alpha_{k}{g}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}+\frac{{y}_{k}{y}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}\\ \;\;\;\;={B}_{k}-\frac{{B}_{k}{s}_{k}{s}_{k}^{T}{B}_{k}}{{s}_{k}^{T}{B}_{k}{s}_{k}}+\frac{{y}_{k}{y}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}. $

所以${B}_{k+1}= {N}_{k}{N}_{k}^{T}$.由于

$ \begin{aligned} {I}+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{s}_{k}^{T}-\frac{{g}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}={I}-(-\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}+\frac{1}{{s}_{k}^{T}{g}_{k}}{g}_{k}){s}_{k}^{T}, \end{aligned} $

由引理2.1, 易得

$ \begin{aligned} ({I}+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{s}_{k}^{T}-\frac{{g}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{g}_{k}})^{-1}={I}-\frac{{y}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}+\frac{{g}_{k}{s}_{k}^{T}}{\| {w}_{k} \|\sqrt{{s}_{k}^{T}{y}_{k}}}, \end{aligned} $

从而有${N}_{k}^{-1}={C}_{k}^{-1}({I}-\frac{{y}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}+\frac{{g}_{k}{s}_{k}^{T}}{\| {w}_{k} \|\sqrt{{s}_{k}^{T}{y}_{k}}})$.证毕.

引理2.3  若$0\neq \delta_{k}~\epsilon~R^{n}$, 记${Q}_{k}={I}-\frac{2\sigma_{k}\sigma_{k}^{T}}{\| \sigma_{k} \|^{2}}$, 其中$\sigma_{k}=\delta_{k}+\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}$, 则

$ \begin{aligned} {Q}_{k}\delta_{k}=-\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}. \end{aligned} $

证  直接计算可知$2\sigma_{k}^{T}\delta_{k}=\| \sigma_{k} \|^{2}$, 故

$ \begin{aligned} {Q}_{k}\delta_{k}=\delta_{k}-\frac{2\sigma_{k}^{T}\delta_{k}}{\| \sigma_{k} \|^{2}}\sigma_{k}=\delta_{k}-\sigma_{k}=-\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}. \end{aligned} $

证毕.

当记

$ \begin{aligned} \delta_{k}={N}_{k}^{-1}{g}_{k+1}={p}_{k}{v}_{k}+{q}_{k}{w}_{k}, \end{aligned} $

(2.6)

其中${p}_{k}=-\frac{{s}_{k}^{T}{g}_{k}}{{s}_{k}^{T}{y}_{k}}$, ${q}_{k}=\frac{(\| {w}_{k} \|+\sqrt{{s}_{k}^{T}{y}_{k}}){s}_{k}^{T}{g}_{k+1}}{\| {w}_{k} \|{s}_{k}^{T}{y}_{k}}$, 则有如下结论.

定理2.1  对于BFGS校正公式(1.2), 若已求得${B}_{k}$关于${g}_{k}$的等内积分解矩阵${C}_{k}^{-1}$, 则${B}_{k+1}$关于${g}_{k+1}$的等内积分解矩阵

$ \begin{aligned} {C}_{k+1}^{-1}={Q}_{k}{C}_{k}^{-1}({I}-\frac{{y}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{y}_{k}}+\frac{{g}_{k}{s}_{k}^{T}}{\| {w}_{k} \|\sqrt{{s}_{k}^{T}{y}_{k}}}), \end{aligned} $

(2.7)

其中${Q}_{k}={I}-\frac{2\sigma_{k}\sigma_{k}^{T}}{\| \sigma_{k} \|^{2}}$, $\sigma_{k}=\delta_{k}+\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}$.

证  注意到${Q}_{k}$为Householder矩阵, ${Q}_{k}{Q}_{k}^{T}={I}$, 所以

$ \begin{aligned} {C}_{k+1}{C}_{k+1}^{T}=(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{y}_{k}{s}_{k}^{T}-\frac{{g}_{k}{s}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}){B}_{k}(I+\frac{\| {w}_{k} \|}{\sqrt{{s}_{k}^{T}{y}_{k}}{s}_{k}^{T}{g}_{k}}{s}_{k}{y}_{k}^{T}-\frac{{s}_{k}{g}_{k}^{T}}{{s}_{k}^{T}{g}_{k}}). \end{aligned} $

故由引理2.2知${B}_{k+1}={C}_{k+1}{C}_{k+1}^{T}$.再由引理2.3得

$ \begin{aligned} {C}_{k+1}^{-1}{g}_{k+1}={Q}_{k}\delta_{k}=-\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}={a}_{k+1}e, \end{aligned} $

(2.8)

其中${a}_{k+1}=-\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{a}_{k}$.故由(2.7) 式定义的${C}_{k+1}^{-1}$为${B}_{k+1}$关于${g}_{k+1}$的等内积分解矩阵.

从上述结论的证明过程可以发现, 由(2.7) 式定义的${C}_{k+1}^{-1}$是(1.2) 式定义的${B}_{k+1}$关于${g}_{k+1}$的等内积分解矩阵, 这个结论与搜索方式是无关的.

推论2.1  在精确线搜索条件下, (2.7) 式与(2.1) 式等价, 即(2.1) 式为(2.7) 式的特例.

证  注意到在精确线搜索条件下${s}_{k}^{T}{g}_{k+1}=0$, ${s}_{k}^{T}{g}_{k}=-{s}_{k}^{T}{y}_{k}$, 所以由(2.6) 式得$\delta_{k}={N}_{k}^{-1}{g}_{k+1}={v}_{k}$, 从而$\sigma_{k}=\delta_{k}+\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{w}_{k}=\frac{\| {v}_{k} \|}{\| {w}_{k} \|}({w}_{k}+{t}_{k}{v}_{k})=\frac{\| {v}_{k} \|}{\| {w}_{k} \|}\widetilde{\sigma}_{k}$, 其中$\widetilde{\sigma}_{k}={w}_{k}+{t}_{k}{v}_{k}$.故${Q}_{k}={I}-\frac{2\sigma_{k}\sigma_{k}^{T}}{\| \sigma_{k} \|^{2}}={I}-\frac{2\widetilde{\sigma}_{k}\widetilde{\sigma}_{k}^{T}}{\| \widetilde{\sigma}_{k} \|^{2}}$.又在精确线搜索条件下有$\| {w}_{k} \|\sqrt{{s}_{k}^{T}{y}_{k}}=\frac{1}{\sqrt{\lambda_{k}}}{s}_{k}^{T}{y}_{k}$.利用以上结果, 由(2.7) 式可直接推出(2.1) 式.所以在精确线搜索条件下(2.7) 式与(2.1) 式等价.证毕.

显然, 把由(2.2) 式和(2.7) 式为分解校正矩阵, 由(1.9) 式计算搜索方向的步骤替换到BFGS算法中对应的步骤里, 就可以构成利用分解校正矩阵确定搜索方向的BFGS新算法.由于分解校正矩阵的迭代运算仅是非奇异矩阵到非奇异矩阵的迭代运算, 因此计算精度的要求应低于原BFGS算法中对称正定矩阵到对称正定矩阵的迭代运算.

新的BFGS算法:

步 1  取初始点${x}^{0}$, $\varepsilon \geq0$, 计算${g}_{0}={g}({x}^{0})$.若$\| {g}_{0} \|\leq \varepsilon$, 则停止运算; 否则转步2.

步 2  令${k}=0$; 对初始矩阵${B}_{0}={I}$作关于${g}_{0}$的等内积分解, 求出分解矩阵${C}_{0}^{-1}$和${a}_{0}=-\frac{\| {g}_{0} \|}{\sqrt{n}}$.

步 3  求搜索方向${d}^{k}$:${d}^{k}=-{a}_{k}({d}_{1}^{k}, \cdots, {d}_{n}^{k})^{T}$.其中${d}_{j}^{k}, ({j}=1, 2, \cdots, n)$是${C}_{k}^{-1}$的第${j}$列元素之和.

步 4  一维搜索:由线性搜索求出步长因子$\alpha_{k}$.

步 5  令${x}^{k+1}={x}^{k}+\alpha_{k}{d}^{k}$, 计算${g}_{k+1}={g}({x}^{k+1})$, 若$\| {g}_{k+1} \|\leq \varepsilon$, 则停止计算; 否则转步6.

步 6  由公式(2.7) 求出${B}_{k+1}$关于${g}_{k+1}$的等内积分解矩阵${C}_{k+1}^{-1}$和系数${a}_{k+1}=-\frac{\| \delta_{k} \|}{\| {w}_{k} \|}{a}_{k}$.

步 7  令${k}={k}+1$, 转步3.