ドキュメンテーション センター

  • 評価版
  • 製品アップデート

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

制約付き非線形最適化アルゴリズム

制約付き最適化の定義

制約付きの最小化は、スカラー関数 f(x) の局所的最小値のベクトル x を見つける問題です。この x には制約があります。

条件は次のとおりです。 c(x) ≤ 0、 ceq(x) = 0、 A·x ≤ b、 Aeq·x = beq、 l ≤ x ≤ u。半無限計画法を使用する制約もあります。「fseminf の問題の定式化とアルゴリズム」を参照してください。

fmincon の信頼領域 Reflective 法アルゴリズム

非線形最小化に対する信頼領域法

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

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

(6-18)

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

f(x) を最小化するための信頼領域を決める上で重要な問題は、近似 q (現在の点 x で決まります) の選択方法と計算方法、信頼領域 N の選択方法と変更方法、信頼領域の部分問題を解く精度です。この節では制約なしの問題に焦点をあてます。この節では、制約なしの問題に的を絞っています。

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

(6-19)

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

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

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

(6-20)

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

(6-21)

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

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

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

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

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

  4. Δ を調節します。

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

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

前処理付き共役勾配法

線形方程式 Hp = –g の大きな対称正定システムを解く一般的な方法は、前処理付き共役勾配法 (PCG) です。この反復法は、形式 H·v の行列ベクトル積を計算する機能を必要とします。ここで v は任意のベクトルです。対称正定行列 M は、H"前提条件子" です。すなわち、M = C2 です。ここで C–1HC–1 は、条件数の良い行列または分類分けされた固有値をもつ行列です。

最小化の過程で、ヘッセ行列 H が対称と仮定します。しかし、H は、強い最小化子の近傍の中でのみ正定であることが保証されます。PCG アルゴリズムは、負または 0 の曲率の勾配をもつ場合に終了します (dTHd ≤ 0)。PCG 出力方向 p は、ニュートン システム Hp = –g への負の曲率方向または近似解のどちからです (tol は近似方法を制御)。いずれにせよ、信頼領域法のアプローチで使用される 2 次元部分空間を定義するために p が使用されます (非線形最小化に対する信頼領域法を参照)。

線形等式制約

線形制約は、制約なしの最小化問題に対して記述された状況を複雑にします。しかし、記述されている基本的な考えは、明白に、効率的な手法を基に行われています。Optimization Toolbox のソルバーの信頼領域法は、厳密に実行可能な反復処理を行います。

一般的な線形等号制約付き最小化問題は、次のように表現されます。

(6-22)

ここで A は m 行 n 列 (m ≤ n) の行列です。いくつかの Optimization Toolbox のソルバーは A を前処理し、AT の LU 分解をベースにした手法 (参考文献 [46]) を使って、厳密な意味で線形従属の部分を除去します。ここで A はランク m とします。

式 6-22 を解くためのメソッドは制約なしアプローチと 2 つの点で異なります。まず初期実行可能点 x0 は、スパースの最小二乗ステップを使って Ax0 = b となるように計算されます。第 2 に、PCG アルゴリズムは近似退化ニュートン ステップ (または A のヌル空間における負の曲率方向) を計算するために、退化前処理付き共役勾配法 (RPCG: Reduced Preconditioned Conjugate Gradients) に置き換えられます ([46] を参照)。キーになる線形代数ステップは、次の型のシステムを解くことです。

(6-23)

ここで、 は A の近似 (A のゼロでない小さな値がランク落ちしない範囲でゼロに置き換えられます) であり、C は H のスパース対称正定近似、すなわち C = H です。詳細は [46] を参照してください。

ボックス制約

ボックス制約問題は、次のように表現されます。

(6-24)

ここで、l は下限を表すベクトル、u は上限を表すベクトルです。l の要素のいくつか (またはすべて) は –∞ にすることができ、u の要素のいくつか (またはすべて) は ∞ にすることができます。この方法は厳密な意味で実行可能点の列を生成します。ロバストな収束挙動を達成しながら、可能領域を維持するために 2 つの手法が使われます。1 つ目の手法ではスケーリングされた変更ニュートン ステップが (2 次元の部分空間 S を定義するために) 制約のないニュートン ステップと置き換わります。2 つ目の手法では反射がステップ サイズを増加させるために使われます。

スケーリングされた変更ニュートン ステップは 式 6-24 式の Kuhn-Tucker の必要条件をチェックして生成されます。

(6-25)

ここで、

ベクトル v(x) は 1 ≤ i ≤ n の範囲で次のように定義されます。

  • gi < 0 および ui < ∞ の場合、vi = xi – ui とします。

  • gi ≥ 0 および li > –∞ の場合、vi = xi – li とします。

  • gi < 0 および ui = ∞ の場合、vi = –1 とします。

  • gi ≥ 0 および li = –∞ の場合、vi = 1 とします。

非線形システム 式 6-25 には微分不可能な点があります。vi = 0 のとき微分不可能になります。厳密に実行可能性を維持することにより、このような点を避けることができます。すなわち、l < x < u の制約を適用します。

式 6-25 に対するスケーリングされた変更ニュートン ステップ sk は、

(6-26)

k 番目の反復で線形システムの解として定義されています。ここで以下のようになります。

(6-27)

(6-28)

ここで Jv は |v| のヤコビ行列の役割をします。対角行列 Jv の個々の対角要素は 0、–1、1 のいずれかになります。l u のすべての要素が有限ならば、Jv = diag(sign(g)) になります。gi = 0 の点で、vi は微分可能にならないかもしれません。そのような点では が定義されます。このような微分不可能性は、vi がどの値を取るかは重要でないため、問題とはなりません。さらに、|vi| はこの点でもまだ不連続となりますが、関数 |vi|·gi は連続です。

2 つ目の手法では反射がステップ サイズを増加させるために使われます。(単一) 反射ステップは、次のように定義されます。範囲制約に交差するステップ p を与え、p に交差する最初の範囲制約を与えます。すなわち、これを i 番目の範囲制約 (i 番目の上限または i 番目の下限) であると仮定します。i 番目の要素を除いて、反射ステップは pR = p になります。ここで pRi = –pi です。

fmincon 有効制約法アルゴリズム

はじめに

制約付き最適化における一般的な目的は、問題をより解き易い部分問題に変換し、部分問題を繰り返しの過程の基準として使用することです。初期に行われていた大きなクラスの特徴は、制約付き問題を基本的な制約なし問題に、制約に対するペナルティ関数を使って変換することです。このようにして、制約付き問題は、パラメーター化された制約なし最適化に対する一連の方法を使って解かれ、その収束性範囲の中で、制約付き問題になります。これらの方法は今のところ比較的効率が悪いと考えられており、Karush-Kuhn-Tucker (KKT) 方程式の解に注目した方法に代行されています。KKT 方程式は制約付き最適化問題に対し、最適性に対する必要条件になっています。問題がいわゆる凸計画問題ならば、f(x) と Gi(x),i = 1,...,m は凸関数になり、KKT 方程式はグローバルな解に対して必要十分になります。

一般的な問題 GP (式 6-1) に関して、Kuhn-Tucker 方程式は

(6-29)

式 6-1 の元の制約とは別に次のように表すことができます。

最初の方程式は、解の点で目的関数とアクティブな制約条件との間で勾配がキャンセルされることを示しています。勾配をキャンセルするためには、目的関数と制約勾配との大きさの違いを平衡させるために、Lagrange 乗数 (λi, i = 1,...,m) を必要とします。アクティブな制約のみがこのキャンセル操作に入るので、アクティブでない制約はこの操作に含まれません。そのためアクティブでない制約の Lagrange 乗数はゼロに設定してください。これは Kuhn-Tucker 式の最後の 2 つの方程式によって陰的に述べられています。

KKT の解は多くの非線形計画法アルゴリズムの基礎となっています。これらのアルゴリズムは、Lagrange 乗数を直接計算しようとしています。制約付き準ニュートン法は、準ニュートン更新手法を使用する KKT 方程式に関して 2 次の情報を集めることにより、超線形収束を保証します。QP 部分問題がそれぞれの主な反復で解かれるので、これらの方法は一般に逐次二次計画法 (SQP: Sequential Quadratic Programming) と呼ばれています (Iterative Quadratic Programming 法、Recursive Quadratic Programming 法、Constrained Variable Metric 法としても知られています)。

