最適化パッケージで用いる算法
•
|
このページでは、最適化パッケージで用いられる算法の概要について述べます。 最適化パッケージの問題環境は下で述べる基準によって選ばれます。いくつかの問題環境は method オプションによって指定することができます。
infolevel[Optimization] を 1 以上に設定すると算法の名前を表示することができます。
|
•
|
以下の説明では、bounded は境界を持つことを仮定し、constrained は線形または非線形を持つことを仮定します。最適化コマンドは制約条件と境界条件を別にして扱います。より効率的に計算するためには、境界を制約条件としてではなく境界条件として指定します。 の値はどの場合でも同じ算法を使いますが、制約条件および境界条件つき非線形計画問題は別々の算法を使って解きます。
|
|
線形計画問題と2次計画問題
|
|
•
|
線形計画問題は LPSolve を、2 次計画問題は QPSolve を使うことで計算できます。これらのコマンドでは method オプションを使うことはできません。
|
•
|
ネットワーク問題は有効制約法によって解きます。
|
•
|
は LPSolve を使ってによって計算を行います。ネットワーク問題は有効制約法を用いて解きます。整数計画問題にするには assume, binaryvariables または integervariables オプションを使って指定します。
|
|
|
非線形計画問題
|
|
•
|
非線形計画問題は NLPSolve コマンドを使って解きます。このコマンドは method オプションを使うことができます。最適化問題は算法で必要とされる状態が指定されていなければ、エラーを返します。
|
•
|
NLPSolve コマンドで使う算法を以下で述べます。述べる算法のリストは制約の強い順に上から並んでいます。
|
|
2 次補間法 -- この算法は制約条件なし境界条件つき 1 変数問題で使われます。この算法を指定するためには、method=quadratic オプションを使います。この算法は目的関数は連続 1 階微分できることを仮定しますが、微分したものを入力する必要はありません。初期点を initialpoint オプションで指定しても無視されます。
|
|
分岐限定法 (大域探索) -- この算法は制約条件なし境界条件つき 1 変数問題で使われます。 この算法を指定するためには、method=branchandbound オプションを使います。この算法は他の最適化パッケージと異なり、探索を行います。 はじめ、Lipschitz であることを仮定し、を使います。
この解は探索をさらに精錬しています。
|
|
修正 Newton 法 -- 修正 Newton 法は非制約条件または有限境界条件のもとで使われます。この算法を指定するには、method=modifiednewton オプションを使います。この算法は目的関数の勾配を使います。代数式およびオペレータの形で与えたときは自動で計算してくれますが、行列の形で与えたときは勾配も入力する必要があります。
|
|
非線形シンプレックス法 -- 非線形シンプレックス法すなわち Nelder-Mead 法は、境界条件なしまたは一般の制約条件のもとで使われます。この算法を指定するためには、method=nonlinearsimplex オプションを指定します。この算法は微分を必要とせず遅くなる傾向がありますが、精度の不確かな目的関数に関して安定してます。効率よく計算するために、最適化問題の解の大きさが 1 になるように規格化するべきです。
|
|
共役勾配法 (PCG) -- 共役勾配法は境界条件がない場合や一般の制約条件を持つ問題に使います。この算法は method=pcg オプションで使うことができます。代数式およびオペレータの形の目的関数については自動で計算した勾配を使いますが、行列の形で与えられる目的関数の場合には勾配を入力として与える必要があります。
|
|
逐次 2 次計画法 (SQP) -- この算法は method=sqp を指定することで使うことができます。この算法は Maple で自動で計算、またはオプションで指定して入力した微分を使います。これらが利用できないときは、数値微分を計算します。
|
•
|
method オプションを指定しない場合、算法は次のルールで NLPSolve で使う算法が決定します。問題が 1 変数で境界条件を除き制約条件がない場合、2 次補間法で計算します。制約条件がなく目的関数の微分が計算できる場合は、PCG 法で計算します。それ以外の場合には SQP 法で計算します。
|
|
|
最小二乗問題
|
|
•
|
最小二乗問題は LSSolve を使い解きます。目的関数の残差および制約条件が線形関数であるとき、有効制約法を使って計算します。問題が非線形関数であるときは、method オプションによって算法を指定します。指定した方法が条件を満たさない場合にはエラーを返します。
|
•
|
非線形計画問題を解くため LSSolve を使うときは次の算法が指定できます。
Gauss-Newton 法と修正 Newton 法 -- 一般の制約条件について計算することができます。微分可能性は必要としません。この算法を使う場合は method=modifiednewton オプションを指定します。
逐次 2 次計画法 (SQP) -- この算法は method=sqp を指定することで使うことができます。この算法は Maple で自動で計算、またはオプションで指定して入力した微分を使います。これらが利用できないときは、数値微分を計算します。
|
•
|
method オプションが指定しない場合、算法は次のルールで LSSolve で使う算法が決定します。制約条件や境界条件がない場合には修正 Newton 法を使います。それ以外の場合には SQP 法を使います。
|
|
|
Download Help Document
Was this information helpful?