【ML】梯度下降/牛顿法/拟牛顿法/DFP/BFGS

梯度下降/牛顿法/拟牛顿法/DFP/BFGS"/>

【ML】梯度下降/牛顿法/拟牛顿法/DFP/BFGS

导航

• 梯度下降法
• 牛顿法
• 拟牛顿法
• DFP
• BFGS
• Broyden类算法
• 参考文献

梯度下降法

设 f ( x ) f(x) f(x)在 R n \mathbb{R}^n Rn上具有一阶连续偏导数，求解无约束优化问题为
min ⁡ x ∈ R n f ( x ) \min\limits_{x\in\mathbb{R}^n}f(x) x∈Rnmin​f(x)
选取合适的初值 x ( 0 ) x^{(0)} x(0)，在负梯度方向上迭代更新 x x x的值.
将 f ( x ) f(x) f(x)在第 k k k次迭代 x ( k ) x^{(k)} x(k)附近Taylor展开
f ( x ) = f ( x ( k ) ) + g k T ( x − x ( k ) ) f(x)=f(x^{(k)})+g_k^T(x-x^{(k)}) f(x)=f(x(k))+gkT​(x−x(k))
其中 g k = ∇ f ( x ( k ) ) g_k=\nabla f(x^{(k)}) gk​=∇f(x(k)).
第 k + 1 k+1 k+1次迭代值为
x ( k + 1 ) ← x ( k ) + λ k p k x^{(k+1)}\leftarrow x^{(k)}+\lambda_kp_k x(k+1)←x(k)+λk​pk​
其中 p k p_k pk​表示搜索方向，取函数下降最快的负梯度方向 p k = − ∇ f ( x ( k ) ) p_k=-\nabla f(x^{(k)}) pk​=−∇f(x(k))， λ k \lambda_k λk​是步长，由一维线性搜索确定，满足方程
f ( x ( k ) + λ k p k ) = min ⁡ λ ≥ 0 f ( x ( k ) + λ p k ) f(x^{(k)}+\lambda_kp_k)=\min_{\lambda\geq 0} f(x^{(k)}+\lambda p_k) f(x(k)+λk​pk​)=λ≥0min​f(x(k)+λpk​)
当满足收敛条件
∥ f ( x ( k + 1 ) ) − f ( x ( k ) ) ∥ < ε \lVert f(x^{(k+1)})-f(x^{(k)})\rVert<\varepsilon ∥f(x(k+1))−f(x(k))∥<ε
或者
∥ x ( k + 1 ) − x ( k ) ∥ < ε \lVert x^{(k+1)}-x^{(k)}\rVert<\varepsilon ∥x(k+1)−x(k)∥<ε
停止迭代
当目标函数为凸函数时，梯度下降可以求出全局最优解.

牛顿法

牛顿法也是求解无约束问题的常用方法，收敛速度较快，但是每一步需要求解目标函数的Hessian矩阵的逆，算法时间复杂度较高.
设 f ( x ) f(x) f(x)具有二阶连续偏导数，第 k k k次迭代值为 x ( k ) x^{(k)} x(k)，可将 f ( x ) f(x) f(x)在 x ( k ) x^{(k)} x(k)附近二阶Tylor展开
f ( x ) = f ( x ( k ) ) + g k T ( x − x ( k ) ) + 1 2 ( x − x ( k ) ) T H ( x ( k ) ) ( x − x ( k ) ) f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})+\frac{1}{2}(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)}) f(x)=f(x(k))+gkT​(x−x(k))+21​(x−x(k))TH(x(k))(x−x(k))
其中 H ( x ( k ) ) H(x^{(k)}) H(x(k))是 f ( x ) f(x) f(x)的Hessian矩阵
H ( x ) = [ ∂ 2 f ∂ x i ∂ x j ] n × n H(x)=\bigg[\frac{\partial^2f}{\partial x_i \partial x_j}\bigg]_{n\times n} H(x)=[∂xi​∂xj​∂2f​]n×n​
根据极小值必要条件
∇ f ( x ) = 0 \nabla f(x)=0 ∇f(x)=0
每次从点 x ( k ) x^{(k)} x(k)开始，设
∇ f ( x ( k + 1 ) ) = 0 \nabla f(x^{(k+1)})=0 ∇f(x(k+1))=0
对Taylor二阶展开两端同时对 x x x求导得到
∇ f ( x ) = ∇ f ( x ( k + 1 ) ) + g k + H k ( x ( k + 1 ) − x ( k ) ) = 0 ⇒ g k + H k ( x ( k + 1 ) − x ( k ) ) = 0 (1) \nabla f(x)=\nabla f(x^{(k+1)})+g_k+H_k(x^{(k+1)}-x^{(k)})=0\\ \Rightarrow g_k+H_k(x^{(k+1)}-x^{(k)})=0\tag{1} ∇f(x)=∇f(x(k+1))+gk​+Hk​(x(k+1)−x(k))=0⇒gk​+Hk​(x(k+1)−x(k))=0(1)
可以解出
x ( k + 1 ) = x ( k ) − H k − 1 g k x^{(k+1)}=x^{(k)}-H_k^{-1}g_k x(k+1)=x(k)−Hk−1​gk​
令 p k = − H k − 1 g k p_k=-H_k^{-1}g_k pk​=−Hk−1​gk​
得到
x ( k + 1 ) = x ( k ) + p k x^{(k+1)}=x^{(k)}+p_k x(k+1)=x(k)+pk​

