アルゴリズムの選択
fmincon アルゴリズム
fmincon には、次の 5 つのアルゴリズム オプションがあります。
'interior-point'(既定の設定)'trust-region-reflective''sqp''sqp-legacy''active-set'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
内点法アルゴリズムによる精度低下の可能性についてを参照してください。 |
推奨の理由
'interior-point'は大規模なスパース問題と小規模な密問題を処理します。最適化アルゴリズムのスパース性を参照してください。このアルゴリズムは、すべての反復で範囲を満たし、NaNまたはInfの結果から回復できます。このアルゴリズムは、大規模な問題に対して特別な手法を使用できます。詳細については、fminconのoptions、「内点法アルゴリズム」を参照してください。'sqp'はすべての反復で範囲を満たします。このアルゴリズムは、NaNまたはInfの結果から回復できます。このアルゴリズムではスパース データを使用できません。最適化アルゴリズムのスパース性を参照してください。'sqp-legacy'は'sqp'に類似していますが、通常、より低速で、さらに多くのメモリを使用します。'active-set'は大きなステップを取ることができるので、高速に処理可能です。このアルゴリズムは、滑らかでない制約をもつ一部の問題に対して効果的です。このアルゴリズムではスパース データを使用できません。最適化アルゴリズムのスパース性を参照してください。'trust-region-reflective'は、勾配を与えることを必要とし、範囲のみまたは線形等式制約のみ (ただし両方ではない) が可能です。これらの制限内でならば、このアルゴリズムは大規模なスパース問題と小規模な密問題を効果的に扱うことができます。このアルゴリズムではスパース データを使用できます。最適化アルゴリズムのスパース性を参照してください。このアルゴリズムは、ヘッセ乗算関数など、特別な手法を使用してメモリ使用量を節約できます。詳細については、fminconのoptions、「信頼領域 Reflective 法アルゴリズム」を参照してください。
各アルゴリズムの説明については、制約付き非線形最適化アルゴリズムを参照してください。
fsolve アルゴリズム
fsolve は次の 3 つのアルゴリズムをもっています。
'trust-region-dogleg'(既定の設定)'trust-region''levenberg-marquardt'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
|
推奨の理由
'trust-region-dogleg'は、非線形方程式を解くために特別に設計された唯一のアルゴリズムです。その他は、この関数の二乗和を最小にするよう試みます。'trust-region'アルゴリズムは、大規模な問題に対して、ヤコビ乗算関数などの特別な手法を使用できます。すべてのアルゴリズムでスパース データを使用できます。最適化アルゴリズムのスパース性を参照してください。
各アルゴリズムの説明については、方程式を解くためのアルゴリズムを参照してください。
fminunc アルゴリズム
fminunc には次の 2 つのアルゴリズムがあります。
'quasi-newton'(既定の設定)'trust-region'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 |
各アルゴリズムの説明については、制約なし非線形最適化アルゴリズムを参照してください。
最小二乗アルゴリズム
lsqlin
lsqlin は次の 3 つのアルゴリズムをもっています。
'interior-point'(既定の設定)'trust-region-reflective''active-set'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 内点法アルゴリズムによる精度低下の可能性についてを参照してください。 |
各アルゴリズムの説明については、最小二乗 (モデル当てはめ) アルゴリズムを参照してください。
lsqcurvefit と lsqnonlin
lsqcurvefit と lsqnonlin は次の 3 つのアルゴリズムをもっています。
'trust-region-reflective'(制約なし問題または範囲制約付き問題の既定値)'levenberg-marquardt''interior-point'(線形制約または非線形制約がある問題の既定値)
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
すべてのアルゴリズムでスパース データを使用できます。最適化アルゴリズムのスパース性を参照してください。最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 |
各アルゴリズムの説明については、最小二乗 (モデル当てはめ) アルゴリズムを参照してください。
線形計画法のアルゴリズム
linprog には 4 つのアルゴリズムがあります。
'dual-simplex-highs'(既定の設定)'interior-point''interior-point-legacy'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
最初に 最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 内点法アルゴリズムによる精度低下の可能性についてを参照してください。 |
推奨の理由
多くの場合、
'dual-simplex-highs'アルゴリズムおよび'interior-point'アルゴリズムは高速であり、使用するメモリが比較的少なくなります。'interior-point-legacy'アルゴリズムは'interior-point'に類似していますが、'interior-point-legacy'では速度やロバスト性が低下したり、メモリ使用量が増加したりすることがあります。すべてのアルゴリズムでスパース データを使用できます。最適化アルゴリズムのスパース性を参照してください。
各アルゴリズムの説明については、線形計画法のアルゴリズムを参照してください。
混合整数線形計画法のアルゴリズム
intlinprog には次の 2 つのアルゴリズムがあります。
'highs'(既定の設定)'legacy'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
最初に 最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 |
推奨の理由
多くの場合、
'highs'アルゴリズムの方が'legacy'アルゴリズムよりも速いか、よりうまく動作します。'highs'アルゴリズムの方が調整オプションが大幅に少なくなっています。そのため、問題を解くときの選択項目が少なくて済みます。'legacy'アルゴリズムは将来のリリースで削除される予定です。
各アルゴリズムの説明については、混合整数線形計画法 (MILP) アルゴリズムを参照してください。
二次計画法のアルゴリズム
quadprog は次の 3 つのアルゴリズムをもっています。
'interior-point-convex'(既定の設定)'trust-region-reflective''active-set'
optimoptions を使用して、コマンド ラインで Algorithm オプションを設定します。
| 推奨 |
|---|
最小化が失敗した場合のヘルプは、ソルバーが失敗する場合またはソルバーが成功している可能性がある場合を参照してください。 内点法アルゴリズムによる精度低下の可能性についてを参照してください。 |
各アルゴリズムの説明については、二次計画法のアルゴリズムを参照してください。
最適化アルゴリズムのスパース性
最適化アルゴリズムの中にはスパース データを受け入れるものがあり、完全な行列を保存したり、演算する必要がありません。このようなアルゴリズムでは、可能な限り計算にスパースな線形代数が使用されます。さらにアルゴリズムはスパース性を維持し (スパース コレスキー分解など)、行列を生成することはありません (共役勾配法など)。このようなアルゴリズムは、大規模な線形制約行列 A または Aeq がある場合や、多数の問題変数がある場合に適しています。
一方、完全な行列を内部的に作成し、密な線形代数を利用するアルゴリズムもあります。問題が十分に大きい場合、完全な行列はメモリを大量に消費し、密な線形代数を計算するのに時間がかかります。変数が多くなく、線形制約行列が大規模でない問題の場合は、このようなアルゴリズムの方がスパース性を利用するアルゴリズムよりも高速になることがあります。
次の表に、スパース データを使用できるソルバーとアルゴリズム、使用できないソルバーとアルゴリズムを示します。
| スパース データを使用できる | スパース データを使用できない |
|---|---|
|
|
| |
| |
| |
| |
| |
|
内点法アルゴリズムによる精度低下の可能性について
fmincon、quadprog、lsqlin および linprog の内点法アルゴリズムには、メモリの消費量が少ないことや、大規模な問題をすばやく解決できるなど、多くの利点があります。ただし、その解は他のアルゴリズムの解と比較して精度がやや落ちる可能性があります。潜在的な精度の低下の原因は、内部計算されるバリア関数によって、反復が不等式制約の境界から遠ざけられるためです。
実際に多くの場合、この精度の低下は非常に小さなものです。
精度の低下を抑えるには、以下を試してください。
StepTolerance、OptimalityTolerance、また場合によってはConstraintToleranceの許容誤差を小さくしてソルバーを再実行します (ただし、妥当な許容誤差は維持してください)。許容誤差と停止条件を参照してください。内点法の求解から始め、別のアルゴリズムを実行します。一部のアルゴリズムでは大量のメモリや長時間を要することがあり、また、すべての
linprogアルゴリズムと一部のquadprogアルゴリズムは初期点を受け入れないため、この方法は失敗することがあります。
たとえば、下限が 0 という制約で関数 x を最小化してみます。fmincon の既定の interior-point アルゴリズムを使用します。
options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off'); x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x = 2.0000e-08
fmincon sqp アルゴリズムを使用すると次のようになります。
options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)x2 = 0
同様に、linprog interior-point-legacy アルゴリズムを使用して同じ問題を解きます。
opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy'); x = linprog(1,[],[],[],[],0,[],1,opts)
x = 2.0833e-13
linprog dual-simplex アルゴリズムを使用すると次のようになります。
opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)x2 =
0これらの場合、内点法アルゴリズムで精度は低下しますが、正しい解にきわめて近くなっています。
