最適性条件とは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > 最適性条件の意味・解説

OR事典

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

読み方：さいてきせいじょうけん
【英】：optimality condition

概要

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

詳説

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

$\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\,$ に対しても $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_jg_j(x)+\sum_{k=1}^{\ell}\mu_kh_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_jg_j(\bar{x})=0 \ (j=1,\dots,m),\ \ h(\bar{x})=0, \end{array}\right.$

ここで，ベクトル $(λ,μ)$ はラグランジュ乗数，条件 $\lambda_jg_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_jg_j(\bar{x})=0\ (j=1,\dots,m), \ \ h(\bar{x})=0. \end{array}\right.$

フリッツ・ジョン条件は， $\lambda_0\neq 0$ のとき(従って $λ 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) \le 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.

「OR事典」の他の用語

非線形計画：

拡張ラグランジュ関数最急降下法最適化問題最適性条件準ニュートン法目的関数直線探索

索引トップ用語の索引ランキングカテゴリー

最適性条件に関係した商品

【送料無料】非線形最適化の基礎 / 福島雅夫【単行本】HMV ローソンホットステーション R
【送料無料】最適デザインの概念楽天ブックス
【送料無料】共立講座21世紀の数学（第13巻）楽天ブックス

>> 「最適性条件」を解説文に含む用語の一覧

>> 「最適性条件」を含む用語の索引

最適性条件のページへのリンク

最適性条件のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		井上和子
2		沓名環希
3		井上和子 (女優)
4		井上和子_(女優)
5		イノウエカズコ
6		行列のできる法律相談所
7		同居人カップルの殺人推理旅行
8		メガゾーン２３　PARTⅡ　秘密く・だ・さ・い
9		TPP
10		井上和子 (言語学者)

11		捗る
12		出不精
13		リーガル・ハイ
14		福利厚生
15		奇跡の人
16		アセスメント
17		自由民主党幹事長
18		ダイバーシティ
19		友引
20		言葉

21		石松千恵美
22		未満
23		功罪
24		タカラダニ
25		ハクビシン
26		先負
27		土曜ワイド劇場
28		ご指導ご鞭撻
29		セクシー・サイン　好き好き好き
30		注意喚起


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

最適性条件とは？

OR事典

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

概要

詳説