拟牛顿法

拟牛顿法通过正定矩阵近似Hessian矩阵的逆或者Hessian矩阵，加快了算法计算速度. 在牛顿法中，计算 H k − 1 H_k^{-1} Hk−1​的时间复杂度较高，考虑使用一个 n n n阶矩阵 G k G_k Gk​去近似 H k − 1 H_k^{-1} Hk−1​.
由 ( 1 ) (1) (1)式可得
g k + 1 − g k = H k ( x ( k + 1 ) − x ( k ) ) g_{k+1}-g_k=H_k(x^{(k+1)}-x^{(k)}) gk+1​−gk​=Hk​(x(k+1)−x(k))
令 y k = g k + 1 − g k ， δ k = x ( k + 1 ) − x ( k ) y_k=g_{k+1}-g_k， \delta_k=x^{(k+1)}-x^{(k)} yk​=gk+1​−gk​，δk​=x(k+1)−x(k)
可以得到拟牛顿条件
y k = H k δ k y_k=H_k\delta_k yk​=Hk​δk​
或者
H k − 1 y k = δ k H_k^{-1}y_k=\delta_k Hk−1​yk​=δk​
当 H k H_k Hk​为正定时，可以保证 p k = − H k − 1 g k p_k=-H_k^{-1}g_k pk​=−Hk−1​gk​是下降方向.
由
x = x ( k ) + λ p k = x ( k ) − λ H k − 1 g k x=x^{(k)}+\lambda p_k=x^{(k)}-\lambda H_k^{-1}g_k x=x(k)+λpk​=x(k)−λHk−1​gk​
f ( x ) f(x) f(x)在 x ( k ) x^{(k)} x(k)的二阶Taylor展开可以表示为
f ( x ) = f ( x ( k ) ) − λ g k T H k − 1 g k f(x)=f(x^{(k)})-\lambda g_k^TH_k^{-1}g_k f(x)=f(x(k))−λgkT​Hk−1​gk​
其中 λ \lambda λ是一个充分小的正数，所以 p k p_k pk​是下降方向.
令正定阵 G k + 1 G_{k+1} Gk+1​近似 H k − 1 H_k^{-1} Hk−1​，即 G k G_k Gk​满足拟牛顿条件
G k + 1 y k = δ k G_{k+1}y_k=\delta_k Gk+1​yk​=δk​
每次迭代可以更新矩阵 G k G_k Gk​
G k + 1 = G k + Δ G k G_{k+1}=G_k+\Delta G_k Gk+1​=Gk​+ΔGk​

DFP

