カルーシュ・クーン・タッカー条件 - Wikipedia

https://ja.wikipedia.org/wiki/カルーシュ・クーン・タッカー条件

https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%BC%E3%82%B7%E3%83%

A5%E3%83%BB%E3%82%AF%E3%83%BC%E3%83%B3%E3%83%BB%E3%82%BF%E3%

83%83%E3%82%AB%E3%83%BC%E6%9D%A1%E4%BB%B6

カルーシュ・クーン・タッカー条件

カルーシュ・クーン・タッカー条件（英: Karush-Kuhn-Tucker condition）あるいはKKT条件とは、非線形計画において一階導関数が満たすべき最適条件を指す。ラグランジュの未定乗数法が等式制約のみを扱うのに対して、KKT条件を用いた解法は不等式制約も扱うことができる。KKT条件に対応する連立方程式は、解析的に閉形式解法が導かれる特殊な場合を除いては直接的には解かない。すでにKKT条件の連立方程式を数値的に解く方法は数多く確立されており、それらを用いて解くのが一般的である。KKT条件は線形計画法における主双対内点法などの解法において、重要な役割を持つ。

ラグランジュ未定乗数法ならびにKuhn-Tucker最適性条件における制約想定 - ...

http://www.cit.nihon-u.ac.jp/kouendata/No.42/7_sujo/7-047.pdf

端点解 - ウィキまとめ

https://wikimatome.org/wiki/端点解

corner（boundary）solution

変数の非負制約および不等式〔群〕制約付きの最適化問題において，最適解がこれらの制約不等式の定義する変数の許容領域である「機会集合」の内点ではなく端点，すなわちコーナーで実現される可能性を除外できない。この端点解の可能性を許容して，古典的ラグランジュの未定乗数法を拡張したのがクーン＝タッカーの1階の条件である。
⇒コーナー解
⇒内点解
⇒クーン＝タッカーの1階条件

対象となる非線形計画問題編集

次のような非線形計画問題を考える。

\text{Minimize} \; f(x)

\text{subject to} \; g_i(x) \leq 0, \; h_j(x) = 0

このとき、 $x$ が変数、 $f$ が目的関数、 $g i (i = 1, 2, ... , m)$ は不等式制約を表す関数、 $h j (j = 1, 2, ... , l)$ は等式制約を表す関数である。不等式制約と等式制約の数はそれぞれ $m$ および $l$ で表す。

この際、KKT条件が局所値の必要条件となるためには、正規条件と呼ばれるいくつかの条件のうちの1つを満たす必要がある。一例として、 $f$ が凸関数で、かつ $g i$ および $h j$ がアフィン関数であるなどの条件がある．

必要条件編集

目的関数 $f : R n \mapsto R$ と制約の関数 $g i : R n \mapsto R, h j : R n \mapsto R$ が $x *$ において連続かつ微分可能であるとする。もし $x *$ が目的関数の極小値を与えるのなら、KKT乗数と呼ばれる $μ i (i = 1, ..., m), λ j (j = 1, ..., l)$ で以下を満たすものが存在する。

定常性: For maximizing f(x): $\nabla f(x^*) = \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_j \nabla h_j(x^*),$; For minimizing f(x): $-\nabla f(x^*) = \sum_{i=1}^m \mu_i \nabla g_i(x^*) + \sum_{j=1}^l \lambda_j \nabla h_j(x^*),$

主問題の実行可能条件: $g_i(x^*) \le 0, \mbox{ for all } i = 1, \ldots, m$; $h_j(x^*) = 0, \mbox{ for all } j = 1, \ldots, l \,\!$

双対問題の実行可能条件: $\mu_i \ge 0, \mbox{ for all } i = 1, \ldots, m$

スラック変数に関する条件: $\mu_i g_i (x^*) = 0, \mbox{for all}\; i = 1,\ldots,m.$

