ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

最小二乗 (モデル近似) アルゴリズム

最小二乗の定義

一般的に最小二乗は二乗和の関数を極小にするベクトル x を見つける問題です。場合によってはいくつかの制約をもちます。

minxF(x)22=minxiFi2(x)

A·x ≤ b、 Aeq·x = beq、 lb ≤ x ≤ ub。

いくつかの Optimization Toolbox™ のソルバーは、さまざまなタイプの F(x) と制約に利用できます。

ソルバーF(x)制約
\C·x – dなし
lsqnonnegC·x – dx ≥ 0
lsqlinC·x – d範囲、線形
lsqnonlin一般 F(x)範囲
lsqcurvefitF(x, xdata) – ydata範囲

\ で使用されるアルゴリズムに加えて、Optimization Toolbox のソルバーには 4 つの最小二乗アルゴリズムがあります。

  • 信頼領域 Reflective 法

  • レーベンバーグ・マルカート法

  • lsqlin 有効制約法

  • lsqnonnegに使用されるアルゴリズム

信頼領域 Reflective 法アルゴリズム、lsqnonneg アルゴリズム、レーベンバーグ・マルカート アルゴリズムは大規模です。大規模と中規模のアルゴリズム を参照してください。中規模 lsqlin アルゴリズムは大規模ではありません。非線形最小二乗法の一般的な調査については Dennis [8] を参照してください。レーベンバーグ・マルカート法の詳細については [28] を参照してください。

信頼領域 Reflective 法の最小二乗

信頼領域 Reflective 法の最小二乗アルゴリズム

Optimization Toolbox のソルバーで使用される多くのメソッドは、信頼領域法を基にしています。信頼領域法はシンプルなものですが最適化では重要な概念です。

最適化の信頼領域法のアプローチを理解するために制約なし最小化問題を考え、f(x) を最小化します。ここで関数はベクトル引数を取り、スカラーを出力します。n 空間の点 x を想定し、より小さい関数値へ移動して最小化を行う場合を考えてみましょう。基本的な概念は、シンプルな関数 q で f を近似することです。この関数は、点 x の近傍 N で関数 f の挙動をよく表すものです。この近傍が信頼領域です。テスト ステップ s が N における最小化 (または近似最小化) によって計算されます。信頼領域の部分問題を次に示します。

mins{q(s), sN}.(6-99)

f(x + s) < f(x) の場合、現在の点が x + s へ更新されます。そうでない場合は現在の点は変更されず、内点集合 N は縮小され、テスト ステップの計算が繰り返されます。

f(x) を最小化するための信頼領域を決める上で重要な問題は、近似 q (現在の点 x で定義) の選択および計算方法、信頼領域 N の選択および変更方法、信頼領域の部分問題を解く精度です。この節では制約なしの問題に焦点をあてます。変数上に制約があるために複雑度が増す問題については、後節で取り扱います。

標準的な信頼領域法 ([48]) では二次近似 q は、x における F のテイラー近似のはじめの 2 項によって決められます。近傍 N は球形または楕円体です。数学的に、信頼領域の部分問題は、次のように表現できます。

min{12sTHs+sTg  such that  DsΔ},(6-100)

ここで g は現在の点 x における f の勾配です。H はヘッセ行列 (2 次導関数の対称行列) です。D は対角スケーリング行列であり、Δ は正のスカラーです。∥.∥ は 2 ノルムです。式 6-100 を解くために適したアルゴリズムがあります ([48] を参照してください)。このようなアルゴリズムは、完全な次元の固有システムと以下の永年方程式に適用されるニュートン過程の計算を一般的に含みます。

1Δ1s=0.

このようなアルゴリズムにより 式 6-100 の正確な解が与えられます。しかし、H の因数分解に比例して時間が必要になります。このため、信頼領域の問題では異なったアプローチが必要となります。式 6-100 に基づく近似とヒューリスティックな方法は文献 ([42][50]) で提案されています。Optimization Toolbox のソルバーがサポートする近似アプローチとして、信頼領域法の部分問題を 2 次元の部分空間 S ([39][42]) に制限します。部分空間 S が計算されると、(部分空間では問題は 2 次元になるため) 完全な次元の固有値 / 固有ベクトルの情報が必要な場合でも 式 6-100 を解く作業は簡単になります。ここでの主な仕事は、部分空間を決定することになります。

