4 解の十分条件

得られた解が最適解であることを確認するためには、特定の条件が満たされる必要があります。ここでは、様々な種類の最適化問題における解の十分条件について詳しく説明します。

すべての非線形関数は、解の近傍で連続な二階導関数を持つと仮定します。

4.1 無制約最小化

無制約最小化問題は、最も基本的な最適化問題の形式ですが、点$x^*$が$f(x)$の無制約局所最小値であるための十分条件は以下の通りです：

1. $\|\nabla f(x^*)\| = 0$ および

2. $\nabla^2 f(x^*)$が正定値

ここで、$\|\cdot\|$はユークリッドノルムを表します。

4.2 変数に対する境界付き最小化

変数に境界制約がある場合、解の条件は無制約の場合とは異なります。

境界制約付き問題の解において、境界上にない変数は自由変数と呼ばれます。解においてどの変数が境界上にあるかが事前に分かっている場合、問題は自由変数だけの無制約問題として解くことができます。したがって、解の十分条件は無制約の場合と同様ですが、自由変数にのみ適用されます。

実行可能点$x^*$が境界制約付き問題の解であるための十分条件は以下の通りです：

1. $\|\bar{g}(x^*)\| = 0$; および

2. $\bar{G}(x^*)$が正定値; および

3. $\frac{\partial}{\partial x_j} f(x^*) < 0, x_j = u_j$; $\frac{\partial}{\partial x_j} f(x^*) > 0, x_j = l_j$,

ここで、$\bar{g}(x)$は自由変数に関する$f(x)$の勾配であり、$\bar{G}(x)$は自由変数に関する$f(x)$のヘッシアン行列です。追加条件(iii)は、1つ以上の境界から離れることによって$f(x)$を減少させることができないことを保証します。

4.3 線形制約付き最小化

線形制約付き最小化問題は、多くの実用的な最適化問題の基礎となります。

ここでは、一般的な線形不等式制約に対する結果を説明します。これらの結果は、境界制約や範囲制約といった特殊なケースにも直接適用できるため、それらの具体的な取り扱いについては別途言及しません。

線形制約付き問題の最適解$x^*$において、等式として成立する制約をアクティブ制約またはバインディング制約と呼びます。最適解$x^*$において、t個のアクティブ制約が存在すると仮定します。このとき、$\hat{A}$をアクティブ制約に対応する$A$の列で構成された行列、$\hat{b}$を同様に$b$から得られるベクトルとすると、次のように表現できます：

$\hat{A}^T x^* = \hat{b}.$

行列$Z$は、以下を満たす$n \times (n-t)$行列として定義されます：

$\hat{A}^T Z = 0;$ $Z^T Z = I.$

$Z$の列は$\hat{A}$の列に直交するベクトルの集合の直交基底を形成します。 ここで、以下の定義を導入します： - $g_Z(x) = Z^T \nabla f(x)$：$f(x)$の射影勾配ベクトル - $G_Z(x) = Z^T \nabla^2 f(x) Z$：$f(x)$の射影ヘッシアン行列

線形制約付き問題の最適解においては、射影勾配ベクトルがゼロでなければなりません。これは、勾配ベクトル$\nabla f(x^*)$が$\hat{A}$の列の線形結合として表現できることを意味します。すなわち、$\nabla f(x^*) = \sum_{i=1}^t \lambda_i^* \hat{a}_i = \hat{A} \lambda^*$となります。

ここで、スカラー$\lambda_i^*$は$i$番目のアクティブ制約に対応するラグランジュ乗数と定義されます。$i$番目のラグランジュ乗数は、$i$番目のアクティブ制約の法線方向における$f(x)$の勾配を表すと解釈できます。

ラグランジュ乗数ベクトルの便利な定義式（ただし、実際の計算には推奨されません）は次のとおりです：

$\lambda^* = (\hat{A}^T \hat{A})^{-1} \hat{A}^T \nabla f(x^*).$

$x^*$が線形制約付き問題の解であるための十分条件は：

1. $x^*$が実行可能で、$\hat{A}^T x^* = \hat{b}$; および

2. $\|g_Z(x^*)\| = 0$、または同等に、$\nabla f(x^*) = \hat{A} \lambda^*$; および

3. $G_Z(x^*)$が正定値; および

4. $\lambda_i^* > 0$ if $\lambda_i^*$が制約$\hat{a}_i^T x^* \geq \hat{b}_i$に対応する場合; $\lambda_i^* < 0$ if $\lambda_i^*$が制約$\hat{a}_i^T x^* \leq \hat{b}_i$に対応する場合。 等式制約の場合、定義上常にアクティブであるため、$\lambda_i^*$の符号は重要ではありません。

4.4 非線形制約付き最小化

非線形制約付き問題では、多くの概念が線形制約付き問題と同様に定義されます。ここでは、表記を簡略化するために、すべての非線形制約を$c(x) \geq 0$の形で表現すると仮定します。

$x$におけるアクティブ制約の集合は、$x$で等式として成立する制約の集合を指します。これに関連して、$\hat{c}$と$\hat{A}$も定義されます。具体的には、$\hat{c}(x)$はアクティブ制約関数を含むベクトルであり、$\hat{A}(x)$の列はアクティブ制約の勾配ベクトルです。

前述の定義と同様に、$Z$は$\hat{A}(x)$に関して以下の条件を満たす行列として定義されます：

$\hat{A}^T Z = 0;$ $Z^T Z = I$

ただし、ここでは表記の簡便さのため、$x$への依存性は省略しています。

射影勾配ベクトル$g_Z(x)$は、ベクトル$Z^T \nabla f(x)$です。非線形制約付き問題の解$x^*$において、射影勾配はゼロでなければなりません。これはアクティブ制約に対応するラグランジュ乗数の存在を意味します。つまり、$\nabla f(x^*) = \hat{A}(x^*) \lambda^*$です。

ラグランジュ関数は以下のように与えられます：

$L(x, \lambda) = f(x) - \lambda^T \hat{c}(x).$

$g_L(x)$をラグランジュ関数の勾配、$G_L(x)$をそのヘッシアン行列、$\hat{G}_L(x)$をその射影ヘッシアン行列（つまり、$\hat{G}_L = Z^T G_L Z$）と定義します。

$x^*$が非線形制約付き問題の解であるための十分条件は：

1. $x^*$が実行可能で、$\hat{c}(x^*) = 0$; および

2. $\|g_Z(x^*)\| = 0$、または同等に、$\nabla f(x^*) = \hat{A}(x^*) \lambda^*$; および

3. $\hat{G}_L(x^*)$が正定値; および

4. $\lambda_i^* > 0$ if $\lambda_i^*$が$\hat{c}_i \geq 0$の形式の制約に対応する場合。 等式制約の場合、定義上常にアクティブであるため、$\lambda_i^*$の符号は重要ではありません。

条件(ii)は重要な意味を持ちます。$Z^T$を適用すると行列$\hat{A}(x^*)$が消去されるため、$x^*$におけるラグランジュ関数の射影勾配もゼロでなければなりません。