您的位置: 首页  >  文章  >  无约束优化问题之梯度下降法、牛顿法原理

无约束优化问题之梯度下降法、牛顿法原理

分类: 文章 • 2024-05-04 12:24:10

无约束优化问题是机器学习中最普遍、最简单的优化问题

x∗=minxf(x),x∈Rnx^{*}=\mathop{min}\limits_{x}f_{(x)},x\in R^{n}

梯度下降法推导

对于只有两个维度的函数f(x,y)f_{(x,y)},如下图所示。

无约束优化问题之梯度下降法、牛顿法原理
如果现在在PP点，假设∣PP′∣=L,∠P′Px=θ|PP'|=L,\angle P'Px=\theta，则由PP到P′P'，函数的单位长度变化量为：
f(x0+Lcos⁡θ,y0+Lsin⁡θ)−f(x0,y0)L\frac{f_{(x_{0}+L\cos{\theta}, y_{0}+L\sin{\theta})}-f_{(x_{0}, y_{0})}}{L}
=f(x0+Lcos⁡θ,y0+Lsin⁡θ)−f(x0+Lcos⁡θ,y0)L+f(x0+Lcos⁡θ,y0)−f(x0,y0)L=\frac{f_{(x_{0}+L\cos{\theta}, y_{0}+L\sin{\theta})}-f_{(x_{0}+L\cos{\theta}, y_{0})}}{L}+\frac{f_{(x_{0}+L\cos{\theta}, y_{0})}-f_{(x_{0}, y_{0})}}{L}
=sin⁡θf(x0+Lcos⁡θ,y0+Lsin⁡θ)−f(x0+Lcos⁡θ,y0)Lsin⁡θ+cos⁡θf(x0+Lcos⁡θ,y0)−f(x0,y0)Lcos⁡θ=\sin{\theta}\frac{f_{(x_{0}+L\cos{\theta}, y_{0}+L\sin{\theta})}-f_{(x_{0}+L\cos{\theta}, y_{0})}}{L\sin{\theta}}+\cos{\theta}\frac{f_{(x_{0}+L\cos{\theta}, y_{0})}-f_{(x_{0}, y_{0})}}{L\cos{\theta}}
=sin⁡θfy(x0,y0)+cos⁡θfx(x0,y0)(L→0)=\sin{\theta}f_{y(x_{0},y_{0})}+\cos{\theta}f_{x(x_{0},y_{0})}\quad(\mathop{L\rightarrow0})
由柯西不等式：
<m,n>=∣∣m∣∣⋅∣∣n∣∣⋅cosθ<m, n>=||m||\cdot||n||\cdot cos{\theta}
<m,n>2=∣∣m∣∣2⋅∣∣n∣∣2⋅cos2θ≤∣∣m∣∣2⋅∣∣n∣∣2<m, n>^{2}=||m||^{2}\cdot||n||^{2}\cdot cos^{2}{\theta}\leq||m||^{2}\cdot||n||^{2}
且只有当θ=0\theta =0即两向量共线时等号成立。
令m=(sin⁡θ,cos⁡θ),n=(fy,fx)m=(\sin{\theta},\cos{\theta}),n=(f_{y},f_{x})，则
(sin⁡θ⋅fy+cos⁡θ⋅fx)2≤(sin⁡2θ+cos⁡2θ)(fy2+fx2)=fy2+fx2(\sin{\theta}\cdot f_{y}+\cos{\theta}\cdot f_{x})^{2}\leq(\sin^{2}{\theta}+\cos^{2}{\theta})(f_{y}^{2}+f_{x}^{2})=f_{y}^{2}+f_{x}^{2}
"=""="成立的条件是两向量共线，即
sin⁡θcos⁡θ=fyfx\frac{\sin{\theta}}{\cos{\theta}}=\frac{f_{y}}{f_{x}}
此时函数的单位长度变化量最大。
而sin⁡θcos⁡θ=fyfx\frac{\sin{\theta}}{\cos{\theta}}=\frac{f_{y}}{f_{x}}意味着单位长度变化量最大的方向为梯度方向。
类比于有nn个自变量的函数f(x1,x2……xn)f_{(x_{1},x_{2}……x_{n})}，其梯度为(∂f∂x1,∂f∂x2……∂f∂xn)(\frac{\partial f}{\partial x_{1}},\frac{\partial f}{\partial x_{2}}……\frac{\partial f}{\partial x_{n}})，则延梯度方向函数增长最快。
基于此原理，梯度下降法取梯度的反方向作为移动方向，延此方向函数下降最快。

牛顿法推导

初级版本

无约束优化问题之梯度下降法、牛顿法原理
对于minf(x)minf_{(x)}来说，需要g(x)=f(x)′=0g_{(x)}=f_{(x)}^{'}=0。
xnx_{n}是第nn个点的横坐标，我们需要求出g(x)=0g_{(x)}=0时的横坐标。
首先对第nn个点求切线为：
y−g(xn)=g(xn)′(x−xn)y-g_{(x_{n})}=g_{(x_{n})}^{'}(x-x_{n})
令y=0y=0得到x=xn−g(xn)g(xn)′x=x_{n}-\frac{g_{(x_{n})}}{g_{(x_{n})}^{'}}
用f(x)′f_{(x)}^{'}代替g(x)g_{(x)}，得：
xn+1=xn−f(xn)′f(xn)′′x_{n+1}=x_{n}-\frac{f_{(x_{n})}^{'}}{f_{(x_{n})}^{''}}

高级版本

无约束优化问题之梯度下降法、牛顿法原理
要求minf(x)minf_{(x)}，
先将f(x)f_{(x)}进行泰勒公式展开，得：
f(x)=f(xn)+f(xn)′(x−xn)+f(xn)′′2!(x−xn)2+……f_{(x)}=f_{(x_{n})}+f_{(x_{n})}^{'}(x-x_{n})+\frac{f_{(x_{n})}^{''}}{2!}(x-x_{n})^{2}+……
将只保留有关xx的项，得：
f(x)=f(xn)′′2x2+(f(xn)′−xnf(xn)′′)x+……f_{(x)}=\frac{f_{(x_{n})}^{''}}{2}x^{2}+(f_{(x_{n})}^{'}-x_{n}f_{(x_{n})}^{''})x+……
此时已将f(x)f_{(x)}化为一个一元二次函数。
所以当此函数取最小值时的横坐标为：
xn+1=−b2a=−f(xn)′−xnf(xn)′′f(xn)′′=xn−f(xn)′f(xn)′′x_{n+1}=-\frac{b}{2a}=-\frac{f_{(x_{n})}^{'}-x_{n}f_{(x_{n})}^{''}}{f_{(x_{n})}^{''}}=x_{n}-\frac{f_{(x_{n})}^{'}}{f_{(x_{n})}^{''}}

相关推荐