引言
本节将介绍优化算法——经典牛顿法 ( Newton Method ) (\text{Newton Method}) (Newton Method)。
回顾：
下降方向
在线搜索方法——方向角度中介绍了下降方向
(
Descent Direction
)
(\text{Descent Direction})
(Descent Direction)的概念。首先，通过推导得到如果更新方向
P
k
\mathcal P_k
Pk与梯度方向
∇
f
(
x
k
)
\nabla f(x_k)
∇f(xk)之间满足如下关系：
[
∇
f
(
x
k
)
]
T
⋅
P
k
<
0
[\nabla f(x_k)]^T \cdot \mathcal P_k <0
[∇f(xk)]T⋅Pk<0
那么称将更新方向
P
k
\mathcal P_k
Pk称作下降方向。需要注意的是，下降方向是线搜索方法关于方向角度的一个概念，而不是仅存在于梯度下降法。而最速下降方向是与梯度方向相反的方向，也是梯度下降法的选择方向。
下降方向的几何意义
观察上述不等式左侧是向量
∇
f
(
x
k
)
\nabla f(x_k)
∇f(xk)与向量
P
k
\mathcal P_k
Pk的内积形式，将其展开：
∣
∣
∇
f
(
x
k
)
∣
∣
⋅
∣
∣
P
k
∣
∣
⋅
cos
θ
<
0
||\nabla f(x_k)|| \cdot ||\mathcal P_k|| \cdot \cos \theta < 0
∣∣∇f(xk)∣∣⋅∣∣Pk∣∣⋅cosθ<0
这意味着向量
−
∇
f
(
x
k
)
-\nabla f(x_k)
−∇f(xk)与向量
P
k
\mathcal P_k
Pk之间的夹角是锐角。后续使用该方法判断牛顿方向是否为下降方向。
经典牛顿法整体介绍
在之前的系列中优化算法(十)
⇒
\Rightarrow
⇒(十七)介绍了梯度下降法。其迭代过程表示如下：
x
k
+
1
=
x
k
−
α
⋅
∇
f
(
x
k
)
x_{k+1} = x_k - \alpha \cdot \nabla f(x_k)
xk+1=xk−α⋅∇f(xk)
从上式可以看出：梯度下降法的底层逻辑是借助了函数
f
(
⋅
)
f(\cdot)
f(⋅)的一阶信息——在使用梯度下降法时，其前置条件是：函数
f
(
⋅
)
f(\cdot)
f(⋅)至少是一阶可微的。如果
f
(
⋅
)
f(\cdot)
f(⋅)一阶不可微，那么
∇
f
(
⋅
)
\nabla f(\cdot)
∇f(⋅)不存在，自然也无法实现迭代求解。
而牛顿法对函数 f ( ⋅ ) f(\cdot) f(⋅)的要求是： f ( ⋅ ) f(\cdot) f(⋅)至少二阶可微。
而牛顿法同样作为线搜索方法，其数值解的迭代过程表示为如下形式：
x
k
+
1
=
x
k
+
α
k
⋅
P
k
x_{k+1} = x_k + \alpha_k \cdot \mathcal P_k
xk+1=xk+αk⋅Pk
关于步长
α
k
\alpha_k
αk，牛顿法与梯度下降法的处理方式相同。如非精确搜索的
Wolfe
\text{Wolfe}
Wolfe准则，这里不再赘述。作为经典牛顿法，与梯度下降法相反，它的步长并不是重点关注的对象。这里假设每次迭代步骤，其步长
α
k
=
1
\alpha_k=1
αk=1：
α
k
=
1
k
=
1
,
2
,
3
,
⋯
\alpha_k = 1 \quad k=1,2,3,\cdots
αk=1k=1,2,3,⋯
关于方向
P
k
\mathcal P_k
Pk，它是牛顿法与梯度下降法作为线搜索方法的核心区别：
- 梯度下降法的方向就是函数 f ( ⋅ ) f(\cdot) f(⋅)在 x k x_k xk处的负梯度方向： − ∇ f ( x k ) -\nabla f(x_k) −∇f(xk)；
- 牛顿法的方向被称作牛顿方向。本节将介绍牛顿方向并讨论该方向是否为下降方向。
关于牛顿方向
首先将步长
α
k
=
1
\alpha_k = 1
αk=1代入，得到
x
k
+
1
x_{k+1}
xk+1与
x
k
x_k
xk之间新的关系表达：在当前迭代步骤下，
P
k
\mathcal P_k
Pk并未求解出来，使用变量
P
\mathcal P
P进行替换。
x
k
+
1
=
x
k
+
P
x_{k+1} = x_k + \mathcal P
xk+1=xk+P
从而当前迭代步骤下的最优方向
P
k
\mathcal P_k
Pk表示为如下形式：
P
k
=
arg
min
P
f
(
x
k
+
1
)
=
arg
min
P
f
(
x
k
+
P
)
\begin{aligned} \mathcal P_k & = \mathop{\arg\min}\limits_{\mathcal P} f(x_{k+1}) \\ & =\mathop{\arg\min}\limits_{\mathcal P} f(x_k + \mathcal P) \end{aligned}
Pk=Pargminf(xk+1)=Pargminf(xk+P)
如果
P
\mathcal P
P足够小，可以对
f
(
x
k
+
P
)
f(x_k + \mathcal P)
f(xk+P)进行泰勒展开(二阶)：其中
O
(
∣
∣
P
∣
∣
2
)
\mathcal O(||\mathcal P||^2)
O(∣∣P∣∣2)表示高阶无穷小;
∇
2
P
(
x
k
)
\nabla^2 \mathcal P(x_k)
∇2P(xk)则表示
x
k
x_k
xk处的
Hessian Matrix
\text{Hessian Matrix}
Hessian Matrix,一个实对称矩阵。
P
k
=
arg
min
P
{
f
(
x
k
)
+
1
1
!
[
∇
f
(
x
k
)
]
T
P
+
1
2
!
P
T
[
∇
2
f
(
x
k
)
]
⋅
P
+
O
(
∣
∣
P
∣
∣
2
)
}
≈
arg
min
P
{
f
(
x
k
)
+
1
1
!
[
∇
f
(
x
k
)
]
T
P
+
1
2
!
P
T
[
∇
2
f
(
x
k
)
]
⋅
P
}
\begin{aligned} \mathcal P_k & = \mathop{\arg\min}\limits_{\mathcal P} \left\{f(x_k) + \frac{1}{1!} [\nabla f(x_k)]^T \mathcal P + \frac{1}{2!} \mathcal P^T [\nabla^2 f(x_k)] \cdot \mathcal P + \mathcal O(||\mathcal P||^2)\right\} \\ & \approx \mathop{\arg\min}\limits_{\mathcal P} \left\{f(x_k) + \frac{1}{1!} [\nabla f(x_k)]^T \mathcal P + \frac{1}{2!} \mathcal P^T [\nabla^2 f(x_k)] \cdot \mathcal P\right\} \end{aligned}
Pk=Pargmin{f(xk)+1!1[∇f(xk)]TP+2!1PT[∇2f(xk)]⋅P+O(∣∣P∣∣2)}≈Pargmin{f(xk)+1!1[∇f(xk)]TP+2!1PT[∇2f(xk)]⋅P}
由于
x
k
x_k
xk是上一次迭代产生的结果，是已知项；可以将上述大括号内的项看作关于
P
\mathcal P
P的函数：
{
ϕ
(
P
)
=
f
(
x
k
)
+
1
1
!
[
∇
f
(
x
k
)
]
T
P
+
1
2
!
P
T
[
∇
2
f
(
x
k
)
]
⋅
P
P
k
≈
arg
min
P
ϕ
(
P
)
\begin{cases} \begin{aligned} \phi(\mathcal P) & = f(x_k) + \frac{1}{1!} [\nabla f(x_k)]^T \mathcal P + \frac{1}{2!} \mathcal P^T [\nabla^2 f(x_k)] \cdot \mathcal P \\ \quad \\ \mathcal P_k & \approx \mathop{\arg\min}\limits_{\mathcal P} \phi(\mathcal P) \end{aligned} \end{cases}
⎩
⎨
⎧ϕ(P)Pk=f(xk)+1!1[∇f(xk)]TP+2!1PT[∇2f(xk)]⋅P≈Pargminϕ(P)
很明显，
ϕ
(
P
)
\phi(\mathcal P)
ϕ(P)就是一个关于
P
\mathcal P
P的二次函数。并且开口向上，是一个凸二次函数，因此该函数有最小值。因此可以求解
ϕ
(
P
)
\phi(\mathcal P)
ϕ(P)的最小值。关于视频,这里有一些疑问：为什么该二次函数开口向上
?
?
?作为二次项系数的
1
2
[
∇
2
f
(
x
k
)
]
\begin{aligned}\frac{1}{2} [\nabla^2 f(x_k)]\end{aligned}
21[∇2f(xk)]未知，怎么就开口向上了~欢迎小伙伴们一起讨论。
- 求解
ϕ
(
P
)
\phi(\mathcal P)
ϕ(P)关于
P
\mathcal P
P的梯度
∇
ϕ
(
P
)
\nabla \phi(\mathcal P)
∇ϕ(P)：
∇ ϕ ( P ) = ∇ f ( x k ) + [ ∇ 2 f ( x k ) ] ⋅ P \nabla \phi(\mathcal P) = \nabla f(x_k) + [\nabla^2 f(x_k)] \cdot \mathcal P ∇ϕ(P)=∇f(xk)+[∇2f(xk)]⋅P - 令
∇
ϕ
(
P
)
≜
0
\nabla \phi(\mathcal P) \triangleq 0
∇ϕ(P)≜0，有：
∇ 2 f ( x k ) ⋅ P = − ∇ f ( x k ) \nabla^2 f(x_k) \cdot \mathcal P = -\nabla f(x_k) ∇2f(xk)⋅P=−∇f(xk)
观察： Hessian Matrix \text{Hessian Matrix} Hessian Matrix是一个 n × n n \times n n×n的实对称矩阵； P , − ∇ f ( x k ) \mathcal P,-\nabla f(x_k) P,−∇f(xk)均是 n × 1 n \times 1 n×1的列向量，因而 ∇ 2 f ( x k ) ⋅ P = − ∇ f ( x k ) \nabla^2 f(x_k) \cdot \mathcal P = -\nabla f(x_k) ∇2f(xk)⋅P=−∇f(xk)表达的是一个方程组，我们也将方程组本身称作牛顿方程。关于牛顿方程的解，自然是 ϕ ( P ) \phi(\mathcal P) ϕ(P)的最小值。
从牛顿方程也可以看出：如果
Hassian Matrix
⇒
∇
2
f
(
x
k
)
\text{Hassian Matrix} \Rightarrow \nabla^2 f(x_k)
Hassian Matrix⇒∇2f(xk)是正定矩阵，完全可以通过两边求逆的方式求出
P
\mathcal P
P的最小解：
P
=
−
[
∇
2
f
(
x
k
)
]
−
1
∇
f
(
x
k
)
\mathcal P = - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)
P=−[∇2f(xk)]−1∇f(xk)
相反，如果
Hessian Matrix
⇒
∇
2
f
(
x
)
\text{Hessian Matrix} \Rightarrow \nabla^2 f(x)
Hessian Matrix⇒∇2f(x)是奇异矩阵，也就是说：该矩阵不满秩，无法求逆。那么只能说：牛顿方程
∇
2
f
(
x
k
)
P
=
−
∇
f
(
x
k
)
\nabla^2 f(x_k) \mathcal P = -\nabla f(x_k)
∇2f(xk)P=−∇f(xk)的解，就是最小解
P
k
\mathcal P_k
Pk。
判断牛顿方向是否为下降方向
-
如果 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk)是正定的，因而本次迭代的最优方向 P k = [ ∇ 2 f ( x k ) ] − 1 ∇ f ( x k ) \mathcal P_k = [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) Pk=[∇2f(xk)]−1∇f(xk)。将 P k \mathcal P_k Pk与负梯度方向 − ∇ f ( x k ) -\nabla f(x_k) −∇f(xk)作内积，观察两向量之间的夹角：
[ − ∇ f ( x k ) ] T ⋅ P k = − [ ∇ f ( x k ) ] T ⋅ [ ∇ 2 f ( x k ) ] − 1 ⋅ ∇ f ( x k ) \begin{aligned} [- \nabla f(x_k)]^T \cdot \mathcal P_k = -[\nabla f(x_k)]^T \cdot [\nabla^2 f(x_k)]^{-1} \cdot \nabla f(x_k) \end{aligned} [−∇f(xk)]T⋅Pk=−[∇f(xk)]T⋅[∇2f(xk)]−1⋅∇f(xk)
由于 [ ∇ 2 f ( x k ) ] n × n [\nabla^2 f(x_k)]_{n \times n} [∇2f(xk)]n×n是正定矩阵，那么它的逆矩阵 [ ∇ 2 f ( x k ) ] n × n − 1 [\nabla^2 f(x_k)]_{n \times n}^{-1} [∇2f(xk)]n×n−1同样也是正定矩阵。根据正定矩阵的性质：如果 A \mathcal A A是正定矩阵，对于 ∀ x ∈ R n \forall x \in \mathbb R^n ∀x∈Rn，且 x ≠ 0 x \neq 0 x=0，均有：
x T A x > 0 x^T \mathcal A x > 0 xTAx>0
因此，项 [ ∇ f ( x k ) ] T ⋅ [ ∇ 2 f ( x k ) ] − 1 ⋅ ∇ f ( x k ) > 0 [\nabla f(x_k)]^T \cdot [\nabla^2 f(x_k)]^{-1} \cdot \nabla f(x_k) > 0 [∇f(xk)]T⋅[∇2f(xk)]−1⋅∇f(xk)>0恒成立。从而 [ − ∇ f ( x k ) ] T ⋅ P k = − [ ∇ f ( x k ) ] T ⋅ [ ∇ 2 f ( x k ) ] − 1 ⋅ ∇ f ( x k ) < 0 [- \nabla f(x_k)]^T \cdot \mathcal P_k = -[\nabla f(x_k)]^T \cdot [\nabla^2 f(x_k)]^{-1} \cdot \nabla f(x_k) < 0 [−∇f(xk)]T⋅Pk=−[∇f(xk)]T⋅[∇2f(xk)]−1⋅∇f(xk)<0恒成立。因此 P k \mathcal P_k Pk一定是下降方向。 -
如果 ∇ 2 f ( x k ) \nabla^2 f(x_k) ∇2f(xk)是奇异矩阵，由于目标函数 f ( ⋅ ) f(\cdot) f(⋅)未知，从而无法得到牛顿方程的具体解结果。因此 P k \mathcal P_k Pk未必是下降方向。文章来源：https://www.toymoban.com/news/detail-670455.html
相关参考：
【优化算法】经典牛顿法-总体介绍文章来源地址https://www.toymoban.com/news/detail-670455.html
到了这里，关于机器学习笔记之优化算法(十八)经典牛顿法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
