最適性条件 (非線形計画における)

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

概要

非線形計画問題において, 最適解が満たすべき条件, あるいは最適解になることを保証する条件の総称. 通常, それらは目的関数と制約関数の勾配ベクトルやヘッセ行列を用いて表現される. 最適性条件には, 1次の最適性条件, 2次の最適性必要条件, 2次の最適性十分条件等があるが, 最も基本的なのがカルーシュ・キューン・タッカー条件である.

詳説

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

${\begin{array}{ll}\min .&f(x)\\{\mbox{s. t.}}&g(x)\leq 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\,$ に対しても $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}$ で定義されるヘッセ行列 $\nabla ^{2}f(x)$ を用いて記述されるが，特に勾配ベクトルのみで表された最適性条件を1次の最適性条件(first-order optimality condition)，ヘッセ行列も利用して表されたものを2次の最適性条件と呼ぶ．

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

　点 ${\bar {x}}\,$ が局所的最適解ならば，後述する制約想定の下で，適当なベクトル $(\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条件が成立する．

$\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 _{j}g_{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条件は次の等式，不等式系が解 $y\in \mathbf {R} ^{n}$ を持たないことを，二者択一定理を用いて言い換えた条件でもある．

$\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: $\nabla g_{j}({\bar {x}})\ (j\in I({\bar {x}})),\ \nabla h_{k}({\bar {x}})\ (k=1,\dots ,\ell )$ は１次独立である．

MF条件:(i) $\nabla h_{k}({\bar {x}})\ (k=1,\dots ,\ell )$ は１次独立である．(ii) $\nabla h({\bar {x}})^{\top }z=0,\nabla g_{j}({\bar {x}})^{\top }z<0(j\in I({\bar {x}}))$を満たす $z\in \mathbf {R} ^{n}$ が存在する．

　LICQ は MF 条件より強い仮定であり，LICQ が成立するとき，ラグランジュ乗数 $(\lambda ,\mu )\,$ は一意に決まる．他方，制約想定が満たされない場合でも，点 ${\bar {x}}$ が局所的最適解ならば，ゼロでないベクトル $(\lambda _{0},\lambda ,\mu )\in \mathbf {R} ^{1+m+\ell }$が存在して，次のフリッツ・ジョン条件が成立する．

$\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 _{j}g_{j}({\bar {x}})=0\ (j=1,\dots ,m),\ \ h({\bar {x}})=0.\end{array}}\right.$

フリッツ・ジョン条件は，$\lambda _{0}\neq 0$ のとき(従って $\lambda _{0}=1$ としてよい)，KKT 条件に一致する．これにより，$\lambda _{0}\neq 0$ を保証する条件を制約想定と呼ぶことも多い．

　凸計画問題の場合，$({\bar {x}},\lambda ,\mu )$ がKKT条件を満たせば，${\bar {x}}$ は最適解になる．しかし一般には，KKT条件は最適性を保証するとは限らない．最適性を詳しく調べるには，2次の最適性条件が必要になる．以下において，各関数は2回連続微分可能であると仮定する．即ち，2回までの偏導関数は全て連続とする．2次の最適性十分条件(second-order sufficient optimality condition)としては，次の定理がよく利用される．

　今，$({\bar {x}},\lambda ,\mu )$ がKKT条件を満たすとする．さらに３つの条件 (a) $\nabla g_{j}({\bar {x}})^{\top }y=0\ {\mbox{if}}\ \lambda _{j}>0$, (b) $\nabla g_{j}({\bar {x}})^{\top }y\leq 0\ {\mbox{if}}\ j\in I({\bar {x}})\ {\mbox{and}}\ \lambda _{j}=0$, (c) $\nabla h({\bar {x}})^{\top }y=0$ を満たすゼロベクトルでない任意の $y\in \mathbf {R} ^{n}$ に対し，$y^{\top }\nabla _{x}^{2}L({\bar {x}},\lambda ,\mu )y>0$ が成立するならば，${\bar {x}}\,$ は孤立局所最適解になる．すなわち，適当な半径 $\delta >0\,$ を選べば，${\bar {x}}\,$ を中心とする半径 $\delta \,$ 内にある任意の可能解 $x\neq {\bar {x}}\,$ に対して，$f({\bar {x}})<f(x)\,$ が成立する．ここで，$\nabla _{x}^{2}L\,$ はラグランジュ関数の$x\,$ に関するヘッセ行列を表わす．

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

　可能解 ${\bar {x}}$ が局所的最適解で，$({\bar {x}},\lambda ,\mu )$ はKKT条件を満たすとする．このとき，１次独立制約想定の下で，(a)-(c)を満たす任意の $y\in \mathbf {R} ^{n}$ に対し，$y^{\top }\nabla _{x}^{2}L({\bar {x}},\lambda ,\mu )y\geq 0$ が成立する．

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

${\begin{array}{ll}\min .&f(x,u)\\{\mbox{s. t.}}&g(x,u)\leq 0,\\&h(x,u)=0,\end{array}}$

$(3)\,$

や，その一般化を舞台に，最適値関数 $\phi (u)=\inf\{f(x,u):g(x,u)\leq 0,h(x,u)=0\}$と最適解集合 $\Phi (u)=\{x:\,f(x,u)=\phi (u),g(x,u)\leq 0,h(x,u)=0\}$ の挙動を考察する．ただし，$u\in \mathbf {R} ^{q}$ はパラメータであり，$u={\bar {u}}$ のとき(3)は非線形計画問題 (1) に一致するものとする．

このとき, もし各関数が $(x,u)\,$ に関して2回連続微分可能で, $({\bar {x}},\lambda ,\mu )$ が 3つの条件

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

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

(iii) 狭義の相補性,

すなわち, 全ての $j\in I({\bar {x}})\,$ に対し$\lambda _{j}>0\,$, を満たすならば, ${\bar {u}}\,$ に十分近い任意の $u\,$ に対して, 問題 (3) に対するKKT条件を満たす $(x(u),\lambda (u),\mu (u))\,$ が $({\bar {x}},\lambda ,\mu )\,$ の近くにただひとつ存在する．また，それらは2回連続微分可能で，条件 (i)-(iii) を満たし，$x(u)\,$ は (3) の孤立局所最適解になる． さらに，それらの1回，2回の微分は (3) に対するKKT条件を用いて計算できる．この結果，ラグランジュ乗数が経済学の重要な概念であるシャドープライスを表すことがわかる．

---

参考文献

[1] J.F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer, 2000.

[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] 川崎英文，極値問題，横浜図書，2004.