ソルバーが成功している可能性がある場合

最終点が初期点と等しい

1 次の最適性の尺度が 0 に近いため、初期点が局所的最小値または解になるようです。ソルバーが初期点を改善しなかったので、この結果では満足できないかもしれません。

初期点が本当に局所的最小値であることに確信がない場合は、以下を試します。

  1. 異なる点から開始する方法については、「初期点の変更」を参照してください。

  2. 目的関数と制約が正しく定義されていることを確認します (たとえば、いくつかの点で正しい値を返すかどうか)。目的関数と制約関数の確認を参照してください。実行不可能な点で関数がエラーを起こさないことを確認します。反復は制約に違反する可能性ありを参照してください。

  3. OptimalityTolerance、ConstraintTolerance、StepTolerance などの許容誤差を変更する方法については、「適切な許容誤差を使用」を参照してください。

  4. 問題をスケーリングして、各座標にほぼ同じ効果をもたせる方法については、「問題のリスケーリング」を参照してください。

  5. 勾配とヘッセ情報を与える方法については、「解析勾配またはヤコビアンの提供」および「ヘッシアンの提供」を参照してください。

局所的最小値の可能性

ソルバーが局所的最小値に到達した可能性がありますが、1 次の最適性の尺度が OptimalityTolerance 許容誤差より小さくないため、確実ではありません (1 次の最適性の尺度の詳細については、1 次の最適性の尺度を参照。) 報告された解が信頼できるかどうかを確かめるには、以下の提案を検討してください。

1.滑らかでない関数
2.最終点で開始して再実行
3.他のアルゴリズムを試す
4.許容誤差の変更
5.問題のリスケーリング
6.近傍点の確認
7.有限差分オプションの変更
8.解析勾配またはヤコビアンの提供
9.ヘッシアンの提供

1.滑らかでない関数

滑らかでない関数を最小化しようとしたり、滑らかでない制約をもつ場合、「局所的最小値の可能性」程度の終了メッセージしか得られないことがあります。これは、1 次の最適性条件が滑らかでない点に適用されないためです。

解が適正であることを納得するために、「近傍点の確認」を試します。

2.最終点で開始して再実行

最終点で最適化を再開すると、より良い 1 次の最適性の尺度をもつ解になる可能性があります。より良い (より低い) 1 次の最適性の尺度により、答えを信頼してもよい理由が増えます。

たとえば、例 (Optimization Toolbox ソルバーによる記号数学の使用) に含まれる次の最小化問題を考えてみましょう。

options = optimoptions('fminunc','Algorithm','quasi-newton');
funh = @(x)log(1 + (x(1) - 4/3)^2 + 3*(x(2) - (x(1)^3 - x(1)))^2);
[xfinal fval exitflag] = fminunc(funh,[-1;2],options)

Local minimum possible.

fminunc stopped because it cannot decrease the 
objective function along the current search direction.

xfinal =
    1.3333
    1.0370

fval =
  8.5265e-014

exitflag =
     5

5 の終了フラグ値は、1 次の最適性の尺度が関数許容誤差より上であることを示します。最小化を xfinal から開始して再度実行します。

[xfinal2 fval2 exitflag2] = fminunc(funh,xfinal,options)

Local minimum found.

Optimization completed because the size of the gradient is 
less than the default value of the function tolerance.

xfinal2 =
    1.3333
    1.0370

fval2 =
  6.5281e-014

exitflag2 =
     1

局所的最小値は「可能」ではなく「見つかりました」であり、終了フラグは 5 ではなく 1 です。2 つの解は事実上同一です。1 次の最適性の尺度が十分に低かったため、2 番目の実行はより満足のいく終了メッセージをもちます: 3.9674e-006 の代わりに 7.5996e-007。

3.他のアルゴリズムを試す

ソルバーが多くあるため、アルゴリズムを選択できます。さまざまなアルゴリズムにより、異なる停止条件を使用することができます。

たとえば、「最終点で開始して再実行」すると、1 回目の実行から、最終フラグ 5 が返されます。この実行では quasi-newton アルゴリズムを使用します。

信頼領域法アルゴリズムにはユーザー指定の勾配が必要です。betopt.m は目的関数と勾配の計算を含んでいます。

function [f gradf] = betopt(x)

g = 1 + (x(1)-4/3)^2 + 3*(x(2) - (x(1)^3-x(1)))^2;
f = log(g);
gradf(1) = 2*(x(1)-4/3) + 6*(x(2) - (x(1)^3-x(1)))*(1-3*x(1)^2);
gradf(1) = gradf(1)/g;
gradf(2) = 6*(x(2) - (x(1)^3 -x(1)))/g;