2 次元の部分空間 S は、以下に示す前処理付き共役勾配過程を用いて決められます。ソルバーは s1 と s2 で決まる線形空間として S を定義します。ここで、s1 は勾配 g の方向にあります。s2 は近似ニュートン方向、すなわち以下の解

Hs2=g,(6-101)

または負の曲率の方向です。

s2THs2<0.(6-102)

このように S を選択する背景の考え方は、最急降下方向または負の曲率方向にグローバルな収束を進めることと、ニュートン ステップが存在する場合は、これを介して迅速にローカルな収束を達成することです。

信頼領域法の概念を使用した制約なしの最小化の概要は以下になります。

  1. 2 次元の信頼領域の部分問題の定式化

  2. テスト ステップ s を決めるため、式 6-100 を解きます。

  3. f(x + s) < f(x) の場合、x = x + s とします。

  4. Δ を調節します。

これら 4 つのステップは、収束するまで繰り返されます。信頼領域の大きさ Δ は標準的な規則に基づいて調整されます。使用するステップが適用されない場合、すなわち f(x + s) ≥ f(x) の場合、内点集合は小さくなります。詳細は [46][49] を参照してください。

Optimization Toolbox のソルバーは特定の関数 f の重要かつ特別なケースをいくつか扱います。非線形最小二乗法、二次関数、線形最小二乗法を考えてみましょう。しかし、根底に存在するアルゴリズムは、一般的な場合と同じです。これらの特別な場合は後続の節で説明します。

大規模な非線形最小二乗

f(x) の重要で特別なケースは、非線形最小二乗問題です。

minxifi2(x)=minxF(x)22,(6-103)

ここで F(x) は fi(x) に等しい F(x) の要素 i を使ったベクトル値関数です。この問題を解くために使われる基本的な方法は 非線形最小化に対する信頼領域法 に記述されている一般的な場合と同じです。しかし、非線形最小二乗問題の構造は、効率性を強調したものです。特に、近似的なガウス・ニュートンの方向、すなわち以下の解 s は

minJs+F22,(6-104)

2 次元部分空間 S を定義するのに使います (ここで、J は F(x) のヤコビ行列です)。要素関数 fi(x) の 2 次導関数は使われません。

各反復で前処理付き共役勾配法は次の正規方程式を近似的に解くために使われます。

JTJs=JTF,

ここで、正規方程式は、明示的な形をしていません。

大規模な線形最小二乗

この場合、解く関数 f(x) は以下になります。

f(x)=Cx+d22,

場合によっては線形制約に従います。アルゴリズムは、ある範囲内で局所的な解に収束する厳密に実行可能な反復を行います。各反復は大規模線形システム (n次元: n は x の長さ) の近似解を含みます。反復行列は行列 C の構造をもっています。特に前処理付き共役勾配法は、正規方程式 を、近似的に解くために使われます。

CTCx=CTd,

ここで、正規方程式は、明示的な形をしていません。

部分空間の信頼領域法が探索方向を決定するのに使われます。しかし、ステップを非線形最小化の場合と同じく反射ステップに制限する代わりに、区分的な Reflective ライン探索が二次型の場合と同じく、各反復で使われます。ライン探索の詳細は [45] を参照してください。一般に、線形システムは、解の点で 1 次の最適性条件をもつニュートン アプローチを表しています。すなわち、非常に強い局所的な収束率をもつことになります。

Jacobian Multiply Function-  lsqlin は、行列 C を陽的に使用せずに線形制約付き最小二乗問題を解くことができますが、代わりにユーザーが与えたヤコビ行列乗算関数 jmfun

W = jmfun(Jinfo,Y,flag)

を使用します。この関数は行列 Y に対して以下の乗算を計算しなければなりません。

  • flag == 0 の場合、W = C'*(C*Y) です。

  • flag > 0 の場合、W = C*Y です。

  • flag < 0 の場合、W = C'*Y です。

これは C が大規模な場合は有用ですが、C を陽的に作成せずに jmfun を記述できるような構造が必要になります。例は、「線形最小二乗付きヤコビ行列乗算関数」を参照してください。

レーベンバーグ・マルカート法

最小二乗問題の関数 f(x) は二乗和が最小化されます。

minxf(x)=F(x)22=iFi2(x).(6-105)

