鴨川η

not δ

Backtracking line search

はじめに

以下の本を2年前に買って手を付けていなかったので読み始めた. 無制約最適化のバックトラック法による直線探索の実装をJuliaでやった.

ステップ幅 をBacktracking line searchで探索する.

コード

function armijo(x, grad)
  f_k = obj(x)
  a = 1.
  rho = 0.5
  c = 0.001
  c_innter_prod_g = c*dot(grad, -grad)
  while obj(x-a*grad) > f_k+a*c_innter_prod_g
    a *= rho
  end
  return a
end

function gradient_descent(x)
  eps = 10.0^-2
  k = 1
  while true
    obj_grad_x = obj_grad(x)
    if norm(obj_grad_x) < eps
      break
    end
    alpha = armijo(x, obj_grad_x)
    x -= alpha*obj_grad_x
    k += 1
  end

  return x
end

function obj(x)
  x1, x2 = x
  return 0.5x1^4 - 2x1^2*x2 + 4x2^2 + 8x1 + 8x2
end

function obj_grad(x)
  x1, x2 = x
  return [2x1^3 - 4*x1*x2 + 8, -2x1^2 + 8x2 + 8]
end

x = [3., 1.]
println(gradient_descent(x))

解がテキストとほぼ一致しているので,可視化してみる.右上の が初期値. テキストと異なるパラメータを使っているらしく,ステップ幅がだいぶ大きくなっているが,収束している.

to_opt_x