'active-set' アルゴリズムは大規模なアルゴリズムではありません。大規模と中規模のアルゴリズム を参照してください。

逐次二次計画法 (SQP)

逐次二次計画法は、非線形計画法の中で最先端の技法です。たとえば、Schittkowski [36] は効率性、精度、解の求まる確率を改良して、多くのテスト問題について他のすべての手法と共にテストしました。

Biggs [1]、Han [22]、Powell ([32][33]) の成果をもとに、制約付き最適化のニュートン法に非常に似た手法が制約なしの最適化に対して適用されます。各々の主反復で、準ニュートン更新法を使ってラグランジュ関数のヘッセ行列で近似がなされます。そして、この手法はライン探索手法に対して、探索方向を求めるために使われる QP 部分問題を作成するのに使われます。SQP の概要は Fletcher [13]、Gill 等 [19]、Powell [35]、Schittkowski [23] に記述されています。ここでは、一般的な方法について記述しています。

GP (式 6-1) で問題の記述を与えると、基本的な考え方はラグランジュ関数の二次近似をもとにした QP 部分問題の定式化です。

(6-30)

ここで 式 6-1 は範囲付きの制約が不等式として表現されることを仮定しています。非線形制限を線形化することで、QP 部分問題を得ることができます。

QP 部分問題

(6-31)

この部分問題は、ある QP アルゴリズムを使って解くことができます (例は、二次計画法での解法 を参照してください)。解は次の新しい反復を作るために使われます。

xk + 1 = xk + αkdk.

ステップ長パラメーター αk はメリット関数内で十分な減少が得られるように適当なライン探索手法により決められます (ヘッセ行列の更新 を参照してください)。行列 Hk はラグランジュ関数 (式 6-30) のヘッセ行列の正定近似になります。BFGS 法が最もポピュラーですが、準ニュートン法のいずれかを使っても Hk は更新できます (「ヘッセ行列の更新」を参照してください)。

非線形の制約付き問題は、SQP 法を使った制約なし問題よりも少ない反復回数で解けることもあります。この理由の一つは、可能領域上に限定されているためで、オプティマイザーが探索方向とステップ長に関して情報に基づく決定を行っていることが一因しています。

Rosenbrock 関数に付加的な非線形不等式制約 g(x) を適用することを考慮します。

(6-32)

制約なしの場合は 140 回の反復であるのに対して、SQP 法を使って解くと 96 回の反復になります。非線形制約 Rosenbrock 関数上の SQP 法 (式 6-6) は x = [–1.9,2.0] からはじめ、x = [0.9072,0.8228] の解の点までの経路を示しています。

図 6-3. 非線形制約 Rosenbrock 関数上の SQP 法 (式 6-6)

SQP 法の実装

SQP 法は、次の小節で簡単に論議されている 3 つの部分から作られています。

ヘッセ行列の更新-  各反復でラグランジュ関数のヘッセ行列の正定準ニュートン近似 H は、λi, i = 1,...,m を Lagrange 乗数の推定とする BFGS 法を使って計算されます。

(6-33)

ここで、

Powell [33] は解の点で正定でない部分があったとしても正定ヘッセ行列を使い続けることを推奨しています。正定ヘッセ行列は H が正定行列で初期化された各更新で が正である場合は保持されます。 が正でない場合、qk になるように各要素ごとに変更されます。この変更の一般的な目的は、qk の要素に歪みを与え、正定更新にできるだけ小さく関与するようにすることです。そのため、変更の初期ステージで qk*sk の最大負要素を半分にする作業を反復します。この手法は が負の許容誤差以上になるまで続けます。この処理後でも がまだ正になっていなければ、定数スカラー w を乗じたベクトル v を加え、qk を変更します。つまり以下のようになります。

(6-34)

ここで、

w は が正になるまでシステマチックに増加します。

関数 fminconfminimaxfgoalattainfseminf は、すべて SQP 法を使います。optionsDisplay'iter' に設定すると、関数値、制約違反の最大量のような種々の情報が与えられます。ヘッセ行列が正定条件を満たしたまま、上で記述した手順の最初の方法を使って変更されるとき、Hessian modified が表示されます。ヘッセ行列が上記 2 番目の方法を使って変更されるとき、Hessian modified twice が表示されます。QP 部分問題が可能領域にない場合、infeasible が表示されます。このような表示は、原因を求めるものではなく、問題が非常に高い非線形性であるとか、通常より収束に長い時間が必要であるということを示すものです。場合によってはメッセージ no update が表示され、 がほぼゼロであることを意味します。これは、問題設定が間違っているか、または非連続関数を最小化しようとしている可能性を示しています。

二次計画法での解法-  SQP 法の主要な各反復で、以下の形式の QP 問題を解きます。ここで Aimn 列の行列 A の第 i 行を示します。

(6-35)

Optimization Toolbox 関数で使われる方法は、有効制約法 (射影法として知られています) ですが、[18][17] に記述されている Gill 等による方法に似ています。この方法は修正されて、線形計画法 (LP)、二次計画法 (QP) のどちらにも使われています。

解を求めるステップは、2 つの部分からなっています。最初の段階は (解が存在する場合) 可能領域点を計算します。2 番目の段階は解に収束する可能領域点の列を生成します。このメソッドでは、有効制約法 が、求解点でアクティブな制約条件 (すなわち制約境界上にある制約条件) の推定値となるように維持されます。事実上、すべての QP アルゴリズムは有効制約法です。構造的には非常に類似しているにもかかわらず、異なる用語で記述されている多くの方法があるので、この点を強調しておきます。

は各反復 k で更新され、探索方向 の基底を作成するために使われます。等式制約は常に有効制約法 内にあります。ここで使われている変数 の記法は SQP 法の主要反復の dk とは別なものとして使われています。探索方向 が計算され、任意の有効制約境界上に存在したまま目的関数が最小化されます。 の部分可能空間は、基底 Zk から作成されます。この基底の列は有効制約法 の推定値に直交します (すなわち、 です)。これにより、Zk の列結合の線形和から形成される探索方向は、有効制約法の境界上にあることが保証されます。

行列 Zk は、行列 を QR 分解した行列の最後の m – l 列から形成されます。ここで l はアクティブな制約の数であり、l < m です。つまり、Zk は次のように与えられます。

(6-36)

ここで、

Zk が見つかると、q(d) を最小にする新しい探索方向 が求められます。ここで、 はアクティブな制約条件のヌル空間です。つまり、 は Zk の列の線形結合で、あるベクトル p に対し となります。

を置き換え、2 次式を p の関数として表すと次のようになります。

(6-37)

p で微分すると、次の結果が得られます。

(6-38)

∇q(p) は、 Zk が定義する部分空間の射影勾配なので、2 次関数の射影勾配になります。 は射影ヘッセ行列と呼ばれます。ヘッセ行列 H は、(SQP のこの方法の場合) 正定であると仮定しているので、Zk が定義する部分空間における関数 q(p) の最小値は ∇q(p) = 0 で生じます。これは次の線形方程式の解の場合に成り立ちます。

(6-39)

ステップは次の式で計算されます。

(6-40)

各反復で目的関数の二次式の性質により、ステップの長さ α の選択には 2 つの方法があります。 に沿った単位長さのステップは、 のヌル空間に制限された関数の最小値に向かう厳密なステップになります。制約に違反せずに、このようなステップをとることができれば、これは QP の解 (式 6-35) になります。そうでない場合、最も近い制約に向かう に沿ったステップが 1 より小さくなり、新しい制約は次の反復で有効制約法に含まれます。任意方向 の制約境界までの距離は次式で与えられます。

(6-41)

これは有効制約法内にない制約に対して定義され、方向 は制約の境界に向かっています。すなわち、 です。

n 個の独立な制約が有効制約法内に含まれ、最小値の位置を含んでいない場合、ラグランジュ乗数 λk は次の線形方程式の特異点にならないように計算されます。

(6-42)

λk のすべての要素が正の場合、xk は QP の最適解です (式 6-35を参照)。しかし λk に負の要素があり、等式制約に対応していない場合、その要素は有効制約法から削除され、新しい反復が行われます。

初期化-  

アルゴリズムは実行可能な初期点を必要とします。SQP 法において現在の点が実行可能な領域に入っていないならば、点は、次の線形計画法を解くことにより求めることができます。

(6-43)

表記 Ai は行列 Ai 番目の行です。式 6-43 式での実行可能点 (存在する場合) は等式制約を満たす値に x を設定して求めることができます。これは、等式制約の組から作成される過決定または、列決定のどちらかの線形方程式を解くことにより得られます。この問題の解が存在する場合、スラック変数 γ はこの点で最大不等式の制約になります。

LP 問題の上記 QP アルゴリズムは、各反復で探索方向を最急降下方向に設定することにより変更できます。ここで、gk は目的関数の勾配 (線形目的関数の係数に等しい) です。

(6-44)

LP 法を使って実行可能な点が求められたならば、メインの QP 部分に移行します。探索方向 は、線形連立方程式を解いて求まる を使って初期化されます。

(6-45)

ここで gk は現在の反復 xk での目的関数の勾配です (すなわち Hxk + c です)。

QP 問題で実行可能解が見つからない場合、メインの SQP ルーチンの探索方向 が、γ を最小化する方向として用いられます。

ライン探索とメリット関数-  QP 部分問題の解はベクトル dk を生成し、次の新しい反復を作成するために使用されます。

(6-46)

ステップ長パラメーター αkメリット関数を十分小さくするように決定されます。メリット関数は Han [22]、Powell [33] により導入され、次の型をしています。

(6-47)

Powell は、ペナルティ パラメーターを設定することを推奨しています。

(6-48)

これは、QP 解において前の反復では active であったが現在 inactive となっている制約からの正の寄与を可能にするものです。これを実装するにあたり、ペナルティ パラメーター ri は最初に次のように設定されています。

(6-49)

ここで はユークリッド ノルムを示します。

これは、解の点において制約が active になる場合に、ペナルティ パラメーターへの小さな勾配をもつ制約からの大きな寄与を補償します。

fmincon SQP アルゴリズム

sqp アルゴリズムは active-set アルゴリズムとよく似ています (説明はfmincon 有効制約法アルゴリズムを参照してください)。基本的な sqp アルゴリズムは、Nocedal と Wright の [31] の第 18 章に説明されています。

sqpactive-set アルゴリズムの最も重要な差異は、以下のとおりです。

範囲に関する厳密な実現可能性

sqp アルゴリズムは、範囲によって制約されている領域内ですべての反復ステップを取ります。さらに、有限差分ステップも範囲に従います。範囲は厳密ではありません。ステップは境界上に正確に置くことができます。この厳密な実現可能性は、目的関数または非線形制約関数が未定義または範囲によって制約される領域外で複雑であるときに便利です。

非倍精度結果に対するロバスト性

反復時に、sqp アルゴリズムは失敗するステップを取るよう試みることができます。こうすることにより、与えた目的関数または非線形制約関数は NaNInf、または複雑な値を返します。この場合、アルゴリズムはいまよりも小さなステップを取るよう試みます。

リファクタリングされた線形代数ルーチン

sqp アルゴリズムは異なるセットの線形代数ルーチンを使用して、二次計画法部分問題 式 6-31 を解きます。これらのルーチンは、active-set のルーチンよりも、メモリ使用量およびスピードの両面においてより効率的です。

再定式化された実現可能性ルーチン

