Levenberg-Marquardt 法の実行

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

最小二乗最適化

図 3-5: λkの更新

の更新にしたがって、 (3-18) 式の解は、探索方向 を得るために使われま

す。 単位ステップ長は、制約なしの方法に対して議論されたものと同様なライン

探索手法に従って求めた方向 に決定されます。 ライン探索手法は、各主繰り返

しで、 になることが保証され、そのため、方法は降下法になりま

す。

この方法は、広範囲の非線形問題で連続的にテストされ、 Gauss-Newton 法よりも よりロバストであることが示され、制約なしの方法よりも、より効率良く繰り返 しがなされることが示されました。 Levenberg-Marquardt アルゴリズムは、関数 lsqnonlinで使われるデフォルトな方法です。 オプションで

LevenbergMarquardtを'off' に設定することで、 Gauss-Newton 法を選択するこ とができます。

No Yes

fp( )xk >fk( )x*

λk 増加 λk 減少

λk λk fk( )x*fp( )xk α* ---+

= λk λk

1+α*

---=

λk dk

dk f x( k+1)<f x( )k

連立非線形方程式の解法

連立非線形方程式 を解くには、連立非線形方程式に含まれる各方程式が0に なるような解を求めます。つまり、 個の方程式と 個の未知数がある場合に

となるような を求めます。ここで、

連立方程式のゼロまたは根が存在することが前提です。 これらの方程式は、たと えばすべてを満足すべき経済的条件などを表しています。

Gauss-Newton

この問題を解く一つの方法として、3-16ページの"最小二乗最適化"で説明した 非線形最小二乗ソルバを使用する方法があります。 この連立方程式には根が存在 することが前提であるため残差は小さくなり、Gauss-Newton法を使用する方法は 有効です。 この場合は、繰り返しの各回に(3-17) 式の線形最小二乗問題を解いて 探索方法を求めます。 (詳細は、3-17ページの"Gauss-Newton 法"を参照してくだ さい)。

Trust-Region Dogleg

他の方法としては、線形連立方程式を解いて探索方向を求める方法があります。

すなわち、Newton法で次のような探索方向 を求めます。

ここで、 はn行n列のヤコビ行列です。

F x( )

n n

F x( ) = 0 x∈ℜn

F x( )

F1( )x F2( )x

Fn( )x

=

.. .

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

xk+1 = xk+dk J x( )k

連立非線形方程式の解法

Newton法では、いくつかの点が問題になる場合があります。 が特異なため

にNewton ステップ が定義されない可能性があります。 また、正確な Newton

ステップ の計算に時間がかかる可能性もあります。 さらに、Newton 法では、

初期値が解と掛け離れている場合は収束しない可能性があります。

Trust-region 法 ( 4-2ページの"非線形最小化に対するTrust-Region法"で概要を説 明)は、初期値が解と掛け離れている場合のロバスト性を向上させ、また、

が特異な場合にも対応できます。Trust-Region法を使用するには、 よりも の方が良いかどうかを判断するためのメリット関数が必要です。次の選択、

も可能ですが、 の最小値が必ずしも の根にはなりません。

Newtonステップ は式

の根であるため、 の最小値にもなります。ここで、

(3-20)

それゆえ、メリット関数の選択としては の方が よりも優れ、

Trust-Regionのサブ問題は、 を条件として次のようになります。

(3-21) J x( )k

∇F1( )xk T

F2( )xk T

∇Fn( )xk T

=

.. .

J x( )k dk

dk

J x( )k xk xk+1

mind f d( ) 1

2--- F x( k+d)TF x( k+d)

=

f d( ) F x( )

dk

M x( k+d) = F x( )k +J x( )dk m d( )

min

d m d( ) 1

2--- M x( k+d) 22

= 1

2--- F x( )k +J x( )dk

= 1

2--- F x( )k TF x( )k + dTJ x( )k TF x( )k

= + 1

2--- dT(J x( )k TJ x( )k )d m d( ) f d( ) D d⋅ ≤ ∆

min

d

1

2--- F x( )k TF x( )k dTJ x( )k TF x( )k 1

2--- dT(J x( )k TJ x( )k )d

+ +

このサブ問題は、dogleg法を使用して効率的に解くことができます。

Trust-Region法の概要は、 Conn [5]、 Nocedal [33]を参照してください。

非線形方程式の実行

Optimization Toolboxでは、Gauss-Newton法、Trust-Region dogleg法の両方が実行 されます。 これらについて、以下に詳しく説明します。

Gauss-Newton 法の実行

Gauss-Newton 法の実行は、最小二乗最適化の場合と同様です。 これについては、

3-20ページの"Gauss-Newton 法の実行"の項で説明しています。

Trust-Region Dogleg

法の実行

このアルゴリズムの最大の特徴は、Powellのdogleg手順を使用して(3-21) 式を 最小化するステップ を計算する点にあります。詳細はPowell [36]を参照してく ださい。

ステップ は、Cauchyステップ(最急降下方向に沿ったステップ)と に対応

する Gauss-Newton ステップを凸に組み合わせることで構成されます。 Cauchyス

