optimality conditionとは? わかりやすく解説

Weblio 辞書 > 学問 > OR事典 > optimality conditionの意味・解説 

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

読み方さいてきせいじょうけん
【英】: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 conditionKKT条件)である.

 点 \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,\mu)ラグランジュ乗数条件 \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 qualificationCQ),あるいは正則条件と呼ぶ.キューン・タッカーの制約想定はじめとして数多く制約想定提案されているが,なかでも1次独立制約想定(LICQ)とマンガサリアン・フロモヴィッツ条件(MF 条件)が重要である.


LICQ: \nabla g_j(\bar{x})\  (j\in I(\bar{x})),
\ \nabla h_k(\bar{x})\ (k=1,\dots,\ell)1次独立である.
MF条件:(i) \nabla h_k(\bar{x})\  (k=1,\dots,\ell)1次独立である.(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 のとき(従って \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条件満たすとする.さらに3つの条件 (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条件満たすとする.このとき,1次独立制約想定の下で,(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.


「optimality condition」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「optimality condition」の関連用語

optimality conditionのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



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

   
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2025 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS