《最適性条件》

【さいてきせいじょうけん (optimality condition)】

　非線形計画問題とは，有限個の不等式，等式制約条件の下で，目的関数を最小(最大)化する問題であり，次のように表される．

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \min. & f(x) \\ \mbox{s. t.} & g(x) \le 0, \\ & h(x) = 0. \end{array} }

$(1)\,$

ここで $x=(x_{1},\dots ,x_{n})^{\top }$ ($^{\top }$ は転置記号), 関数 $f(x)\,$, $g(x)=(g_{1}(x),\dots ,g_{m}(x))^{\top }$，$h(x)=(h_{1}(x),\dots ,h_{\ell }(x))^{\top }$ は微分可能で，導関数は連続と仮定する．制約条件を満たす点 ${\bar {x}}\,$ を実行可能解(以下，可能解という)と呼ぶ．任意の可能解 $x\,$ に対して $f({\bar {x}})\leq f(x)$ が成立するとき， ${\bar {x}}\,$ を最適解と呼ぶ．しかしながら，一般には非線形計画問題の最適解を求めることは容易ではなく，局所的に最適な解である局所的最適解を考えることが多い．即ち，可能解 ${\bar {x}}\,$ で，適当な半径 $\delta >0\,$ を選べば，${\bar {x}}\,$ を中心とする半径 $\delta \,$ 内にあるどの可能解 $x\,$ に対しても 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\bar{x})\leq f(x)} が成立するものを局所的最適解と呼ぶ．

　局所的最適解を求める際，局所的最適解が満たすべき条件，局所的最適解であることを保証する条件が基本的な役割を果たすが，それらを総称して最適性条件(optimality condition)と呼ぶ．通常，最適性条件は目的関数，制約関数の勾配ベクトル $\nabla f(x):=(\partial f/\partial x_{1},\dots ,\partial f/\partial x_{n})^{\top }$ や，$(i,j)\,$ 成分が $\partial ^{2}f/\partial x_{i}\partial x_{j}$ で定義されるヘッセ行列 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla^2 f(x)} を用いて記述されるが，特に勾配ベクトルのみで表された最適性条件を1次の最適性条件(first-order optimality condition)，ヘッセ行列も利用して表されたものを2次の最適性条件と呼ぶ．

　1次の最適性条件で，最もよく利用されるのが次の カルーシュ・キューン・タッカー条件(Karush-Kuhn-Tucker condition，KKT条件)である．

　点 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}\,} が局所的最適解ならば，後述する制約想定の下で，適当なベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\lambda,\mu)\in \mathbf{R}^{m+\ell}} が存在して，ラグランジュ関数を $L(x,\lambda ,\mu ):=f(x)+\sum _{j=1}^{m}\lambda _{j}g_{j}(x)+\sum _{k=1}^{\ell }\mu _{k}h_{k}(x)$ と定義するとき，次のKKT条件が成立する．

:構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left\{\begin{array}{l} \nabla_x L(\bar{x},\lambda,\mu)= \nabla f(\bar{x})+\sum_{j=1}^m\lambda_j\nabla g_j(\bar{x})+ \sum_{k=1}^{\ell}\mu_k\nabla h_k(\bar{x})=0, \\ g_j(\bar{x})\leq 0,\ \lambda_j\geq 0,\ \lambda_jg_j(\bar{x})=0 \ (j=1,\dots,m),\ \ h(\bar{x})=0, \end{array}\right.}

ここで，ベクトル $(\lambda ,\mu )$ はラグランジュ乗数，条件 $\lambda _{j}g_{j}({\bar {x}})=0$ は相補性条件と呼ばれる．

　一方, KKT条件は次の等式，不等式系が解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y\in \mathbf{R}^n} を持たないことを，二者択一定理を用いて言い換えた条件でもある．

:構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla f(\bar{x})^{\top}y<0, \nabla h(\bar{x})^{\top}y=0,\ \ \nabla g_j(\bar{x})^{\top}y\leq 0\ (j\in I(\bar{x})). }

$(2)\,$

ただし，$I({\bar {x}}):=\{j:\,g_{j}({\bar {x}})=0\}$ はアクティブな不等式制約, すなわち点 ${\bar {x}}\,$ において等号が成り立つ不等式制約の集合を表わす．条件(2)に現れる集合 $\{y:\,\nabla g_{j}({\bar {x}})^{\top }y\leq 0\ (j\in I({\bar {x}})),\ \nabla h({\bar {x}})^{\top }y=0\}$ は実行可能集合 $\{x:\,g(x)\leq 0,\ h(x)=0\}$ の，点 ${\bar {x}}\,$ における近似集合と考えられるが，実際に良い近似になるのは，何らかの仮定を満たす場合に限られる．この種の仮定を総称して，制約想定 (constraint qualification，CQ)，あるいは正則条件と呼ぶ．キューン・タッカーの制約想定をはじめとして，数多くの制約想定が提案されているが，なかでも１次独立制約想定(LICQ)とマンガサリアン・フロモヴィッツ条件(MF 条件)が重要である．

LICQ: 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla g_j(\bar{x})\ (j\in I(\bar{x})), \ \nabla h_k(\bar{x})\ (k=1,\dots,\ell)} は１次独立である．

MF条件:(i) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla h_k(\bar{x})\ (k=1,\dots,\ell)} は１次独立である．(ii) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla h(\bar{x})^{\top}z=0, \nabla g_j(\bar{x})^{\top}z<0 (j\in I(\bar{x}))} を満たす 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle z\in \mathbf{R}^n} が存在する．

　LICQ は MF 条件より強い仮定であり，LICQ が成立するとき，ラグランジュ乗数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\lambda,\mu)\,} は一意に決まる．他方，制約想定が満たされない場合でも，点 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} が局所的最適解ならば，ゼロでないベクトル 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\lambda_0,\lambda,\mu)\in \mathbf{R}^{1+m+\ell}} が存在して，次のフリッツ・ジョン条件が成立する．

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \left\{\begin{array}{l} \lambda_0\nabla f(\bar{x})+\sum_{j=1}^m\lambda_j\nabla g_j(\bar{x})+ \sum_{k=1}^{\ell}\mu_k\nabla h_k(\bar{x})=0,\ \ \lambda_0\geq 0 \\ g_j(\bar{x})\leq 0,\ \lambda_j\geq 0,\ \lambda_jg_j(\bar{x})=0\ (j=1,\dots,m), \ \ h(\bar{x})=0. \end{array}\right.}

フリッツ・ジョン条件は，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_0\neq 0} のとき(従って $\lambda _{0}=1$ としてよい)，KKT 条件に一致する．これにより，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_0\neq 0} を保証する条件を制約想定と呼ぶことも多い．

　凸計画問題の場合，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x},\lambda,\mu)} がKKT条件を満たせば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} は最適解になる．しかし一般には，KKT条件は最適性を保証するとは限らない．最適性を詳しく調べるには，2次の最適性条件が必要になる．以下において，各関数は2回連続微分可能であると仮定する．即ち，2回までの偏導関数は全て連続とする．2次の最適性十分条件(second-order sufficient optimality condition)としては，次の定理がよく利用される．

　今，$({\bar {x}},\lambda ,\mu )$ がKKT条件を満たすとする．さらに３つの条件 (a) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla g_j(\bar{x})^{\top}y=0\ \mbox{if}\ \lambda_j>0} , (b) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla g_j(\bar{x})^{\top}y\leq 0\ \mbox{if}\ j\in I(\bar{x})\ \mbox{and}\ \lambda_j=0} , (c) 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla h(\bar{x})^{\top}y=0} を満たすゼロベクトルでない任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y\in \mathbf{R}^n} に対し，$y^{\top }\nabla _{x}^{2}L({\bar {x}},\lambda ,\mu )y>0$ が成立するならば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}\,} は孤立局所最適解になる．すなわち，適当な半径 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \delta>0\,} を選べば，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}\,} を中心とする半径 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \delta\,} 内にある任意の可能解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\neq \bar{x}\,} に対して，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\bar{x})<f(x)\,} が成立する．ここで，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \nabla_x^2 L\,} はラグランジュ関数の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\,} に関するヘッセ行列を表わす．

　この十分条件と対をなす2次の最適性必要条件(second-order necessary optimality condition)としては，次の定理が知られている．

　可能解 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{x}} が局所的最適解で，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x},\lambda,\mu)} はKKT条件を満たすとする．このとき，１次独立制約想定の下で，(a)-(c)を満たす任意の $y\in \mathbf {R} ^{n}$ に対し，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle y^{\top} \nabla_x^2 L(\bar{x},\lambda,\mu)y\geq 0} が成立する．

　2次の最適性十分条件は，最適性の判定以外にも，安定性理論，感度分析，アルゴリズムの収束の議論において重要な役割を演じる．安定性理論(stability theory)と感度分析(sensitivity analysis)は，目的関数や制約関数を微小変化させたとき，最適解や最適値関数がどのように変化するかを調べる問題であり，主としてそれらの連続性を論じるのが安定性理論，微分可能性や変化率を取り扱うのが感度分析である．通常，パラメトリックな問題

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \begin{array}{ll} \min. & f(x,u) \\ \mbox{s. t.} & g(x,u) \le 0, \\ & h(x,u) = 0, \end{array} }

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (3) \,}

や，その一般化を舞台に，最適値関数 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \phi (u)=\inf\{f(x,u): g(x,u)\leq 0, h(x,u)=0\}} と最適解集合 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Phi (u)=\{x:\, f(x,u)=\phi(u), g(x,u)\leq 0, h(x,u)=0\}} の挙動を考察する．ただし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u\in \mathbf{R}^q} はパラメータであり，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u=\bar{u}} のとき(3)は非線形計画問題 (1) に一致するものとする．

このとき, もし各関数が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (x, u)\,} に関して2回連続微分可能で, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x}, \lambda, \mu)} が 3つの条件

(i) 2次の最適性十分条件,

(ii) 1次独立制約想定,

(iii) 狭義の相補性,

すなわち, 全ての 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle j \in I(\bar{x})\,} に対し構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \lambda_j > 0\,} , を満たすならば, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{u}\,} に十分近い任意の 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle u\,} に対して, 問題 (3) に対するKKT条件を満たす $(x(u),\lambda (u),\mu (u))\,$ が 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\bar{x},\lambda,\mu)\,} の近くにただひとつ存在する．また，それらは2回連続微分可能で，条件 (i)-(iii) を満たし，構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(u)\,} は (3) の孤立局所最適解になる． さらに，それらの1回，2回の微分は (3) に対するKKT条件を用いて計算できる．この結果，ラグランジュ乗数が経済学の重要な概念であるシャドープライスを表すことがわかる．

---

参考文献

[1] J.F. Bonnans and A. Shapiro, "Optimization problems with perturbations: Guided tour,"　SIAM Review, 49 (1998), 228-264.

[2] A.V. Fiacco, Introduction to Sensitivity and Stability Analysis in Nonlinear Programming, Academic Press, 1983.

[3] A.V. Fiacco and G.P. McCormick, Nonlinear Programming, SIAM, 1990.

[4] 福島雅夫，非線形最適化の基礎，朝倉書店，2001．

[5] 今野浩，山下浩，非線形計画法，日科技連，1978．

[6] 熊田禎宣，木谷忍，計画のための最適化数学，井上書院，1988.