テップは、次のように計算されます。

ここで、 は(3-20) 式を最小化するように選択されます。

Gauss-Newton ステップは、MATLAB \(行列の左割) 演算子を使って、

を解くことで計算されます。

ステップ はつぎの式が成り立つように選択されます。

ここで、 は、 を満たすような区間[0,1]内の最大値です。 これは、 が (ほぼ)特異である場合、 はCauchyの方向と一致します。

doglegアルゴリズムが効率的なのは、(Gauss-Newtonステップ計算のための)繰り

返しの各回で、1つの線形解しか必要としないからです。 また、場合によっては、

ライン探索を伴うGauss-Newton法を使用する方法よりもこのアルゴリズムの方が ロバストです。

d

d f x( )

dC = –αJ x( )k TF x( )k α

J x( )kdG N = –F x( )k

d

d = dC+λ(dGNdC)

λ d ≤ ∆ Jk

d

制約付き最適化

制約付き最適化

制約付き最適化において、一般的な目的は、問題を繰り返す過程をベースとして、

より解き易いようなサブ問題に変換することです。 初期に行われていた大きなク ラスの特徴は、制約付き問題を基本的な制約なし問題に、制約に対するペナルティ 関数を使って変換することです。 このようにして、制約付き問題は、パラメータ 化された制約なし最適化に対する一連の方法を使って解かれ、その収束性範囲の 中で、制約付き問題になります。 これらの方法は、現在比較的効率が悪いと考え られており、 Kuhn-Tucker(KT) 方程式の解に注目した方法に代行されています。

KT 方程式は、制約付き最適化問題に対し最適性に対する必要条件になっていま

す。 問題がいわゆる凸計画問題ならば、 と は凸関数にな

り、そして、KT方程式は、グローバルな解に対して必要十分になります。

一般的な問題 GP ((3-1) 式) に関して、Kuhn-Tucker 方程式は、(3-1)式のオリジ ナルの制約とは別に、つぎのように表わすことができます。

(3-22)

最初の方程式は、解の点で目的関数とアクティブな制約条件との間で勾配がキャ ンセルされることを示しています。 勾配をキャンセルするためには、目的関数と 制約条件の勾配との大きさの違いを平衡させるために、Lagrange乗数

( )を必要とします。 アクティブな制約条件のみが、このキャンセ ル操作に入るので、アクティブでない制約条件は、この操作に含まれません。 そ のため、アクティブでないものに対する制約条件に対応する Lagrange乗数はゼ ロとして設定してください。 このことは、(3-22) 式の最後の2つの方程式によっ て陰的に述べられています。

KT 方程式の解は、多くの非線形計画法アルゴリズムの基礎となっています。 これ

らのアルゴリズムは、Lagrange 乗数を直接計算しようとしています。 制約付き準

Newton 法は、準 Newton 更新手法を使用するKT 方程式に関して 2次の情報を集

めることにより、超線形収束を保証します。 QP サブ問題が、各主繰り返しで解か れるので、これらの方法は、一般に逐次2次計画 ( Sequential Quadratic Programming (SQP)) 法として知られています。 また、Iterative Quadratic Programming, Recursive Quadratic Programming, Constrained Variable Metric methods ともいわれます。

この節では、次の事柄について説明します。

f x( ) Gi( )x ,i = 1, ,… m

∇f x∗( ) λi∗⋅∇Gi( )x∗

i=1 m

+ = 0

λi* Gi(x*) = 0 i = 1, ,… m λi∗≥ 0 i = me+1, ,… m

λi, i = 1,…m

• 3-26ページの"逐次二次計画法 (SQP)"

• 3-26ページの"QP サブ問題"

• 3-28ページの"SQP 法の実行"

• 3-33ページの"シンプレックスアルゴリズム"

逐次二次計画法 (SQP)

逐次二次計画法は、非線形計画法の中で最先端の技法です。 たとえば、

Schittowski [38]は、効率性、精度、解の求まる確率について改良して、多くのテ

スト問題について、他のすべての手法と共にテストしました。

Biggs [1], Han [24]、Powell ([34],[35]) の成果をもとに、制約付き最適化に対する

Newton 法に非常に似た手法が、制約なしの最適化に対して適用されます。 各々の

主繰り返しで、準Newton 更新法を使って ラグランジュ関数のヘッセ行列で近似 がなされます。 そして、この手法はライン探索手法に対して、探索方向を求める た め に 使 わ れ る QP サ ブ 問 題 を 作 成 す る の に 使 わ れ ま す。 SQP の 概 要 は、

Fletcher [15], Gill et al. [21], Powell [37]、Schittowski [25] に記述されています。 ここ では、一般的な方法について記述しています。

GP((3-1) 式) で、 問題の記述を与えると、基本的な考え方は、ラグランジュ関数

の二次近似をもとにした QP サブ問題の定式化です。

(3-23)

ここでGP((3-1) 式)は範囲付きの制約が不等式として表現されることを仮定し

ています。 非線形制限を線形化することで、QPサブ問題を得ることができます。

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