kReese.net

Karush - Kuhn - Tuckerの (KKT) の条件, 時にはKuhn - Tuckerの条件と呼ば, 条件が最適であるために、非線形計画問題を満たすために必要なことです。. KKT条件は、不等式制約を可能にすることで、ラグランジュ乗数法を拡張, 等式制約のみを許可するラグランジェ乗数とは対照的に、.

私たちは非線形最適化問題を考えよう:

最小限に抑える $f(x)$
の対象と: $g_{i}(x)\leq 0 \\ h_{j}(x) = 0$

我々はできるようになる $x^{*}$ 私たちの問題のための相対的な最小点を表す, また、いくつかの制約の資格を満たしている. このと, その後、我々は、全ての要素に対してベクトルが存在すると仮定することができます $\lambda_j \left ( j = 1, \ldots, l \right )$ , ここで、市販等式制約の数を表します。, と $\mu_i\left ( i = 1, \ldots, m \right )$ , ここで、 メートル 不等式制約の数を表します。. これらの定数, $\lambda_j$ と $\mu_i$ , KKT乗数と呼ばれています.

非線形計画問題で開催されるKKT条件のために (NLP), その後、3つの条件のそれぞれを満たす必要があります。 [1-4]. 何が問題の状態プライマルフィージビリティ直した, 不等式と等式制約上その $x^*$ 最適であることが問題のために満たされている必要があります。:

$\left.\begin{matrix} h\left ( x^* \right )=0\\ g\left ( x^* \right )\leq0 \end{matrix}\right\} \textrm{primal feasibility (PF)}$

2番目の条件はデュアル実現可能性条件と呼ばれています. この条件の状態で, むしろ冗長に, その内のすべての要素 $\mu_i$ ゼロより大きくなければなりません。, そして問題の定常性は等しくなければならないこと 0.

$\left.\begin{matrix} \bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0\\ \lambda_i \in \mathbb{R}\\ \mu_i \geq 0 \end{matrix}\right\}\textrm{dual feasibility (DF)}$

問題の定常性は:

$\bigtriangledown f\left ( x^* \right ) + \sum_{i=1}^{m}\lambda_{i}\bigtriangledown h_{i}\left ( x^* \right ) + \sum_{j=1}^{l}\mu_{j}\bigtriangledown g_{j}\left ( x^* \right ) = 0$

他の二つは単純にその条件である一方で リットル と メートル ために満たす必要があります。 $x^*$ 最適なものへ.

満たされなければならない番目の条件は補完的なスラックとして知られています. これは、単純にそれぞれのムーと、それぞれの不等式の制約のためにそれを述べて, 二つの製品がゼロになるはず:

$\mu_i g_{i} \left ( x^* \right ) = 0$

これらの3つの条件が満たされている場合, 我々は、KKT条件と当社のソリューションを満たしている, $x^*$ , NLPの問題の最適解である. そこよりも多分より xは条件を満たす空間で. 問題空間の任意の点位置のすべての要素リットルやメートル, そのようなそのタプル (xは, リットル, メートル) KKT条件を満たすにはKKTポイントと呼ばれます. これらの制約の導出は次の場所にあります。 [1,2]

制約の資格

前述のように, 我々がテストしている点を考慮するポイントのためにいくつかの資格を満たすために必要. 最もよく知られている制約の資格は、線形独立の制約の資格です。 (その他のlicq), 単にことを述べている $h_{j}(x^*)$ と $g_{i}(x^*)$ 時点では他から線形独立である $x^*$ . マンガサリアン- Fromovitzの制約の資格 (MFCQ) の状態で正lineraly独立したが、さらに、同様にその他のlicq $x^*$ . [5]

その他のlicqをリラックスしかしながら、他の制約の修飾子があります。. スレーターの制約修飾子が凸問題に使用することができます。. そのような点xが存在する場合 $h_{j}(x^*) =$ と $g_{i}(x^*) < 0$ すべてのiに対して,Jアクティブで $x^*$ , その後、スレートの条件が成り立つ. [5,6]

制約修飾子の他のタイプは存在するのか, しかし、これらの3つは、最も一般的にKKT資格で使用されているよう.

[1] クーン, H. とタッカー, A., “非線形プログラミング” 第二バークレーシンポジウム論文集 1951, PPの. 481-492.
[2] Karush, W., “サイドの制約などの不等式を持ついくつかの変数関数の極小値”. M. Scが. 論文, 大. of Chicago, シカゴの, 市販, 1939.
[3] クーン, のM. “Karush - Kuhn - Tuckerのtheorema”, インターネット: http://smp.if.uj.edu.pl/~kopiec/MT/Materialy/KarushKuhnTucker.pdf, CDSEM連合. マンハイム, 2006.
[4]McCarl, Bの. とSpreen, T., “非線形最適化条件”, チャンネル. 12, 代数システムを使用して適用数理計画. インターネット: http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/thebook.pdf
[5]Eustaquio, 研究. カラス, メール. とリベイロ, A. 非線形計画法のための制約の資格, テクニカルレポート, 大. パラナ.
[6] 到着する, D. とZalinescu, 総務. “凸プログラミングのいくつかの制約の認定条件の必要性について”, 凸解析のジャーナル, 11 (1), 2004. PPの 95-110.

コンピュータ科学と教育ジャーナル

最近の投稿

Karush - Kuhn - Tuckerの条件

制約の資格