您的位置:时时app平台注册网站 > 编程知识 > 福特Explorer 语言实现Newton下落法时时app平台注册

福特Explorer 语言实现Newton下落法时时app平台注册

2019-12-06 10:54

凸是一个很好的性质.如果已经证明了某个问题是凸的,那这个问题基本上算是解决了.
最近在解决一个多目标优化的问题.多目标的问题往往是非凸的.好在能够知道这个问题的近似解大概是多少.这样这个多目标优化的问题至少能够在局部运用凸优化的方法来解决了.解决凸优化的方法有很多,比如梯度下降法,内点法.在梯度下降法中,牛顿下降法是一种重要的方法,也容易实现.更好的是牛顿下降法的收敛速度是二次的,比通常的下降法的收敛速度要快很多.

  这个式子是成立的,当且仅当 Δx 无线趋近于0。此时上式等价与:

R语言实现(代码)

newton <- function(func = objfun, x0, tol = 1e-5, n.max = 100,...){
    x <- x0
    g <- grad(func, x, ...)
    h <- hessian(func, x, ...)

    n <- 0
    while( max(abs(g))>tol && n<n.max ){
        x <- x-solve(h,g)
        g <- grad(func, x, ...)
        h <- hessian(func, x, ...)
        n <- n 1
    }
    if(n == n.max){
        cat('newton failed to convergen')
        return(x)
    }
    return(x)
}

时时app平台注册网站 1

例子

testfun <- function(x, a,b){
    y <- a*x[1]^2   b*x[2]^2
    return (y)
}
library(numDeriv)
y <- newton(func = testfun, x0=c(1,1), a = 1,b = 1)

  2、牛顿法用于最优化

从这里可以看出,如果hessian矩阵是奇异的,那么牛顿下降法将会失效.这是后就需要运用其他的算法了.比如拟牛顿法.

  一般认为牛顿法可以利用到曲线本身的信息,比梯度下降法更容易收敛(迭代更少次数),如下图是一个最小化一个目标方程的例子,红色曲线是利用牛顿法迭代求解,绿色曲线是利用梯度下降法求解。

说明

func : 目标函数.
x0: 目标函数的极小化初始值.
tol:控制精度,越接近零越精确,代表梯度已经是0.
n.max:迭代次数.
... : 目标函数的其他参数.

时时app平台注册网站 2

输出

y
[1] 3.596345e-12 3.596345e-12

原文链接

  在上面讨论的是2维情况,高维情况的牛顿迭代公式是:

依赖包

numDeriv
如果需要安装,在R控制台里键入:

install.package(numDeriv)

  并不是所有的方程都有求根公式,或者求根公式很复杂,导致求解困难。利用牛顿法,可以迭代求解。

牛顿算法
$ x(n 1) = x(n) - H(x(n))^{-1} grad f(x(n)) $
(H(x)表示hessian矩阵)

  高维情况依然可以用牛顿迭代求解,但是问题是Hessian矩阵引入的复杂性,使得牛顿迭代求解的难度大大增加,但是已经有了解决这个问题的办法就 是Quasi-Newton methond,不再直接计算hessian矩阵,而是每一步的时候使用梯度向量更新hessian矩阵的近似。Quasi-Newton method的详细情况我还没完全理解,且听下回分解吧。。。

  这次为了求解f'=0的根,把f(x)的泰勒展开,展开到2阶形式:

  求解:

时时app平台注册网站 3

 

 

时时app平台注册网站 4

  在最优化的问题中,线性最优化至少可以使用单纯行法求解,但对于非线性优化问题,牛顿法提供了一种求解的办法。假设任务是优化一个目标函数f,求函 数f的极大极小问题,可以转化为求解函数f的导数f'=0的问题,这样求可以把优化问题看成方程求解问题(f'=0)。剩下的问题就和第一部分提到的牛顿 法求解很相似了。

  

时时app平台注册网站 5

时时app平台注册网站 6

时时app平台注册网站 7

  求解方程f(x)=0,即f(x0) (x-x0)*f'(x0)=0,求解x = x1=x0-f(x0)/f'(x0),因为这是利用泰勒公式的一阶展开,f(x) = f(x0) (x-x0)f'(x0)处并不是完全相等,而是近似相等,这里求得的x1并不能让f(x)=0,只能说f(x1)的值比f(x0)更接近f(x)=0,于是乎,迭代求解的想法就很自然了,可以进而推出x(n 1)=x(n)-f(x(n))/f'(x(n)),通过迭代,这个式子必然在f(x*)=0的时候收敛。整个过程如下图:

  得出迭代公式:

  原理是利用泰勒公式,在x0处展开,且展开到一阶,即f(x) = f(x0) (x-x0)f'(x0)

  其中H是hessian矩阵,定义为:

  1、求解方程。

时时app平台注册网站 8

本文由时时app平台注册网站发布于编程知识,转载请注明出处:福特Explorer 语言实现Newton下落法时时app平台注册

关键词: