pythonによる最急降下法

最急降下法は、関数の最適化を行う手法として一番単純である。
多変数の場合、途中で直線探索を行う必要がある。
今回も参考図書は、金谷健一「これなら分かる最適化法」である。

最適化したい関数は

とする。

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

import numpy as np

def func(x):
    A = np.matrix([[1.0,0.0],[0.0,1.0]])
    b = np.matrix([[4.0],[4.0]])
    c = np.matrix([[8.0]])
    return -x.transpose()*A*x + b.transpose()*x - c

def nabrafunc(x):
    b = np.matrix([[4.0],[4.0]])
    return -2.0*x + b

def Func(x,t):
    return x + t*nabrafunc(x)

def dFunc(x,x0):
    return nabrafunc(x).transpose()*nabrafunc(x0)

def search(x0,t):
    T = 0.0
    Td = 0.0
    h = 0.0001
    eps = 1e-10
    x = Func(x0,t)
    xd = Func(x0,t)
    
    while(float(np.abs(dFunc(x,x0))[[0]]) > eps):
        h = np.sign(float(dFunc(x,x0)[[0]]))*np.abs(h)
        T = t
        Td = t + h
        x = Func(x0,T)
        xd = Func(x0,Td)       
        
        if(float(func(x)[[0]]) < float(func(xd)[[0]])):
            while(float(func(x)[[0]]) < float(func(xd)[[0]])):
                h = 2.0 * h
                T = Td
                Td = T + h
                x = Func(x0,T)
                xd = Func(x0,Td)
                
            t = T
            h = h/2.0
        else:
            while(float(func(x)[[0]]) > float(func(xd)[[0]])):
                h = h/2.0
                Td = Td - h
                x = Func(x0,T)
                xd = Func(x0,Td)
                
            t = Td
            h = 2.0*h
    
    print "t:"
    print t
    return t

def hillCliming(x):
    t = 1.0
    delta = 10e-5
    dx = t*nabrafunc(x)
    
    while(np.sqrt(float((dx.transpose()*dx)[[0]])) > delta):
        t = search(x,t)
        dx = t*nabrafunc(x)
        x = x + dx
    
    return x


X = np.matrix([[4.0],[4.0]])

Xr = hillCliming(X)
print "\nresult:"
print Xr

結果はこちら。

t:
0.5
t:
0.5

result:
[[ 2.]
 [ 2.]]

scipyのoptimizeとかはどれくらい最適化パッケージを搭載しているんだろうか。
気になるところである。