DFP算法设置 G k + 1 G_{k+1} Gk+1​为如下结构
G k + 1 = G k + P k + Q k G_{k+1}=G_k+P_k+Q_k Gk+1​=Gk​+Pk​+Qk​
其中 P k P_k Pk​和 Q k Q_k Qk​为待定矩阵，即
G k + 1 y k = G k y k + P k y k + Q k y k G_{k+1}y_k=G_ky_k+P_ky_k+Q_ky_k Gk+1​yk​=Gk​yk​+Pk​yk​+Qk​yk​
为了满足拟牛顿条件
G k + 1 y k = δ k G_{k+1}y_k=\delta_k Gk+1​yk​=δk​
令
{ P k y k = δ k ⇔ P k = δ k δ k T δ k T y k Q k y k = − G k y k ⇔ Q k = − G k y k y k T G k y k T G k y k \left\{ \begin{aligned} &P_ky_k=\delta_k\Leftrightarrow P_k=\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}\\ &Q_ky_k=-G_ky_k\Leftrightarrow Q_k=-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k} \end{aligned} \right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧​​Pk​yk​=δk​⇔Pk​=δkT​yk​δk​δkT​​Qk​yk​=−Gk​yk​⇔Qk​=−ykT​Gk​yk​Gk​yk​ykT​Gk​​​
可以得到迭代公式
G k + 1 = G k + δ k δ k T δ k T y k − G k y k y k T G k y k T G k y k G_{k+1}=G_k+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k} Gk+1​=Gk​+δkT​yk​δk​δkT​​−ykT​Gk​yk​Gk​yk​ykT​Gk​​

BFGS

考虑使用矩阵 B k B_k Bk​逼近Hessian矩阵 H H H，根据拟牛顿条件
B k + 1 δ k = y k B_{k+1}\delta_k=y_k Bk+1​δk​=yk​
可以得到一组迭代公式
B k + 1 = B k + P k + Q k B k + 1 δ k = B k δ k + P K δ k + Q k δ k B_{k+1}=B_k+P_k+Q_k\\ B_{k+1}\delta_k=B_k\delta_k+P_K\delta_k+Q_k\delta_k Bk+1​=Bk​+Pk​+Qk​Bk+1​δk​=Bk​δk​+PK​δk​+Qk​δk​
令
{ P k δ k = y k ⇔ P k = y k y k T y k T δ k Q k δ k = − B k δ k ⇔ Q k = − B k δ k δ k T B k δ k T B k δ k \left\{ \begin{aligned} &P_k\delta_k=y_k\Leftrightarrow P_k=\frac{y_ky_k^T}{y_k^T\delta_k}\\ &Q_k\delta_k=-B_k\delta_k\Leftrightarrow Q_k=-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k} \end{aligned} \right. ⎩⎪⎪⎪⎨⎪⎪⎪⎧​​Pk​δk​=yk​⇔Pk​=ykT​δk​yk​ykT​​Qk​δk​=−Bk​δk​⇔Qk​=−δkT​Bk​δk​Bk​δk​δkT​Bk​​​
得到迭代公式
B k + 1 = B k + y k y k T y k T δ k − B k δ k δ k T B k δ k T B k δ k (2) B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}\tag{2} Bk+1​=Bk​+ykT​δk​yk​ykT​​−δkT​Bk​δk​Bk​δk​δkT​Bk​​(2)

Broyden类算法

根据 G k G_k Gk​和 B k B_k Bk​之间的关系， G k = B k − 1 ， G k + 1 = B k + 1 − 1 G_k=B_k^{-1}，G_{k+1}=B_{k+1}^{-1} Gk​=Bk−1​，Gk+1​=Bk+1−1​. 对 ( 2 ) (2) (2)使用Sherman-Morrison公式可以得到

假设 A A A是 n n n阶可逆矩阵， u u u和 v v v是 n n n维向量，且 A + u v T A+uv^T A+uvT也是可逆矩阵，则有
( A + u v T ) − 1 = A − 1 − A − 1 u v T A − 1 1 + v T A − 1 u (A+uv^T)^{-1}=A^{-1}-\frac{A^{-1}uv^TA^{-1}}{1+v^TA^{-1}u} (A+uvT)−1=A−1−1+vTA−1uA−1uvTA−1​

G k + 1 = ( I − δ k y k T δ k T y k ) G k ( I − δ k y k T δ k T y k ) T + δ k δ k T δ k T y k G_{k+1}=(I-\frac{\delta_ky_k^T}{\delta_k^Ty_k})G_k(I-\frac{\delta_ky_k^T}{\delta_k^Ty_k})^T+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k} Gk+1​=(I−δkT​yk​δk​ykT​​)Gk​(I−δkT​yk​δk​ykT​​)T+δkT​yk​δk​δkT​​
可以得到一类拟牛顿法
G k + 1 = α G D F P + ( 1 − α ) G B F G S ， 0 ≤ α ≤ 1 G_{k+1}=\alpha G^{DFP}+(1-\alpha)G^{BFGS}， 0\leq\alpha\leq 1 Gk+1​=αGDFP+(1−α)GBFGS，0≤α≤1

参考文献

统计学习方法 清华大学出版社 李航