Gauss-Newton 法

ドキュメント内 optimize_print.book (Page 127-130)

• Levenberg-Marquardt 法

• 非線形最小二乗法の実行

Gauss-Newton 法

Gauss-Newton 法において、探索方向 は、各々の主繰り返し k で得られ、線形

最小二乗問題の解になります。

(3-17)

この方法で引出される方向は、Q(x) の項が無視できるときの Newton 方向と同じ

です。 探索方向 は、各々の繰り返しで関数f(x) が減少することを保証するため

ライン探索方法の一部として使われます。

Gauss-Newton 法を使って可能な効率を考えるため、 図3-3は最小二乗問題として

考えたときの Rosenbrock 関数 (3-1) 式 での最小値までのパスを示しています。 制 約なしの BFGS 法の 140 回の繰り返しを行ったものと比べ、Gauss-Newton 法は、

有限差分勾配を使って、たった 48 回の繰り返しの後に収束します。

G x( ) H x( ) Fi( )x Hi( )x

G x( ) = 2J x( )TF x( )

H x( ) = 2J x( )TJ x( )+2Q x( )

Q x( ) Fi( )xHi( )x

i=1 m

=

F x( ) xk

F x( )

dk

J x( )k dkF x( )k

22

xmin∈ℜn dk

図 3-3: Rosenbrock 関数への Gauss-Newton 法の適用

Gauss-Newton 法は、(3-16) 式の二次の項 Q(x) が意味をもつとき、しばしば問題

が生じます。 この問題を解く方法が、Levenberg-Marquardt 法です。

Levenberg-Marquardt

Levenberg-Marquardt 法 [27],[29]は、つぎの線形方程式の解を探索方向として使い

ます。

(3-18) ここで、スカラ は、 の大きさと方向を共にコントロールします。 がゼロ のとき、方向 は、Gauss-Newton法の方向と一致します。 が無限大方向にな

ると、 はゼロベクトル方向へ向かい、最急降下方向になります。 この方法は、

ある十分大きな に対して、 でなければなりません。そのた

め、 はGauss-Newton法の効果を制限している二次の項が存在するときでさえ、

減少することを保証するようにコントロールされます。

それ故に、 Levenberg-Marquardt 法は、Gauss-Newton の方向と最急降下の方向の間 の探索方向を使います。 つぎの 図3-4, Rosenbrock 関数上の Levenberg-Marquardt 法

-1 -0.5 0 0.5 1 1.5 2 2.5 3

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

o

Start Point

oSolution

o o

o

o

o

o

o o

oo o

J x( )k TJ x( ) λk + kI

( )dk = –J x( )F xk ( )k

λk dk λk

dk λk

dk

λk F x( k+dk)<F x( )k λk

最小二乗最適化

に こ の 事 柄 が 示 さ れ て い ま す。 Rosenbrock 関 数 (3-1)式 に 対 す る 解 は、

Gauss-Newton 法の 48 回に比べ、90 回の繰り返しの後、収束しています。 この場

合、Levenberg-Marquardt 法の効率の悪さは、Gauss-Newton 法では、残差が解の点

でゼロになるときに一般的により効率良くなることに起因しています。 しかし、

このような情報を前もって知ることは、常に可能ではありません。そして、しば しば、このように生じる効率の悪さを、 Levenberg-Marquardt 法の強化されたロバ スト性が補償します。

図 3-4: Rosenbrock 関数上の Levenberg-Marquardt 法

非線形最小二乗法の実行

非線形最小二乗法の一般的な研究は、Dennis [10]を参照してください。

Levenberg-Marquardt 法の詳細は、More [30]を参照してください。 Gauss-Newton

法や Levenberg-Marquardt 法は共に、Optimization Toolbox の中で用意されていま

す。 これらの詳細が以下に記述されています。

• Gauss-Newton 法の実行

• Levenberg-Marquardt 法の実行

-1 -0.5 0 0.5 1 1.5 2 2.5 3

-2 -1.5 -1 -0.5 0 0.5 1 1.5 2

oStart Point

oSolution

o o

oo o

o

o

o o o

o o

o o

ooooo

ドキュメント内 optimize_print.book (Page 127-130)