最小二乗最適化
図 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( )k ⋅dG N = –F x( )k
d
d = dC+λ(dGN–dC)
λ 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* G⋅ i(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サブ問題を得ることができます。