この種の問題は、モデル関数をデータに近似する、すなわち非線形パラメーター推定のような広範囲な問題で生じます。このような問題はベクトル x とスカラー  t に対して、出力 y(x,t) をコントロールして連続モデルの経路 φ(t) に従わせる場合などにも使用されます。この問題は、次のように表現されます。

minxnt1t2(y(x,t)φ(t))2dt,(6-106)

ここで y(x,t) と φ(t) はスカラー関数です。

積分が適切な積分公式を使用して離散化されるとき、上記は最小二乗問題として定式化されます。

minxnf(x)=i=1m(y¯(x,ti)φ¯(ti))2,(6-107)

ここで、y¯φ¯ は積分スキームの重みを含みます。この問題ではベクトル F(x) が以下であることに注意してください。

F(x)=[y¯(x,t1)φ¯(t1)y¯(x,t2)φ¯(t2)...y¯(x,tm)φ¯(tm)].

この種の問題では、現実的に到達可能なターゲットの曲線になるように実行するため、残差 ∥F(x)∥ は最適解で小さくなります。制約なしの最適化の基礎 で説明するように制約なしの最小化のための一般的な手法を用いて LS の関数は最小化できますが、問題の特性によっては解法のステップを繰り返す効率がよくなります。LS の勾配行列とヘッセ行列は特別な構造をもちます。

F(x) の m 行 n 列のヤコビ行列を J(x) とし、f(x) の勾配ベクトルを G(x) とし、f(x) のヘッセ行列を H(x) とし、各 Fi(x) のヘッセ行列を Hi(x) とすると、以下のようになります。

G(x)=2J(x)TF(x)H(x)=2J(x)TJ(x)+2Q(x),(6-108)

ここで、

Q(x)=i=1mFi(x)Hi(x).

行列 Q(x) は xk が解に到達して残差 ∥F(x)∥ がゼロになるとき、Q(x) もゼロになるという特性があります。そのため ∥F(x)∥ が解の点で小さくなるとき、最適化手段のベースとしてガウス・ニュートンの方向を使うことが効率的な方法になります。

ガウス・ニュートン法において、探索方向 dk は各反復 k で得られ、線形最小二乗問題の解になります。

minxnJ(xk)F(xk)22.(6-109)

この方法で導かれる方向は Q(x) の項が無視できるときのニュートン方向と同じです。探索方向 dk は、各反復で関数 f(x) が減少することを保証するためにライン探索方向の一部として使われます。

ガウス・ニュートン法は 2 次の項 Q(x) が影響を及ぼすとき、しばしば問題が生じます。この問題を解く方法が、レーベンバーグ・マルカート法です。

レーベンバーグ・マルカート法 [25][27] は、次の線形方程式の解を探索方向として使います。

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(6-110)

またはオプションとして以下の方程式を使います。

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(6-111)

ここでスカラー λk は dk の大きさと方向を共にコントロールします。式 6-110 を選択するにはオプション ScaleProblem'none' に設定します。式 6-111 を選択するには ScaleProblem'Jacobian' に設定します。

λk がゼロのとき、方向 dk はガウス・ニュートン法の方向と一致します。λk が無限大方向になると、dk はゼロ ベクトル方向へ向かい、最急降下方向になります。これは、一部の十分に大きい λk に対して、項 F(xk + dk) <  F(xk) が成り立つことを意味します。そのため λk はガウス・ニュートン法の効果を制限する二次の項が存在するときでさえ、減少を保証するようにコントロールされます。

そのため、レーベンバーグ・マルカート法はガウス・ニュートンの方向と最急降下の方向の間の探索方向を使います。これは Figure 6-4, Rosenbrock 関数上のレーベンバーグ・マルカート法 に示されています。Rosenbrock 関数の解はガウス・ニュートン法の 48 回に比べ、90 回関数評価した後収束しています。この場合、レーベンバーグ・マルカート法の効率の悪さはガウス・ニュートン法では残差が解の点でゼロになるときに一般的により効率良くなることに起因しています。しかし、このような情報を前もって知ることは常に可能ではありません。そして、しばしばこのように生じる効率の悪さをレーベンバーグ・マルカート法の強化されたロバスト性が補償します。

図 6-4. Rosenbrock 関数上のレーベンバーグ・マルカート法

この図をアニメーションで表示するには、MATLAB® コマンド ラインで「bandem」と入力します。

この情報は役に立ちましたか?