sqp アルゴリズムは、制約が満たされないときの 式 6-31 の解に対して、2 つの新しい方法をもっています。

  • sqp アルゴリズムは目的関数と制約関数を 1 つのメリット関数に結合します。このアルゴリズムは、緩和された制約に従ってメリット関数を最小化しようと試みます。変更されたこの問題により実現可能解が得られる場合があります。ただし、この方法は元の問題よりも多くの変数をもつので、式 6-31における問題のサイズは増加します。サイズが増加されたことにより、部分問題の解を得るためにより多くの時間を必要としています。これらのルーチンは、Spellucci の [60] と Tone の [61] の記事に基づいています。sqp アルゴリズムでは、メリット関数 式 6-47 のペナルティ パラメーターが [41] の提案に従って設定されます。

  • 非線形制約が満たされず、試みたステップにより制約違反が増大するという状況を考えてみます。sqp アルゴリズムは、制約に対して二次近似を使用して実現可能性を得るように試みます。この二次近似の手法により実現可能解が得られる場合があります。ただし、この手法は非線形制約関数の評価をさらに多く必要とするので、解を得るためにより多くの時間を必要としています。

fmincon の内点法アルゴリズム

バリア関数

制約付き最小化の内点法アプローチとは、一連の近似最小化問題を解くことです。元の問題は次のようになります。

(6-50)

0 より大きい各 μ に対し、近似問題は次のようになります。

(6-51)

不等式制約 g と同じだけのスラック変数 si があります。ln(si) を範囲指定にするため、si は正に制限されます。μ がゼロに減少すると、fμ は f の最小値に到達します。追加された対数項はバリア関数と呼ばれます。このメソッドは [40][41][51] に記述されています。

近似問題 式 6-51 は等式制約付き問題になります。これは元の非線形制約付き問題 式 6-50 を解くより簡単です。

近似問題を解くために、各反復でアルゴリズムは 2 種類のステップ タイプの中からいずれかを使用します。

  • (x、s) の直接ステップ。このステップは線形近似の近似問題に対して KKT 式の 式 3-2式 3-3 を解きます。これはニュートン ステップとも呼ばれます。

  • CG (共役勾配法) ステップ。

既定の設定ではこのアルゴリズムはまず直接ステップを試します。直接手順が使えない場合、CG 手順を試します。直接手順が使えない場合として、近似問題が現在の反復で局所的に凸でない場合があります。

各反復でこのアルゴリズムは "メリット関数" を以下のように減少させます。

パラメーター は解が可能領域に入るようにするため、反復数とともに増加します。実行したステップがメリット関数を減少させない場合、アルゴリズムは実行したステップを棄却して新しいステップを試します。

反復 xj において、目的関数または非線形制約関数のどちらかが複素数値、NaN、Inf、またはエラーを返すと、アルゴリズムは xj を棄却します。棄却は、メリット関数が十分に減少しなかった場合と同じ効果があります。次に、アルゴリズムは別のより短いステップを試みます。try-catch でエラーを発生する可能性のあるコードをすべてラップします。

function val = userFcn(x)
try
    val = ... % code that can error
catch
    val = NaN;
end

目的関数と制約は初期点で適切な値 (double) を生成しなければなりません。

直接ステップ

以下の変数は直接ステップの定義に使用されます。

  • H は fμ のラグランジュ行列のヘッセ行列を示します。

    (6-52)
  • Jg は制約関数 g のヤコビ行列を示します。

  • Jh は制約関数 h のヤコビ行列を示します。

  • S = diag(s).

  • λ は制約 g に関連するラグランジュ乗数ベクトルを示します。

  • Λ = diag(λ).

  • y は h に関連するラグランジュ乗数ベクトルを示します。

  • e は g と同じサイズの 1 のベクトルを示します。

式 6-53 は直接ステップ (Δx、Δs) を定義します。

(6-53)

この方程式は線形化されたラグランジュ行列を使用して 式 3-2式 3-3 を直接解こうとします。

(Δx、Δs) に対してこの式を解くために、このアルゴリズムは行列の LDL 因数分解を行います。(MATLAB® ldl 関数リファレンス ページの 「「例 3 — D の構造体」」 を参照してください)。これは最も計算に時間がかかるステップです。この因数分解の 1 つの結果は、予測されたヘッセ行列が正定であるかどうかの判定基準になります。正定でない場合、このアルゴリズムは次の節に記述されている共役勾配ステップを使用します。

共役勾配ステップ

近似問題 式 6-51 を解く共役勾配アプローチは他の共役勾配計算と同様です。この場合、このアルゴリズムはx と s を調整し、スラック s を正に保持します。このアプローチは線形化された制約の下で信頼領域法の近似問題の二次近似を最小化します。

特に R は信頼領域の半径を示すようにし、他の変数を 直接ステップ で定義されているようにします。このアルゴリズムは λ を正の状態にしたまま最小二乗近似で以下の KKT 式を近似して解き、ラグランジュ乗数を得ます。

そしてステップ (Δx、Δs) をとり、以下を近似して解きます。

(6-54)

これは、次の線形制約に従います。

(6-55)

式 6-55 を解くために、アルゴリズムは R の半径の範囲内で線形制約のノルムを最小化しようとします。そして制約を使って 式 6-54 を解きます。この制約は半径 R の信頼領域内で s を厳密に正の状態にし、式 6-55 を解いた残差を適合させます。アルゴリズムと微分の詳細は [40][41][51] を参照してください。共役勾配の他の説明は 前処理付き共役勾配法 を参照してください。

内点法のアルゴリズムのオプション

ここでは、内点法アルゴリズムのいくつかのオプションの効果と意味を説明します。

  • AlwaysHonorConstraints'bounds' に設定すると、各反復は設定した範囲制約を満たします。'none' に設定すると、アルゴリズムは中間の反復中に範囲違反します。

  • Hessian — 以下に設定された場合

    • 'user-supplied': ユーザーが与えた関数にラグランジュ行列のヘッセ行列を渡します。この関数ハンドルはオプション HessFcn に与えられなければなりません。

    • 'bfgs': fmincon が密な準ニュートン近似によってヘッセ行列を計算します。

    • 'lbfgs': fmincon が制限されたメモリの大規模の準ニュートン近似によってヘッセ行列を計算します。

    • 'fin-diff-grads': fmincon が勾配の有限差分によってヘッセ行列とベクトルの積を計算します。他のオプションが適切に設定される必要があります。

    ヘッセ行列とベクトルの積を計算するために別の関数を与えることもできます。これらのオプションの詳細は ヘッセ行列 を参照してください。

  • InitBarrierParam — μ の開始値です。既定の設定では 0.1 です。

  • ScaleProblem'obj-and-constr' に設定した場合、アルゴリズムは目的関数と制約をスケーリングしたもので動作します。これは開始値を使って注意深くスケーリングします。スケーリングを無効にするには ScaleProblem'none' にします。

  • SubproblemAlgorithm — 直接ニュートン ステップを使うかどうかを判定します。既定の設定 'ldl-factorization' はこのタイプのステップを使用します。'cg' を設定すると共役勾配ステップのみを使用します。

オプションの全リストは Interior-Point アルゴリズム を参照してください。

fminbnd アルゴリズム

fminbnd は MATLAB をインストールすると使用できるソルバーです。このソルバーは範囲内の 1 次元で局所的最小値を求めるソルバーです。これは微分係数をベースにしません。その代わり、黄金分割法と放物線内挿法を使用します。

fseminf の問題の定式化とアルゴリズム

fseminf の問題の定式化

fseminffmincon とは異なるタイプの制約を使って最適化問題を解きます。fmincon の式は以下になります。

c(x) ≤ 0、 ceq(x) = 0、 A·x ≤ b、 Aeq·x = beq、 l ≤ x ≤ u などが条件になります。

fseminf は上記の他に以下の半無限制約を追加します。1 次元または 2 次元の範囲空間または四角形 Ij 内の wj と、連続関数 K(x, w) のベクトルに対して制約は以下になります。

すべての wj ∈ Ij に対して、Kj(x, wj) ≤ 0。

fseminf 問題の「次元」は制約集合 I の最大次元を意味します。すべての Ij が区間ならば 1 であり、少なくとも 1 つの Ij が四角形ならば 2 になります。K のベクトル サイズはこの概念の次元を示しません。

半無限計画法と呼ばれる理由は変数 (x と wj) の数は有限ですが、制約数が無限であるためです。これは x の制約が連続区間または四角形 Ij の集合上にあるためです。これは点数が無限にあるため、制約が無限にあります。無限個の点 wj に対して Kj(x, wj) ≤ 0 です。