特に $m = 0$ の場合は等式制約のみを持つ問題となるので、KKT条件はラグランジュの未定乗数が満たすべき条件と同値になり、KKT乗数はラグランジュ乗数と呼ばれる。仮に、いくつかの関数が微分不可能である場合、劣微分を用いたKKT条件を同様に定めることができる。

参考文献編集

田村, 明久、村松, 正和『最適化法』共立出版〈工系数学講座 17〉、2002年4月1日。ISBN 4-320-01616-5。

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

ラグランジュの未定乗数法 - Wikipedia

https://ja.wikipedia.org/wiki/ラグランジュの未定乗数法

ラグランジュの未定乗数法（ラグランジュのみていじょうすうほう、英: method of Lagrange multiplier）とは、束縛条件のもとで最適化を行うための数学（解析学）的な方法である。いくつかの変数に対して、いくつかの関数の値を固定するという束縛条件のもとで、別のある1つの関数の極値を求めるという問題を考える。各束縛条件に対して定数（未定乗数、Lagrange multiplier）を用意し、これらを係数とする線形結合を新しい関数（未定乗数も新たな変数とする）として考えることで、束縛問題を普通の極値問題として解くことができる方法である。

定理編集

ラグランジュの未定乗数法は、次のような定理として記述される。

2次元の場合編集

束縛条件g (x , y ) = 0 のもとで、f (x , y )が最大値となる点(a , b )を求める問題，つまり

maximize

f(x,y)

subject to

g(x,y)=0

という問題を考える。ラグランジュ乗数をλとし、

$F(x,y,\lambda )=f(x,y)-\lambda g(x,y)$

とおく。点(a , b )で∂g/∂x も∂g/∂y も0でないならば、αが存在して点(a , b , α)で

${\frac {\partial F}{\partial x}}={\frac {\partial F}{\partial y}}={\frac {\partial F}{\partial \lambda }}=0$

が成り立つ^[1] 。

一般の多次元の場合編集

n 次元空間の点x = (x₁, ... ,x_n ) のある領域R を定義域とする被評価関数z = f (x ) が、同じ領域を定義域とするm 次元ベクトル値関数

${\boldsymbol {G}}({\boldsymbol {x}})={\begin{pmatrix}g_{1}(x_{1},\dots ,x_{n})\\\vdots \\g_{m}(x_{1},\dots ,x_{n})\end{pmatrix}}={\boldsymbol {0}}\qquad (1)$

のもとで、R 内の点x において極値をとるための必要条件は、その点におけるf の勾配ベクトル

$\nabla f=^{t}{\begin{pmatrix}{\frac {\partial f}{\partial x_{1}}},\dots ,{\frac {\partial f}{\partial x_{n}}}\end{pmatrix}}$

が、その点で、m 個のg_i それぞれの勾配ベクトルが張るm 次元線型部分空間に含まれること、すなわち、スカラーの組 λ = (λ₁, ... ,λ_m ) を用いて、

$\nabla f=\sum _{i=1}^{m}\lambda _{i}\nabla g_{i}\qquad (2)$

が成り立つことである。移項して∇を取れば、

$f({\boldsymbol {x}})-\sum _{i=1}^{m}\lambda _{i}g_{i}({\boldsymbol {x}})$

が停留点をとることである。ただし、{∇g₁, ... ,∇g_m } は一次独立、すなわち

$\dim(\nabla g_{1},\dots ,\nabla g_{m})=m$

でなければならない。式(1)のm 本と式(2)のn 本の式を連立させて、x とλの(n +m ) 個の未知数について解けば、f の極値を与える候補点が得られる^[2]。

解釈編集

幾何学的な説明編集

図1: 束縛条件g (x,y ) = cに対して関数f (x,y ) を最大化する場合。

図2: 図1の等高線地図。赤い線は束縛条件

g(x,y)=c

を示す。青い線は

f(x,y)

の等高線。赤い線が青い等高線に接する点が解。

