1 次の最適性の尺度

1 次の最適性の尺度とは

1 次の最適性は、点 x が最適解にどの程度近いかを示す尺度です。アルゴリズムによって定義が異なりますが、ほとんどの Optimization Toolbox™ ソルバーでこの尺度が使用されます。1 次の最適性は必要条件ですが、十分条件ではありません。言い換えれば、次のようになります。

• 1 次の最適性の尺度は、最小値がゼロでなければなりません。

• 1 次の最適性の尺度がゼロである点は、最小値とは限りません。

1 次の最適性に関する一般的な情報については、Nocedal および Wright [31] を参照してください。Optimization Toolbox ソルバーの 1 次の最適性の尺度の詳細については、制約なしの最適性、制約付きの最適性の理論、ソルバー型の制約付き最適性を参照してください。

1 次の最適性に関する停止規則

OptimalityTolerance の許容誤差は 1 次の最適性の尺度に関連しています。一般的に、1 次の最適性の尺度が OptimalityTolerance 未満の場合、ソルバーの反復計算が終了します。

一部のソルバーやアルゴリズムでは、"相対的な" 1 次の最適性が停止条件として使用されます。1 次の最適性の尺度が μ x OptimalityTolerance 未満の場合、ソルバーの反復計算が終了します。ここでは、μ は次のいずれかです。

• x0 での目的関数の勾配の無限大ノルム (最大値)

• linprog の f または b、あるいは quadprog の H などのソルバーへの入力の無限大ノルム (最大値)

相対尺度は問題のスケールを求めようとします。目的関数を非常に大きい数または小さい数で乗算しても、相対停止条件に対する停止状態は変わりませんが、スケール化されていない停止条件に対する状態は変わります。

より詳細な終了メッセージをもつソルバーでは、停止条件の詳細で、どのような場合に相対的な 1 次の最適性を使用するかが示されます。

制約なしの最適性

滑らかな制約のない問題

$$\underset{x}{\min }f(x),$$

に対して、1 次の最適性の尺度は ∇f(x) の無限大ノルム (つまり、最大絶対値) です。

$$\text{first-order optimality measure = }\underset{i}{\max }\left|{\left(\nabla f(x)\right)}_i\right|={\Vert \nabla f(x)\Vert }_{\infty }.$$

この最適性の尺度は最小値に到達するための滑らかな関数としてよく知られた条件を基にしています。その勾配は 0 でなければなりません。制約なしの問題に対して 1 次の最適性の尺度がほぼ 0 の場合、目的関数の勾配はほぼ 0 になり、ほぼ最小値になります。1 次の最適性の尺度が小さくない場合は目的関数は最小値ではありません。

制約付きの最適性の理論

このセクションでは、制約問題に対する 1 次の最適性の尺度の定義の背景にある理論を説明します。Optimization Toolbox の関数で使用される定義は ソルバー型の制約付き最適性 にあります。

滑らかな制約付きの問題では、g と h をそれぞれ不等式と等式制約 (すなわち、範囲、線形、非線形制約) を表すベクトル関数にします。

$$\underset{x}{\min }f(x)\text{ subject to }g(x)\le 0,h(x)=0.$$

この場合、1 次の最適性の意味は、制約なしの問題よりも複雑になります。この定義はカルーシュ・キューン・タッカー (KKT) 条件に基づいています。KKT 条件は、勾配は最小値でゼロにならなければならないという条件に相当し、制約を考慮して変更されています。違いは KKT 条件が制約ありの問題に適用できる点です。

KKT 条件は、次に示す補助的なラグランジュ関数を使用します。

$$L(x,\lambda )=f(x)+{\displaystyle \sum {\lambda }_{g,i}{g}_i(x)}+{\displaystyle \sum {\lambda }_{h,i}{h}_i(x)}.$$

(1)

λ_g と λ_h を連結したベクトル λ はラグランジュ乗数ベクトルです。このベクトルの長さは制約の合計数です。

KKT 条件は以下のとおりです。

$${\nabla }_{x}L(x,\lambda )=0,$$

