最急降下法とニュートン法

最急降下法とニュートン法をRで実装して比較してみた。
細かい理屈はめんどいから省略。


ある関数の最小値や最大値を機械的に求める方法として最急降下法とニュートン法があります。（他にもあります。）
ニュートン法の方が収束が速いそうなのでRで実装して試してみました。
（注意）ニュートン法は2階微分可能な関数でないといけない。


最小値を求める関数: y(x)= 4x^3 - 4x
yが最小値0になる x = 1,-1

以下Rでの実装

#勾配法のプログラム(1変数、最急降下法、ニュートン法)
#関数の最小化を行う
#元の関数 
example.f <- function(x){
  return ( x^4-2*x^2+1 )
}

#勾配を求める関数(微分した関数)
example.df <- function(x){
  return ( 4*x^3-4*x )
}

#２階微分
example.ddf <- function(x){
  return ( 12*x^2-4 )
}

#最急降下法
# xfirst:初期値 rho:学習率指定, its:最大繰り返し回数
kouka.hou <- function(xfirst,rho,its){
  ylist <- c() # 関数の値を入れるリスト
  xlist <- c() # xの値を入れるリスト
  x <- xfirst  # 初期値を与える
  xlist <- c(xlist,x)
  ylist <- c(ylist,example.f(x))
  cnt <- 1     # f(x)を計算した回数
  for(i in 1:its){
    delta.x <- rho*example.df(x)
    x <- x - delta.x
    xlist <- c(xlist,x)
    ylist <- c(ylist,example.f(x))
    cnt <- cnt+1
    if( abs(delta.x) <= 1e-8 ){ #収束条件
      break
    }
  }
  return ( matrix(c(xlist,ylist),cnt,2) ) 
}
#ニュートン法
# xfirst:初期値, its:最大繰り返し回数
newton.hou <- function(xfirst,its){
  ylist <- c() # 関数の値を入れるリスト
  xlist <- c() # xの値を入れるリスト
  x <- xfirst  #初期値を与える
  xlist <- c(xlist,x)
  ylist <- c(ylist,example.f(x))
  cnt <- 1     # f(x)を計算した回数
  for(i in 1:its){
    delta.x <- example.df(x)/example.ddf(x)
    x <- x - delta.x
    xlist <- c(xlist,x)
    ylist <- c(ylist,example.f(x))
    cnt <- cnt+1
    if( abs(delta.x) <= 1e-8 ){ #収束条件
      break
    }
  }
  return ( matrix(c(xlist,ylist),cnt,2) )
}

実行結果

> ( result <- kouka.hou(-2,rho,100) )
[,1] [,2]
[1,] -2.0000000 9.000000e+00
[2,] 0.4000000 7.056000e-01
[3,] 0.5344000 5.103911e-01
[4,] 0.6871137 2.786518e-01
[5,] 0.8321977 9.452366e-02
[6,] 0.9345404 1.603625e-02
[7,] 0.9818783 1.289886e-03
[8,] 0.9959840 6.425520e-05
[9,] 0.9991775 2.704027e-06
[10,] 0.9998347 1.093028e-07
[11,] 0.9999669 4.381370e-09
[12,] 0.9999934 1.753290e-10
[13,] 0.9999987 7.013723e-12
[14,] 0.9999997 2.805534e-13
[15,] 0.9999999 1.132427e-14
[16,] 1.0000000 4.440892e-16
[17,] 1.0000000 0.000000e+00
> ( result2<- newton.hou(-2,100) )
[,1] [,2]
[1,] -2.000000 9.000000e+00
[2,] -1.454545 1.244792e+00
[3,] -1.151047 1.055657e-01
[4,] -1.025326 2.630999e-03
[5,] -1.000908 3.304139e-06
[6,] -1.000001 6.104228e-12
[7,] -1.000000 0.000000e+00
[8,] -1.000000 0.000000e+00
>

最急降下法では17回計算
ニュートン法では8回計算
確かにニュートン法の方が少ない回数で最小値を求めることができていますね。
多変数の場合はヘシアン行列の逆行列を求めることになるから、
ニュートン法の方が遅くなることもあるかも？