簡単のため2次元の場合を考えよう。g (x,y ) = c（ここでc は与えられた定数である）に対し、関数f (x,y ) を最大化するものとしよう。f の値を高さとしたグラフを考える。d のいろいろな値に対しf (x,y ) = d で与えられるf の軌道が考えられる。束縛条件はg の値をcに固定してg が1つの軌道にあるとすることである。g= c の軌道に沿って歩くと、f とg の軌道は違うから、この軌道は一般に多数のf 軌道を横切ることになる。そこでd の異なる値に対して横切るいろいろなf =d の軌道に注目しよう。軌道を横切るとすると、坂を上ればf の値は増加する（下れば減少する）。

ただし横切ろうとしている軌道f =d が実際は軌道g=c（束縛条件）と交差せず接触だけする場合に限り、f の値は変化しない（束縛条件下でf が最大となる点ではまさにそうである）。ここではf とg との勾配ベクトル（各変数による偏微分を成分とする）の向きが同じになる。

ここで0でないスカラー λ を導入し、f − λg を考える。上の点の条件は、λ のある値に対してf − λg の勾配が0であるということに等しい（λ はfとg の勾配の比）。

物理的な解釈編集

物理学の問題を解くとき、ラグランジュの未定乗数は単なる方便ではなく、ある物理量を表すことが多い。

たとえば、流体力学において、非圧縮性流れのナビエ-ストークス方程式を解く場合、圧力は速度ベクトル場が連続の式という束縛条件を満たすための未定乗数として求められる^[3]。

変則版編集

2次元問題で、束縛条件が1つの場合には、以下のように連立方程式を作っても良い：

${\frac {\partial f}{\partial x}}+\lambda '{\frac {\partial f}{\partial y}}=0$

${\frac {\partial g}{\partial x}}+\lambda '{\frac {\partial g}{\partial y}}=0$

$g(x,y)=0$

ただしこの場合のλ'は、もとの定理のλとは異なる。

この変則版は、極値となる点で全微分df = 0 となる方向と、dg = 0 となる方向が平行であることから導かれる。

例編集

情報理論的エントロピーが最大となる離散的確率分布を見出すことを考えよう。このときエントロピーは確率を変数とする関数で、

$f(p_{1},p_{2},\dots ,p_{n})=-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}$

となる。もちろんこれらの確率の合計は1に等しく、束縛条件を表す関数は

$g(p_{1},p_{2},\dots ,p_{n})=\sum _{k=1}^{n}p_{k}-1$

となる。ラグランジュ乗数を用いてエントロピー最大の点を見つけよう。すべてのi （1から n をとる）に対して次の条件が必要である：

${\frac {\partial }{\partial p_{i}}}(f+\lambda g)=0$

従って

${\frac {\partial }{\partial p_{i}}}\left(-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}+\lambda (\sum _{k=1}^{n}p_{k}-1)\right)=0$

これらn 個の方程式から次の式が得られる：

$-\left({\frac {1}{\ln 2}}+\log _{2}p_{i}\right)+\lambda =0$

これは、すべてのp_i が等しいということを示している（変数はλ だけだから）。

束縛条件 ∑_k p_k = 1 を使って、

$p_{i}={\frac {1}{n}}$

がわかる。すなわち、すべての事象が等確率の一様分布がエントロピー最大の分布である：つまり他のどんな確率分布の場合よりも、確率変数が実際に観測されたときに得られる情報量の期待値が大きいということである。

参考文献編集

^ 三宅敏恒 (1992). 入門微分積分. 培風館. p. 104. ISBN 4-563-00221-6.
^ 清水昭比古「学力低下時代の教え方　第4回　ラグランジの未定係数法」、『日本機械学会誌』第112巻第1093号、一般社団法人日本機械学会、2009年12月、 987-992頁。
^ Joel H. Ferziger; Milovan Perić; 小林敏雄、谷口伸行、坪倉誠訳『コンピュータによる流体力学』シュプリンガー・フェアラーク東京、2003年、195-197頁。ISBN 4-431-70842-1。

NAMs出版プロジェクト

水曜日, 4月 26, 2017