trust-region アルゴリズムを使用して最適化を実行すると、結果として異なる終了フラグになります。

options = optimoptions('fminunc','Algorithm','trust-region','SpecifyObjectiveGradient',true);
[xfinal3 fval3 exitflag3] = fminunc(@betopt,[-1;2],options)

Local minimum possible.

fminunc stopped because the final change in function value 
relative to its initial value is less than the default value 
of the function tolerance.

xfinal3 =
    1.3333
    1.0370

fval3 =
  7.6659e-012

exitflag3 =
     3

終了条件は、最良ではありませんが quasi-newton 条件よりは良い条件です。最終点からアルゴリズムを再度実行すると、極めて小さい 1 次の最適性の尺度をもつより良い点が生成されます。

[xfinal4 fval4 eflag4 output4] = fminunc(@betopt,xfinal3,options)

Local minimum found.

Optimization completed because the size of the gradient is 
less than the default value of the function tolerance.

xfinal4 =

    1.3333
    1.0370

fval4 =
     0

eflag4 =
     1

output4 = 
         iterations: 1
          funcCount: 2
       cgiterations: 1
      firstorderopt: 7.5497e-11
          algorithm: 'trust-region'
            message: 'Local minimum found.

Optimization completed because the size o...'
    constrviolation: []

4.許容誤差の変更

許容誤差を厳しくするか緩めると、より満足できる結果をもたらすことがあります。たとえば、「他のアルゴリズム」セクションで OptimalityTolerance のより小さな値を選択すると、以下のようになります。

options = optimoptions('fminunc','Algorithm','trust-region',...
    'OptimalityTolerance',1e-8,'SpecifyObjectiveGradient',true); % default=1e-6
[xfinal3 fval3 eflag3 output3] = fminunc(@betopt,[-1;2],options)

Local minimum found.

Optimization completed because the size of the gradient is 
less than the selected value of the function tolerance.

xfinal3 =
    1.3333
    1.0370

fval3 =
     0

eflag3 =
     1

output3 = 
         iterations: 15
          funcCount: 16
       cgiterations: 12
      firstorderopt: 7.5497e-11
          algorithm: 'trust-region'
            message: 'Local minimum found.

Optimization completed because the size...'
    constrviolation: []

fminunc は、以前より反復を 1 回多くし、より良い解に到達します。

5.問題のリスケーリング

スケーリングとセンタリングを行うことにより、各座標が目的関数と制約関数へほぼ同じ効果を与えるようにします。例については、「問題のセンタリングとスケーリング」を参照してください。

6.近傍点の確認

目的関数と制約が最終点の近くの点に存在している場合は、それらを評価します。最終点が局所的最小値である場合は、近傍実行可能点はより大きい目的関数値をもちます。例については、「近傍点の確認」を参照してください。

Global Optimization Toolbox ライセンスをお持ちの場合は、最終点から patternsearch (Global Optimization Toolbox) ソルバーを実行してみてください。patternsearch は近傍点を検査し、すべてのタイプの制約を受け入れます。

7.有限差分オプションの変更

中心有限差分法は評価操作よりも時間がかかりますが、より正確です。問題が高い曲率をもつ可能性がある場合は、中心差分を使用します。

コマンド ラインで中心差分を選択するには、optimoptions を使用して、'FiniteDifferenceType' を既定の 'forward' ではなく 'central' に設定します。

8.解析勾配またはヤコビアンの提供

勾配またはヤコビアンが提供されない場合、ソルバーは有限差分法によって勾配とヤコビアンを推定します。つまり、これらの導関数を提供することにより、計算時間の節約や精度の向上が期待できます。問題ベースのアプローチは、自動的に勾配を提供できます。Optimization Toolbox の自動微分を参照してください。

制約問題の場合は、勾配を与えることで別の利点があります。ソルバーは、x それ自体は実行可能だが、x の周囲の有限差分は常に実行不可能な点へ導くような点 x に到達することがあります。この場合、ソルバーは失敗するか途中で停止する可能性があります。勾配を与えることで、ソルバーは続行できます。

目的関数と非線形制約関数を定義するファイル内に、勾配またはヤコビアンも与えます。構文についての詳細については、スカラー目的関数の記述、ベクトルと行列の目的関数の記述、非線形制約を参照してください。

勾配またはヤコビアンの有効性を確認で説明されているように、勾配またはヤコビ関数が正しいことを確認するには関数 checkGradients を使用します。