制約が無限にある問題を解くのは不可能だと思うかもしれません。fseminf は問題を 2 つの部分からなる同様な問題に再定式することによってこのような問題を扱います。2 つの部分とは最大化と最小化です。半無限制約は以下のように再定式します。

(6-56)

ここで |K| はベクトル K の要素数です。すなわち、半無限制約関数の数です。x を固定するために、これは範囲区間または四角形上の一般最大化になります。

fseminf はさらに、ソルバーが使用する x ごとに、区分的な 2 次または 3 次近似 κj(x, wj) を関数 Kj(x, wj) にすることで、問題を簡略化します。fseminf は、式 6-56 にあるように、Kj(x, wj) の代わりに、内挿関数 κj(x, wj) の最大のみを考慮します。これは元の問題 (半無限制約関数の最小化) を有限数の制約付き問題に変形します。

サンプリング点-  半無限制約関数はサンプリング点 (二次近似または三次近似に使用する点) を与える必要があります。これを行うには以下を行わなければなりません。

  • サンプリング点 w 間の初期空間 s

  • s からサンプリング点 w を生成する方法

初期空間 s は |K| 行 2 列の行列です。s の j 行目は制約関数 Kj の隣接したサンプリング点間隔を示します。Kj が 1 次元の wj に依存する場合、s(j,2) = 0 に設定します。fseminf は後続の反復で行列 s を更新します。

fseminf は行列 s を使用して、サンプリング点 w を生成します。これは 近似 κj(x, wj) を作成するために使用されます。s から w を生成する手順は、同じ間隔または四角形 Ij を最適化は維持する必要があります。

サンプリング点の作成例-  2 つの半無限制約 K1 と K2 をもつ問題を考えてみましょう。K1 は 1 次元の w1 をもち、K2 は 2 次元の w2 をもちます。以下のコードは w1 = 2 から 12 までのサンプリング集合を生成します。

% Initial sampling interval
if isnan(s(1,1))
    s(1,1) = .2;
    s(1,2) = 0;
end

% Sampling set
w1 = 2:s(1,1):12;

fseminf は制約関数をはじめて呼び出すときに sNaN として指定します。これを確認して、初期サンプリング間隔を設定することができます。

以下のコードは、各要素を 1 から 100 までにして正方形内の w2 からサンプリング集合を生成します。2 番目の要素より 1 番目の要素の方が初期サンプルが多くなります。

% Initial sampling interval
if isnan(s(1,1))
   s(2,1) = 0.2;
   s(2,2) = 0.5;
end
 
% Sampling set
w2x = 1:s(2,1):100;
w2y = 1:s(2,2):100;
[wx,wy] = meshgrid(w2x,w2y);

前のコードの一部は以下のように簡略化できます。

% Initial sampling interval
if isnan(s(1,1))
    s = [0.2 0;0.2 0.5];
end

% Sampling set
w1 = 2:s(1,1):12;
w2x = 1:s(2,1):100;
w2y = 1:s(2,2):100;
[wx,wy] = meshgrid(w2x,w2y);

fseminf のアルゴリズム

fseminf は基本的に半無限計画法の問題を fmincon が扱う問題に変形します。fseminf は半無限計画法の問題を解くために以下のステップをとります。

  1. x の現在値での fseminf は、内挿 κj(x, wj,i) が局所的最最大値となる条件において、すべての wj,i を識別します(最大値は固定された x に対する w の変動を参照します)。

  2. fseminf は以下の fmincon 問題の解において 1 反復ステップをとります。

    c(x) ≤ 0, ceq(x) = 0, A·x ≤ b, Aeq·x = beq, and l ≤ x ≤ u。ここで、c(x) は、すべての wj ∈ Ij に対して取られた κj(x, wj) のすべての最大値で拡張され、これは κj(x, wj,i) の j および i に対する最大値と等価です。

  3. fseminf は、新しい点 x が停止判定に見合うか (反復を停止するか) を確認します。停止判定に合わない場合は手順 4 に進みます。

  4. fseminf は半無限制約の離散化を更新しなければならないかを確認し、近似的にサンプリング点を更新します。これにより、更新された近似 κj(x, wj) が提供されます。次に手順 1 を続行します。

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