无约束最优化问题 \begin{align*} \\& \min_{x \in R^{n}} f\left(x\right)\end{align*} 其中$x^{*}$为目标函数的极小点。
设$f\left(x\right)$具有二阶连续偏导数,若第$k$次迭代值为$x^{\left(k\right)}$,则可将$f\left(x\right)$在$x^{\left(k\right)}$附近进行二阶泰勒展开 \begin{align*} \\& f\left(x\right) = f\left(x^{\left(k\right)}\right)+g_{k}^{T}\left(x-x^{\left(k\right)}\right)+\dfrac{1}{2}\left(x-x^{\left(k\right)}\right)^{T} H\left(x^{\left(k\right)}\right)\left(x-x^{\left(x\right)}\right)\end{align*} 其中,$g_{k}=g\left(x^{\left(k\right)}\right)=\nabla f\left(x^{\left(k\right)}\right)$是$f\left(x\right)$的梯度向量在点$x^{\left(k\right)}$的值,$H\left(x^{\left(k\right)}\right)$是$f\left(x\right)$的海赛矩阵 \begin{align*} \\& H\left(x\right)=\left[\dfrac{\partial^{2}f}{\partial x_{i} \partial x_{j}}\right]_{n \times n}\end{align*} 在点$x^{\left(k\right)}$的值。
函数$f\left(x\right)$有极值的必要条件是在极值点处一阶导数为0,即梯度向量为0。特别的当$H\left(x^{\left(k\right)}\right)$是正定矩阵时,函数$f\left(x\right)$的极值为极小值。
假设$x^{\left(k+1\right)}$满足 \begin{align*} \\& \nabla f\left(x^{\left(k+1\right)}\right)=0\end{align*} 根据二阶泰勒展开,得 \begin{align*} \\& \nabla f\left(x\right)=g_{k}+H_{k}\left(x-x^{\left(x\right)}\right)\end{align*} 其中,$H_{k}=H\left(x^{\left(k\right)}\right)$,则 \begin{align*} \\& g_{k}+H_{k}\left(x^{\left(k+1\right)}-x^{\left(x\right)}\right)=0 \\ & x^{\left(k+1\right)}=x^{\left(k\right)}-H_{k}^{-1}g_{k}\end{align*} 令 \begin{align*} \\& H_{k}p_{k}=-g_{k}\end{align*} 则 \begin{align*} \\& x^{\left(k+1\right)}=x^{\left(k\right)}+p_{k}\end{align*}
牛顿法:
输入:目标函数$f\left(x\right)$,梯度$g\left(x\right)=\nabla f\left(x\right)$,海赛矩阵$H\left(x\right)$,精度要求$\varepsilon$
输出:$f\left(x\right)$的极小点$x^{*}$
设牛顿法搜索方向是$p_{k}=-\lambda g_{k}$ 由 \begin{align*} \\& x^{\left(k+1\right)}=x^{\left(k\right)}-H_{k}^{-1}g_{k} \end{align*} 有 \begin{align*} \\& x=x^{\left(k\right)}-\lambda H_{k}^{-1} g_{k}=x^{\left(k\right)}+\lambda p_{k} \end{align*} 则$f\left(x\right)$在$x^{\left(k\right)}$的泰勒展开可近似为 \begin{align*} \\& f\left(x\right)=f\left(x^{\left(k\right)}\right)-\lambda g_{k}^{T} H_{k}^{-1} g_{k}\end{align*} 由于$H_{k}^{-1}$正定,故$g_{k}^{T} H_{k}^{-1} g_{k} > 0$。当$\lambda$为一个充分小的正数时,有$f\left(x\right) < f\left(x^{\left(x\right)}\right)$,即搜索方向$p_{k}$是下降方向。
取$x=x^{\left(k+1\right)}$,由 \begin{align*} \\& \nabla f\left(x\right)=g_{k}+H_{k}\left(x-x^{\left(x\right)}\right)\end{align*} 得 \begin{align*} \\& g_{k+1}-g_{k}=H_{k}\left(x^{\left(k+1\right)}-x^{\left(x\right)}\right)\end{align*} 记$y_{k}=g_{k+1}-g_{k},\delta_{k}=x^{\left(k+1\right)}-x^{\left(k\right)}$,则 \begin{align*} \\& y_{k}=H_{k}\delta_{k} \\ & H_{k}^{-1}y_{k}=\delta_{k}\end{align*} 称为拟牛顿条件。
DFP算法中选择$G_{k}$作为$H_{k}^{-1}$的近似,假设每一步迭代中矩阵$G_{k+1}$是由$G_{k}$加上两个附加项构成,即 \begin{align*} \\& G_{k+1}=G_{k}+P_{k}+Q_{k}\end{align*} 其中,$P_{k}$与$Q_{k}$是待定矩阵。则 \begin{align*} \\& G_{k+1}y_{k}=G_{k}y_{k}+P_{k}y_{k}+Q_{k}y_{k}\end{align*} 为使$G_{k+1}$满足拟牛顿条件,可使$P_{k}$与$Q_{k}$满足 \begin{align*} \\& P_{k}y_{k}=\delta_{k} \\ & Q_{k}y_{k}=-G_{k}y_{k}\end{align*} 可取 \begin{align*} \\& P_{k}= \dfrac{\delta_{k} \delta_{k}^{T}}{\delta_{k}^{T} y_{k}} \\ & Q_{k}=- \dfrac{G_{k}y_{k}y_{k}^{T}G_{k}}{y_{k}^{T}G_{k}y_{k}}\end{align*} 可得矩阵$G_{k+1}$的迭代公式 \begin{align*} \\& G_{k+1}=G_{k}+\dfrac{\delta_{k} \delta_{k}^{T}}{\delta_{k}^{T} y_{k}}- \dfrac{G_{k}y_{k}y_{k}^{T}G_{k}}{y_{k}^{T}G_{k}y_{k}}\end{align*} 可以证明,如果初始矩阵$G_{0}$是正定的,则迭代过程中的每个矩阵$G_{k}$都是正定的。
DFP算法:
输入:目标函数$f\left(x\right)$,梯度$g\left(x\right)=\nabla f\left(x\right)$,精度要求$\varepsilon$
输出:$f\left(x\right)$的极小点$x^{*}$
BFGS算法中选择$B_{k}$逼近海赛矩阵$H_{k}$,相应的拟牛顿条件 \begin{align*} \\& B_{k+1} \delta_{k} = y_{k}\end{align*} 假设每一步迭代中矩阵$B_{k+1}$是由$B_{k}$加上两个附加项构成,即 \begin{align*} \\& B_{k+1}=B_{k}+P_{k}+Q_{k}\end{align*} 其中,$P_{k}$与$Q_{k}$是待定矩阵。则 \begin{align*} \\& B_{k+1}y_{k}=B_{k}y_{k}+P_{k}y_{k}+Q_{k}y_{k}\end{align*} 为使$B_{k+1}$满足拟牛顿条件,可使$P_{k}$与$Q_{k}$满足 \begin{align*} \\& P_{k}\delta_{k}=y_{k} \\ & Q_{k}\delta_{k}=-B_{k}y_{k}\delta_{k}\end{align*} 可取 \begin{align*} \\& P_{k}= \dfrac{y_{k}y_{k}^{T}}{y_{k}^{T}\delta_{k} } \\ & Q_{k}=- \dfrac{B_{k}\delta_{k}\delta_{k}^{T}B_{k}}{\delta_{k}^{T}B_{k}\delta_{k}}\end{align*} 可得矩阵$B_{k+1}$的迭代公式 \begin{align*} \\& B_{k+1}=B_{k}+\dfrac{y_{k}y_{k}^{T}}{y_{k}^{T}\delta_{k} }- \dfrac{B_{k}\delta_{k}\delta_{k}^{T}B_{k}}{\delta_{k}^{T}B_{k}\delta_{k}}\end{align*} 可以证明,如果初始矩阵$B_{0}$是正定的,则迭代过程中的每个矩阵$B_{k}$都是正定的。
BFGS算法:
输入:目标函数$f\left(x\right)$,梯度$g\left(x\right)=\nabla f\left(x\right)$,精度要求$\varepsilon$
输出:$f\left(x\right)$的极小点$x^{*}$
记 \begin{align*} \\& G_{k}=B_{k}^{-1},\quad G_{k+1}=B_{k+1}^{-1}\end{align*} 两次应用Sherman-Morrison公式,得 \begin{align*} \\& G_{k+1}=\left(I- \dfrac{\delta_{k}y_{k}^{T}}{\delta_{k}^{T}y_{k}}\right)G_{k}\left(I-\dfrac{\delta_{k}y_{k}^{T}}{\delta_{k}^{T}y_{k}}\right)^{T}+\dfrac{\delta_{k}\delta_{k}^{T}}{\delta_{k}^{T}y_{k}}\end{align*} 称为BFGS算法关于$G_{k}$的迭代公式。
令由DFP算法$G_{k}$的迭代公式得到的$G_{k+1}$记作$G^{DFP}$,由BFGS算法$G_{k}$的迭代公式得到的$G_{k+1}$记作$G^{BFGS}$, 由于$G^{DFP}$和$G^{BFGS}$均满足拟牛顿条件, 则两者的线性组合 \begin{align*} \\& G_{k+1}=\alpha G^{DFP}+\left(1-\alpha\right) G^{BFGS}\end{align*} 也满足拟牛顿条件,而且是正定的。其中,$0 \leq \alpha \leq 1$。该类算法称为Broyden类算法。