Symbolic Math Toolbox™ のライセンスをお持ちの場合は、プログラミングによって勾配とヘッシアンを計算することができます。例については、Symbolic Math Toolbox を使用した勾配とヘッシアンの計算を参照してください。

勾配とヤコビアンを使用している例は、勾配およびヘッシアンを使った最小化、勾配付き非線形制約、Symbolic Math Toolbox を使用した勾配とヘッシアンの計算、ヤコビアンを使用した場合と使用しない場合の非線形方程式の解法、およびヤコビアンを使用した大規模スパース連立非線形方程式を参照してください。問題ベースのアプローチの自動微分については、問題ベースの最適化における自動微分の効果を参照してください。

9.ヘッシアンの提供

ヘッシアンを与えると、ソルバーはより正確かつより少ない反復で作動します。

以下のソルバーとアルゴリズムはヘッシアンを受け入れます。

Symbolic Math Toolbox のライセンスをお持ちの場合は、プログラミングによって勾配とヘッシアンを計算することができます。例については、Symbolic Math Toolbox を使用した勾配とヘッシアンの計算を参照してください。問題ベースのアプローチでヘッシアンを提供するには、問題ベースのワークフローへの導関数の供給を参照してください。

Symbolic Math Toolbox を使用した勾配とヘッシアンの計算の例は、fmincon が、ヘッシアンなしでは 77 回反復し、ヘッシアンを使用すると 19 回しか反復しないことを示します。

特異行列に関する警告

最適化プロセスで、次の 1 つ以上の警告が発行される場合があります。

  • 警告: 行列は作業精度で特異です。

  • 警告: 行列は特異行列、ほぼ特異行列であるか、不適切にスケーリングされています。結果は不正確になる可能性があります。RCOND = <条件数>。

  • 警告: 行列は、特異行列に近いか、正しくスケーリングされていません。結果は不正確になる可能性があります。RCOND = <条件数>。

これらの警告は通常、ソルバーがステップ方程式 (直接ステップを参照) を解こうとして数値的な問題が生じた場合に発生します。

この状況に対処するには、次の手順を試します。

  1. 結果のチェック

    ソルバーで問題が生じていても、最小化を適切に解けないわけではありません。多くの場合、結果に問題はありません。終了フラグをチェックし、適切な手順を実行して、返された答えが信頼できることを確認します。これらの手順は、このページとトピックソルバーが失敗する場合およびソルバーが成功する場合に記載されています。結果が信頼できることがわかったら、以降のアクションを行う必要はありません。

  2. 部分問題のアルゴリズムの変更

    部分問題のアルゴリズムを変更すると、ソルバーが特異性を回避して解を求める別の経路をたどる場合があります。このオプションは、既定の "interior-point" アルゴリズムを使用する fmincon ソルバーにのみ適用されます。

    options = optimoptions("fmincon",SubproblemAlgorithm="cg")

  3. センタリングとスケーリング

    問題データのセンタリングとスケーリングを行うことで、数値的な問題を解決できる場合があります。範囲 lb や ub などの入力データをおおよそ次数 1 で設定し、必要なスケーリングがすべて内部的に実行されるようにしてみます。

    たとえば、装置が 1e-6 m から 2e-5 m までで動作できる場合、下限を 1e-6、上限を 2e-5 と指定するのではなく、下限を 1 (つまり 1e-6 m)、上限を 20 (つまり 2e-5 m) と指定します。同様に、装置が 1e6+1 から 1e6+4 までの距離で動作する場合、下限を 1、上限を 4 と指定し、変数に内部的に 1e6 を追加します。

  4. データの摂動

    多くの場合、特異行列は、データに摂動を与えると特異性が低下します。摂動を与えることができるデータには、開始点 x0、範囲 lb および ub、その他の制約、目的関数定義などがあります。問題を実質的に変える変更は加えないでください。

    データに摂動を与えるには、小さなランダム量を追加します。たとえば、x がデータの場合、代わりに x + 1e-6*randn(size(x)) を使用してみてください。以下に示す摂動を 1 つ以上指定します。

    % Perturb x0.
x0 = x0 + 1e-6*randn(size(x0));
% Perturb bounds.
lb = lb + 1e-6*randn(size(lb));
ub = ub + 1e-6*randn(size(ub));
% Perturb linear inequality constraints A*x <= b.
b = b + 1e-6*randn(size(b));
% Perturb objective function myfun(x) by changing the evaluation point.
z = 1e-6*randn(size(x0)); % Choose one perturbation.
fun = @(x)myfun(x + z) % Repeated evaluations of fun are not random.

参考

トピック