思維導圖
- 牛頓法求解最優化問題原理
- 牛頓法與梯度下降法的差異
- 擬牛頓法
牛頓法求解最優化問題原理
- 原理闡述：
-
f
(
x
)
f(x)
f(x)的取得最小值(極小值)的必要條件是
?
f
(
x
)
=
0
\nabla{f(x)}=0
?f(x)=0，所以牛頓法就是來逼近
x
?
x^*
x?，使
?
f
(
x
?
)
=
0
\nabla{f(x^*)}=0
?f(x?)=0，
-
f
(
x
)
f(x)
f(x)的取得最小值(極小值)的必要條件是
?
f
(
x
)
=
0
\nabla{f(x)}=0
?f(x)=0，所以牛頓法就是來逼近
x
?
x^*
x?，使
?
f
(
x
?
)
=
0
\nabla{f(x^*)}=0
?f(x?)=0，
- 程序推導：
-
f
(
x
?
)
f(\vec{x})
f(x
)在
x
0
?
\vec{x_0}
x0?
?處的二階泰勒展開式為
f ( x ) = f ( x 0 ) + ? f ( x 0 ) T ( x ? x 0 ) + 1 2 ( x ? x 0 ) T ? 2 f ( x 0 ) ( x ? x 0 ) + o ( ∣ ∣ x ? x 0 ∣ ∣ 2 ) f(x)=f(x_0)+\nabla{f(x_0)}^T(x-x_0)+\frac{1}{2}(x-x_0)^T\nabla^2f(x_0)(x-x_0)+o(||x-x_0||^2) f(x)=f(x0?)+?f(x0?)T(x?x0?)+21?(x?x0?)T?2f(x0?)(x?x0?)+o(∣∣x?x0?∣∣2) - 將二次項以及二次項的高階無窮小項舍去，可近似得
f ( x ) = f ( x 0 ) + ? f ( x ) T ( x ? x 0 ) f(x)=f(x_0)+\nabla{f(x)}^T(x-x_0) f(x)=f(x0?)+?f(x)T(x?x0?) - 對上式子兩邊同求求梯度
? f ( x ) = ? f ( x 0 ) + ? 2 f ( x 0 ) ( x ? x 0 ) \nabla{f(x)}=\nabla{f(x_0)}+\nabla^2f(x_0)(x-x_0) ?f(x)=?f(x0?)+?2f(x0?)(x?x0?) - 令梯度等于0，即牛頓法原理的核心：梯度為0，求得駐點，駐點處可能取得極值
? f ( x 0 ) + ? 2 f ( x 0 ) ( x ? x 0 ) = 0 \nabla{f(x_0)}+\nabla^2f(x_0)(x-x_0)=0 ?f(x0?)+?2f(x0?)(x?x0?)=0 - 變式可得：
x = x 0 ? ( ? 2 f ( x 0 ) ) ? 1 ? f ( x 0 ) x=x_0-(\nabla^2f(x_0))^{-1}\nabla{f(x_0)} x=x0??(?2f(x0?))?1?f(x0?) - 由于推導程序中忽略了二階及二階以上的無窮小，故而需要反復的迭代來求解，
-
f
(
x
?
)
f(\vec{x})
f(x
)在
x
0
?
\vec{x_0}
x0?
?處的二階泰勒展開式為
- 案例展示：求取
f
(
x
,
y
)
=
x
2
+
y
2
+
x
f(x,y)=x^2+y^2+x
f(x,y)=x2+y2+x的極值
- 將
f
(
x
,
y
)
=
x
2
+
y
2
+
x
f(x,y)=x^2+y^2+x
f(x,y)=x2+y2+x在
(
x
,
y
)
(x,y)
(x,y)處展開成二階泰勒
f ( x + Δ x , y + Δ y ) = f ( x , y ) + [ Δ x Δ y ] [ f x ′ f y ′ ] + 1 2 [ Δ x Δ y ] [ f x x ′ ′ f x y ′ ′ f y x ′ ′ f y y ′ ′ ] [ Δ x Δ y ] + o n f(x+\Delta{x},y+\Delta{y})=f(x,y)+\left[ \begin{matrix} \Delta{x} & \Delta{y} \end{matrix} \right] \left[ \begin{matrix} f'_x\\\\f'_y \end{matrix} \right]+\frac{1}{2}\left[ \begin{matrix} \Delta{x} & \Delta{y} \end{matrix} \right] \left[ \begin{matrix} f''_{xx} & f''_{xy}\\\\f''_{yx} & f''_{yy} \end{matrix} \right]\left[ \begin{matrix} \Delta{x}\\\\\Delta{y} \end{matrix} \right]+o^n f(x+Δx,y+Δy)=f(x,y)+[Δx?Δy?]???fx′?fy′?????+21?[Δx?Δy?]???fxx′′?fyx′′??fxy′′?fyy′′????????ΔxΔy????+on - 由梯度向量為
[
2
x
+
1
2
y
]
\left[ \begin{matrix} 2x+1 \\ 2y \end{matrix} \right]
[2x+12y?]，Heissan矩陣為
[
2
0
0
2
]
\left[ \begin{matrix} 2 &0 \\ 0 & 2 \end{matrix} \right]
[20?02?]，帶入上式可得：
f ( x + Δ x , y + Δ y ) = f ( x , y ) + ( 2 x + 1 ) ? Δ x + 2 y ? Δ y + o 2 f(x+\Delta{x},y+\Delta{y})=f(x,y)+(2x+1)*\Delta{x}+2y*\Delta{y}+o^2 f(x+Δx,y+Δy)=f(x,y)+(2x+1)?Δx+2y?Δy+o2 - 舍去二階及二階以上的無窮小，可得式子
f ( x + Δ x , y + Δ y ) = f ( x , y ) + ( 2 x + 1 ) ? Δ x + 2 y ? Δ y f(x+\Delta{x},y+\Delta{y})=f(x,y)+(2x+1)*\Delta{x}+2y*\Delta{y} f(x+Δx,y+Δy)=f(x,y)+(2x+1)?Δx+2y?Δy - 對
f
(
x
+
Δ
x
,
y
+
Δ
y
)
f(x+\Delta{x},y+\Delta{y})
f(x+Δx,y+Δy)求偏度(即分別對
x
x
x和
y
y
y求偏導數)，可得：
? f ( x + Δ x , y + Δ y ) ? x = ? f ( x , y ) ? x + 2 ? Δ x = 0 \frac{\partial f(x+\Delta{x},y+\Delta{y})}{\partial x}=\frac{\partial f(x,y)}{\partial x}+2*\Delta{x}=0 ?x?f(x+Δx,y+Δy)?=?x?f(x,y)?+2?Δx=0
? f ( x + Δ x , y + Δ y ) ? y = ? f ( x , y ) ? y + 2 ? Δ y = 0 \frac{\partial f(x+\Delta{x},y+\Delta{y})}{\partial y}=\frac{\partial f(x,y)}{\partial y}+2*\Delta{y}=0 ?y?f(x+Δx,y+Δy)?=?y?f(x,y)?+2?Δy=0 - 經整理可得：
{ 2 x + 1 + 2 Δ x = 0 2 y + 2 Δ y = 0 \left \{ \begin{array}{c} 2x+1+2\Delta{x}=0 \\ 2y+2\Delta{y}=0 \end{array} \right. {2x+1+2Δx=02y+2Δy=0? - 又由
x
=
x
k
x=x_{k}
x=xk?，
y
=
y
k
y=y_{k}
y=yk?以及
Δ
x
=
x
k
+
1
?
x
k
\Delta{x}=x_{k+1}-x_{k}
Δx=xk+1??xk?，
Δ
y
=
y
k
+
1
?
y
k
\Delta{y}=y_{k+1}-y_{k}
Δy=yk+1??yk?，帶入可得：
{ 2 x k + 1 + 2 ( x k + 1 ? x k ) = 0 2 y k + 2 ( y k + 1 ? y k ) = 0 \left \{ \begin{array}{c} 2x_{k}+1+2(x_{k+1}-x_{k})=0 \\ 2y_{k}+2(y_{k+1}-y_{k})=0 \end{array} \right. {2xk?+1+2(xk+1??xk?)=02yk?+2(yk+1??yk?)=0? - 移項，解出
(
x
k
+
1
,
y
k
+
1
)
(x_{k+1},y_{k+1})
(xk+1?,yk+1?)
[ x k + 1 y k + 1 ] = [ x k y k ] ? [ 2 x k + 1 2 2 y k 2 ] = [ ? 0.5 0 ] \left[ \begin{matrix} x_{k+1} \\ y_{k+1} \end{matrix} \right]=\left[ \begin{matrix} x_{k} \\ y_{k} \end{matrix} \right]-\left[ \begin{matrix} \frac{2x_k+1}{2} \\\\ \frac{2y_k}{2} \end{matrix} \right]=\left[ \begin{matrix} -0.5\\\\0 \end{matrix} \right] [xk+1?yk+1??]=[xk?yk??]????22xk?+1?22yk??????=????0.50????
- 將
f
(
x
,
y
)
=
x
2
+
y
2
+
x
f(x,y)=x^2+y^2+x
f(x,y)=x2+y2+x在
(
x
,
y
)
(x,y)
(x,y)處展開成二階泰勒
牛頓法與梯度下降法的差異
- 推導起點都是 f ( x ? ) f(\vec{x}) f(x )的泰勒展開式，且二階及更高階無窮小的影響都用步長 γ \gamma γ接近于0來保證( x + Δ x x+\Delta{x} x+Δx在 x x x的鄰域內)；
- 梯度下降法后續的處理為：
f ( x + Δ x ) ? f ( x ) = ? f ( x ) ? Δ x ≤ 0 f(x+\Delta{x})-f(x)=\nabla{f(x)}*\Delta{x}\leq0 f(x+Δx)?f(x)=?f(x)?Δx≤0恒成立，所以要求 Δ x = ? γ ? f ( x ) \Delta{x}=-\gamma\nabla{f(x)} Δx=?γ?f(x) - 牛頓法后續的處理為：
f ( x + Δ x ) = f ( x ) + ? f ( x ) ? Δ x ? f ( x + Δ x ) = ? f ( x ) + ? 2 f ( x ) ? Δ x = 0 f(x+\Delta{x})=f(x)+\nabla{f(x)}*\Delta{x} \\ \nabla{f(x+\Delta{x})}=\nabla{f(x)}+\nabla^2{f(x)}*\Delta{x}=0 f(x+Δx)=f(x)+?f(x)?Δx?f(x+Δx)=?f(x)+?2f(x)?Δx=0
然后兩邊求梯度并讓梯度等于0，再經整理可得 Δ x = ? ? f ( x ) ? 2 f ( x ) \Delta{x}=-\frac{\nabla{f(x)}}{\nabla^2{f(x)}} Δx=??2f(x)?f(x)? - 牛頓法要求Hessian矩陣要可逆
- 牛頓法比梯度下降法更容易收斂
擬牛頓法
- 使用場景： 如果Hessian矩陣不可逆，牛頓法難以使用
- 解決方案： 構造一個近似Hessian矩陣或其逆矩陣的正定對稱矩陣，用來代替Hessian矩陣
- 構造方法： BFGS演算法
擬牛頓法——BFGS演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250221.html
標籤：其他
上一篇：三分法求函式極值
下一篇：第一周學習報告