【最適化】1変数ニュートン法　C++コード付き - 数学とか語学とか楽しいよね

はじめに

今回は無制約最小化問題に対する数値解法（反復法）である、1変数ニュートン法のC++コードを公開します。例題として

$\min (x-2)^2$

を考えます。もちろん、最適解は $x^*=2$ です。反復法とは、適当な初期値 $x^{0}$ を定め、

$x^{n+1} = x^{n} + \alpha d$

という漸化式によって値を更新していき、最終的に最適解 $x^*$ へと収束させるような方法のことです。ここで、 $d$ が探索方向、 $\alpha$ がステップのサイズです。つまり、反復法を構成しているのは探索方向とステップのサイズです。ニュートン法の場合、探索方向とステップのサイズは一度に求まります。お得ですね。

参考文献

参考文献は『最適化と変分法』pp.44-49、『最適化とその応用』pp.151-155、それと以下のPDFファイルです。どちらの本も非常に参考になります。いつも読んでいます。
http://www-optima.amp.i.kyoto-u.ac.jp/~nobuo/Ryukoku/2002/course7.pdf

基礎系数学最適化と変分法 (東京大学工学教程)

作者: 寒野善博,土谷隆,東京大学工学教程編纂委員会
出版社/メーカー: 丸善出版
発売日: 2014/10/22
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

工学基礎最適化とその応用 (新・工科系の数学)

作者: 矢部博
出版社/メーカー: 数理工学社
発売日: 2006/04
メディア: 単行本
購入: 1人クリック: 10回
この商品を含むブログ (11件) を見る

ニュートン法とは？

ニュートン法とは、目的関数（最小化しようとする対象）に対する1次の最適性条件

$\nabla f(x) = 0$

に対して、非線型方程式に対するニュートン法を適用したもの、と言えます。詳しく説明しましょう。現在 $x^{n}$ にいて $d$ だけ進んだ時に1次の最適性条件を満たすとしましょう。つまり、

$\nabla f(x+d) = 0$

です。我々が知りたいのは $d$ です。上の式を1次までテイラー展開すると

$\nabla f(x) + \nabla^2 f(x) d= 0$

となります。 $\nabla^2 f(x)$ はヘシアンと呼ばれています。ここから $d$ について解くと

$d = -\frac{\nabla f(x)}{\nabla^2 f(x)}$

となります。これが1変数ニュートン法における探索方向とステップサイズです。一度に求まります。多変数の場合は行列になるので逆行列をかける必要があります。この $d$ を用いて

$x^{n+1} = x^{n} + d$

のように値を更新して収束させればよいのです。詳細は上記の参考文献を見てください。

C++コード

#include <iostream>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

//function//
inline double f(double x)
{
	return (x-2.0)*(x-2.0);
}

//gradient//
inline double fx(double x)
{
	return 2.0*(x-2.0);
}

//hessian//
inline double fxx(double x)
{
	return 2.0;
}

//Newton method//
inline double Newton(double x)
{	
	return -fx(x)/fxx(x);
}

int main()
{
	double err=pow(10.0,-10.0);//tolerance
	double x=10.0;//initial value
	double d;//direction and step size
	
	
	//iteration//
	for(int i=0;i<10000;i++)
	{
		cout<<i<<" "<<abs(fx(x))<<endl;
		
		//convergence check//
		if(abs(fx(x))<err) break;
		
		d=Newton(x);
		
		//update//
		x=x+d;
	}
	
	cout<<endl;
	cout<<x<<endl;
	
    return 0;
}