勾配法プログラム

[mysocialexperience]

以下のプログラムでf(x)=-2x^2+5x+2の最大点を，勾配法で求めようとすると
符号が変化せずに収束しません。
どこが間違っているのでしょうか？
分かる方よろしくお願いいたします。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include"MT.h"

using namespace std;

int main()
{
	double x = 0;/*初期化*/
	double gradient;
	double ipu = 0.001;
	double f = 0;
	int judge = 1;/*+ or -*/
	int new_judge;

	gradient = -4 * x + 5;
	if (gradient > 0)judge = 1;
	else judge = 0;
	gradient = 0;
	
	while (1){
		gradient = -4 * x + 5;
		
		if (gradient > 0)new_judge = 1;
		else new_judge = 0;

		if (new_judge != judge)break;

		x = x + ipu*gradient;
		
		gradient = 0;
	}

	f = -2 * x*x + 5 * x + 2;
	cout << "x.." << x << ", f(x).." << f << endl;

	return 0;
}

[みけCAT]

少し書き換えたプログラムを実行した所、符号は変化しなそうでしたが収束はしました。
符号の変化を待つ、という方針が間違っているかもしれません。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
//#include"MT.h"

using namespace std;

int main()
{
	double x = 0;/*初期化*/
	double gradient;
	double ipu = 0.001;
	double f = 0;
	int judge = 1;/*+ or -*/
	int new_judge;

	gradient = -4 * x + 5;
	if (gradient > 0)judge = 1;
	else judge = 0;
	gradient = 0;
	
	int max=5000;
	int i=0;
	while (i++<max){
		gradient = -4 * x + 5;
		
		if (gradient > 0)new_judge = 1;
		else new_judge = 0;

		if (new_judge != judge)break;

		x = x + ipu*gradient;
		printf("%d %.15f %.15f\n", i, x, gradient);
		
		gradient = 0;
	}

	f = -2 * x*x + 5 * x + 2;
	cout << "x.." << x << ", f(x).." << f << endl;

	return 0;
}

[lbfuvab]

例えば、f(x)=xの零点x=0を考えた時、f'(x) = 1なので傾きの符号では収束性を測る事は出来ないと思います。
普通に適当な定数εを決めて、|f(x)|<εで測ってはどうでしょうか

[みけCAT]

例えば、f(x)=xの零点x=0を考えた時、f'(x) = 1なので傾きの符号では収束性を測る事は出来ないと思います。
普通に適当な定数εを決めて、|f(x)|<εで測ってはどうでしょうか

今回は零点ではなく最大点を求めたいので、|f'(x)|<εですね。

[lbfuvab]

最大点ですか。
それは失礼しましたm(_ _)m

[usao]

> x = x + ipu * gradient;

何でこんな方法なのでしょう？
符号が変化するには，この演算によって，xが「極大点の向こう側」に移動しないとならないわけですが…
極大点に近づくにつれてgradientの値はどんどん小さくなり，極大点付近ではかなり0に近い値になります．
（つまりxの移動量はどんどん小さくなる．すごく収束が遅そう）

xの値をこの式によって　gradientに比例する量　でシフトさせていくとき，
xが極大点を飛び越えるかどうかは ipuの値次第ではないでしょうか．
ループ内で　ipu * gradient の値を都度表示等してみると良いのではないでしょうか．
>ipu = 0.001;
では，xの座標が極大点座標に漸近的に近づいていくような動きになるのではないでしょうか．


＃やりたいことは　x += ipu * sign( gradient )　とかなのでは？
＃というか，上に凸な２次関数だとわかっているなら　f'(x)=0 を解けば良いような…　とかいう話ではないのだろうな．