勾配降下法をやってみた。

最小二乗法が簡単だったので調子に乗って勾配降下法をC言語で実装してみました。
関数の最小値を求めるもっとも簡単なやつです。
これも実装だけならば簡単。いろいろ実験して遊ぶのには最適です。
関数の傾きを求めてちょっとづつ移動していくやつです。

遊んでわかったことは初期値が平らなところから始まるとこれでもかと思うくらいなかなか値が収束しません。ダメじゃん。傾きを計算するのに導関数もいるしね。

ということでいつか非線形関数の最小二乗法のLevenberg-Marquardt法で最小値を求める実験でもやろうと思っているのですが、Levenberg-Marquardt法、とってもめんどくさいし数学的によくわからないので片手間ではブログ書けないのです。どうしよう・・・・。

---------------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define WIDTH 80
#define HEIGHT 25

//
//myplot
//

static char dot[HEIGHT][WIDTH];
static double off_x = 0.0;
static double off_y = 0.0;
static double scale = 1.0;

static void myplot_init(void)
{
int i;
memset(dot, ' ', HEIGHT*WIDTH);
for (i = 0; i < WIDTH; i++)dot[0][i] = '-';
for (i = 0; i < HEIGHT; i++){
dot[i][0] = '|';
dot[i][WIDTH - 1] = 0;
}
}

static void myplot_plot(double x, double y, char c)
{
int ix, iy;
x = (x - off_x)*scale * 2;
y = (y - off_y)*scale;
ix = (int)x;
iy = (int)y;
if (ix<0 || ix>WIDTH - 2)return;
if (iy<0 || iy>HEIGHT - 1)return;
dot[iy][ix] = c;
}

static void myplot_print(void)
{
int i;
for (i = 0; i < HEIGHT - 1; i++)printf("%s\n", dot[HEIGHT - 2 - i]);
}

void myplot_set_scale(double off_x_, double off_y_, double scale_)
{
off_x = off_x_;
off_y = off_y_;
scale = scale_;
}


//
// main
//
double f(double x)
{
return 20-exp(-x*x/20)*15;
}

double df(double x)
{
return 0.1*x*exp(-x*x / 20) * 15;
}

int main()
{

int i;
double x = 5;
double n = 0.1;

myplot_init();
for (i = 0; i < 10; i++){
myplot_plot(i * 10, 0, '+');
myplot_plot(0, i * 10, '+');
}
myplot_set_scale(-20, 0, 1);
for (i = -100; i < 100; i++)myplot_plot(i, f(i), '*');
//for (i = -100; i < 100; i++)myplot_plot(i, 3*df(i)+10, '@');
myplot_plot(x, f(x), 'S');

for (i = 0; i < 1000; i++){
x = x - n*df(x);
//printf("%f\n", x);
myplot_plot(x, f(x), 'A');
}
myplot_plot(x, f(x), 'E');
myplot_print();


return 0;
}


---------------------------------------------