ドッグレッグ法

出典: フリー百科事典『ウィキペディア(Wikipedia)』

ドッグレッグ法(ドッグレッグほう、: dog leg method)またはパウエルのドッグレッグ法(パウエルのドッグレッグほう、: Powell's dog leg method)は、1970年マイケル・J・D・パウエル英語版によって導入された、非線形最小二乗問題を解くための反復最適化アルゴリズムである[1]レーベンバーグ・マルカート法と同様、ガウス・ニュートン法勾配降下法とを組み合わせるが、信頼領域を明示的に使用する。各反復において、ガウス・ニュートン法により算出されたステップが信頼領域内にある場合は、それを使用して現在の解を更新する。ガウス・ニュートン法により算出されたステップが信頼領域外に出てしまう場合、コーシー点と呼ばれる最急降下方向に沿った目的関数英語版の最小点を探す。コーシー点が信頼領域の外側にある場合は、信頼領域の境界まで切りつめられ、新しい解として採用される。コーシー点が信頼領域内にある場合、新しい解は、信頼領域の境界と、コーシー点とガウス・ニュートン法によるステップを結ぶ線(ドッグレッグステップ)との交点を次の解とする[2]

このアルゴリズムの名前は、ドッグレッグステップの構成がゴルフドッグレッグホールの形状に似ていることに由来する[2]

定式化[編集]

ドッグレッグステップの構成

を所与として、次の形式の最小二乗問題を考える。

パウエルのドッグレッグ法は最適点に収束する点により構築することでこの問題を解く。各反復において、ガウス・ニュートン法ステップは次のように与えられる。

ここで、ヤコビ行列を表わす。一方、最急降下方向は次式のように与えられる。

目的関数を最急降下方向に沿って線形化すると、以下を得る。

コーシー点におけるパラメータtの値を計算するには、最後の表式をtに関して微分したものとゼロを結んだ等式を解けばよく、解は次の式で与えられる。

所与の信頼半径のもと、パウエルのドッグレッグ法では次のように更新ステップを選択する。

  • ガウス・ニュートンステップが信頼領域内にある場合()、
  • と最急降下ステップの両方が信頼領域の外にある場合()、
  • は信頼領域の外側にあるが、は内側にある場合、についてを満たすよう解いたもの(ドッグレッグステップ)[1]

出典[編集]

  1. ^ a b Powell 1970.
  2. ^ a b Yuan 2000.

参照文献[編集]

  • Lourakis, M.L.A.; Argyros, A.A. (2005). “Is Levenberg-Marquardt the most efficient optimization algorithm for implementing bundle adjustment?”. Tenth IEEE International Conference on Computer Vision (ICCV'05) Volume 1. pp. 1526-1531. doi:10.1109/ICCV.2005.128. ISBN 0-7695-2334-X 
  • Yuan, Ya-xiang (2000). “A review of trust region algorithms for optimization”. Iciam. 99 
  • Powell, M.J.D. (1970). “A new algorithm for unconstrained optimization”. In Rosen, J.B.; Mangasarian, O.L.; Ritter, K.. Nonlinear Programming. New York: Academic Press. pp. 31–66 
  • Powell, M.J.D. (1970). “A hybrid method for nonlinear equations”. In Robinowitz, P.. Numerical Methods for Nonlinear Algebraic Equations. London: Gordon and Breach Science. pp. 87–144 

外部リンク[編集]

関連項目[編集]