(2)

$${\lambda }_{g,i}{g}_i(x)=0\forall i,$$

(3)

$$\{\begin{array}{c}g(x)\le 0,\\ h(x)=0,\\ {\lambda }_{g,i}\ge 0.\end{array}$$

(4)

ソルバーは、式 4の 3 つの式を最適性の尺度の計算には使用しません。

式 2に関連する最適性の尺度は

$$\Vert {\nabla }_{x}L(x,\lambda )\Vert =\Vert \nabla f(x)+{\displaystyle \sum {\lambda }_{g,i}\nabla g_i(x)+{\displaystyle \sum {\lambda }_{h,i}\nabla h_{h,i}(x)}}\Vert .$$

(5)

です。式 3に関連する最適性の尺度は

$$\Vert \overrightarrow{{\lambda }_{g}g}(x)\Vert ,$$

(6)

です。ここで、式 6のノルムは、ベクトル $$\overrightarrow{{\lambda }_{g,i}{g}_i}(x)$$ の無限大ノルム (最大値) を意味します。

組み合わされた最適性の尺度は 式 5 と 式 6 で計算する値の最大値です。非線形制約関数を受け入れるソルバーで、制約違反 g(x) > 0 または |h(x)| > 0 が ConstraintTolerance 違反として報告されます。詳細については、許容誤差と停止条件を参照してください。

ソルバー型の制約付き最適性

ほとんどの制約付きのツールボックス ソルバーでは、1 次の最適性の尺度の計算が、範囲、線形関数、非線形関数に分割され、2 つのノルムの最大値になります。これは 式 5 と 式 6 に対応します。

$$\begin{array}{l}\Vert {\nabla }_{x}L(x,\lambda )\Vert =\Vert \nabla f(x)+A^T{\lambda }_{ineqlin}+Ae{q}^T{\lambda }_{eqlin}\\ +{\displaystyle \sum {\lambda }_{ineqnonlin,i}\nabla c_i(x)+{\displaystyle \sum {\lambda }_{eqnonlin,i}\nabla ce{q}_i(x)}}\Vert ,\end{array}$$

(7)

$$\Vert \overrightarrow{\left|l_i-x_i\right|{\lambda }_{lower,i}},\overrightarrow{\left|x_i-u_i\right|{\lambda }_{upper,i}},\overrightarrow{\left|{(Ax-b)}_i\right|{\lambda }_{ineqlin,i}},\overrightarrow{\left|c_i(x)\right|{\lambda }_{ineqnonlin,i}}\Vert ,$$

(8)

ここで、式 7と式 8のベクトルのノルムは、無限大ノルム (最大値) です。ラグランジュ乗数の添字は、ソルバーのラグランジュ乗数構造体に対応します。詳細については、ラグランジュ乗数構造体を参照してください。式 7 の和は、すべての制約の範囲になります。範囲が ±Inf の場合、その項に制約はなく、和に含まれません。

線形等式のみ

線形等式のみの大規模問題の中には、1 次の最適性尺度が "射影" 勾配の無限大ノルムになるものがあります。つまり、1 次の最適性尺度は、Aeq のヌル空間に射影された勾配のサイズになります。

境界付きの最小二乗法ソルバーと信頼領域 Reflective 法ソルバー

最小二乗ソルバーと信頼領域 Reflective 法アルゴリズムで、問題が境界のみである場合、1 次の最適性の尺度は、|v_i*g_i| の i に対する最大値です。ここで、g_i は勾配の i 番目の要素、x は現在の点です。

$$v_i=\{\begin{array}{ll}\left|x_i-b_i\right|\hfill & \text{if the negative gradient points toward bound }{b}_i\hfill \\ 1\hfill & \text{otherwise}\text{.}\hfill \end{array}$$

x_i が境界にある場合は、v_i はゼロです。x_i が境界にない場合は、最小化点で勾配 g_i はゼロになります。このため、1 次の最適性の尺度は、最小化点ではゼロになります。

関連するトピック

• ソルバー出力と反復表示