pythonによる直線探索

関数の最適化を行う手法として一番単純なのが最急降下法である。
1変数の場合の最急降下法を実装してみた。

最急降下法の場合、気にしないといけないのが「1ステップあたりどれだけ進むか」というステップ幅である。上に凸な関数な場合これを決める方法として、
1)その地点での接線方向が正のときは、ステップ幅を倍々に大きくしていく
2)その地点での接線方向が負のときは、ステップ幅を半々に小さくしていく
という方法をとる(参考図書：金谷健一「これなら分かる最適化法」)

で、実装してみた。最適化したい関数は

とする。

#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def f(x):
    return -(x - 2.0)**2

def df(x):
    return -2.0*(x - 2.0)

def search(x):
    h = 0.0001
    eps = 10e-10
    X = 0.0
    Xd = 0.0

    while(np.abs(df(x)) > eps):
        h = np.sign(df(x)) * np.abs(h)
        X = x
        Xd = x + h
        if(f(X) < f(Xd)):
            while(f(X) < f(Xd)):
                h = 2.0 * h
                X = Xd
                Xd = X + h
            x = X
            print x
            h = h / 2.0
        else:
            while(f(X) > f(Xd)):
                h = h / 2.0
                Xd = Xd - h
            x = Xd
            print x
            h = 2.0 * h
    return x

y = search(3.0)
print "\nresult:"
print y

結果はこちら

2.1809
1.9761
2.0017
1.9985
2.0001
1.9999
2.0

result:
2.0

うん、きちんと収束している。
それにしてもpythonだとだいぶ自信をもって結果を返してくるのだな…。
有効桁数とか探索の初期値によるところが大きいんだろうけど。