牛顿法,大致的思想是用泰勒公式的前几项来代替原来的函数,然后对函数进行求解和优化。牛顿法和应用于最优化的牛顿法稍微有些差别。
牛顿法用来迭代的求解一个方程的解,原理如下: 对于一个函数f(x),它的泰勒级数展开式是这样的
\[f(x) = f(x_0) + f'(x_0)(x-x_0) + \frac{1}{2} f”(x_0)(x-x_0)^2 + …+\frac{1}{n!}f^{n}(x_0)(x-x_0)^n \]
当使用牛顿法来求一个方程解的时候,它使用泰勒级数前两项来代替这个函数,即用\(\phi(x)代替f(x)\),其中:
\[\phi(x) = f(x_0) + f'(x_0)(x-x_0) \]
令\(\phi(x) = 0\),则 \(x = x_0 – \frac{f(x_0)}{ f'(x_0)}\)。 所以,牛顿法的迭代公式是\(x_{n+1} = x_n – \frac{f(x_n)}{ f'(x_n)}\)
求解n的平方根,其实是求方程\(x^2 -n = 0\)的解
利用上面的公式可以得到:\(x_{i+1} = x_i – \frac{x_i^2 – n}{2 x_i} = (x_i + \frac{n}{x_i} ) /2\)
编程的时候核心的代码是:x = (x + n/x)/2
应用于最优化的牛顿法是以迭代的方式来求解一个函数的最优解,常用的优化方法还有梯度下降法。 取泰勒展开式的二次项,即用\(\phi(x)\)来代替\(f(x)\):
\[\phi(x) = f(x_0) + f'(x_0)(x-x_0) + \frac{1}{2} f”(x_0)(x-x_0)^2 \]
最优点的选择是\(\phi'(x)=0\)的点,对上式求导
\[\phi'(x) =f'(x_0) + f”(x_0)(x-x_0) \]
令\(\phi'(x) = 0\),则\(x = x_0 – \frac{f'(x_0)}{f”(x_0)}\) 所以,最优化的牛顿迭代公式是
\[x_{n+1} = x_n – \frac{f'(x_n)}{f”(x_n)} \]
在高维下
\[\phi(x) = f(x_0) + \nabla f(x_0)^T (x-x_0) + \frac{1}{2} (x-x_0)^T \nabla^2 f(x_0)(x-x_0) \]
求\(\nabla \phi(x)\),并令它等于0,则公式变为了
\[\nabla f(x_0) + \nabla^2 f(x_0)(x-x_0) =0 \]
即
\[x = x_0 – {\nabla ^2 f(x_0) }^{-1} \nabla f(x_0) \]
所以,迭代公式变为
\[x_{n+1} = x_{n} – {\nabla ^2 f(x_n) }^{-1} \nabla f(x_n) \]
其中: \(x_{n+1} ,x_n\)都是N*1维的矢量。 \(\nabla^2 f(x_n)\)是Hessien矩阵,\({\nabla ^2 f(x_n) }^{-1}\)是Hessien矩阵的逆矩阵,它们都是是N*N维的。 \(\nabla f(x_n)\)是 \(f(x)\)的导数,是N*1维的。
和梯度下降法相比,在使用牛顿迭代法进行优化的时候,需要求Hessien矩阵的逆矩阵,这个开销是很大的。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/168015.html原文链接:https://javaforall.cn