3

KKT条件の導出

3529
0

はじめに

制御工学で非線形計画のKarush-Kuhn-Tucker条件(KKT条件)を触れることがあったのでまとめる。非専門分野なのでご指摘頂けると嬉しいです。

不等式制約と等式制約付き非線形計画のKKT条件

この節では、不等式制約と等式制約付き非線形計画のKKT条件について触れる。KKT条件は、非線形計画問題の最適性の必要条件である。非線形計画は下式で与えるとする。

minf(x)s.t.gi(x)0(1)hj(x)=0

このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。

(2.1)f(x)+i=1myigi(x)+j=1lzihj(x)=0,(2.2)hj(x)=0,(2.3)gi(x)0,(2.4)yi0,   (2.5)yigi(x)=0 

Farkasの補題からのKKT条件の導出

KKT条件をFarkasの補題を用いて導出する。局所最適解近傍に着目してFarkasの補題を用いて導出するのが基本的な方針である。

Farkasの補題

任意の行列Aと任意のベクトルbに対して次の命題がいずれか一方が成り立つ。
(1) Ax=bx0を満たすxが存在する。
(2) ATy0bTy>0を満たすyが存在する。

Farkasの補題から簡単な式変形をすることで系1を得る。

次の命題がいずれか一方が成り立つ。
(1) Au+Bv+c=0u0を満たすuvが存在する。
(2) ATy0BTy=0cTy<0を満たすyが存在する。

A=[A,B,B],x=[u,v+,v]T,v=v+v,b=cとおく。Farkasの補題より系1が求まる。

Mangasarizan-Fronovitz制約を想定する(MF制約想定)。

MF制約想定とは
hj(x)(j=1,2,..l)は1次独立である。gi(x)Ts<0かつhj(x)Ts=0を満たすsが存在する。ただし、I(x)=i|gi(x)=0である。

xを式(1)の局所最適解とする。ただし、fhjは微分可能であるものとする。このとき、以下を満たすsは存在しない。

f(x)Ts<0gi(x)Ts<0(3)hj(x)Ts=0

許容方向sが存在すると仮定する。xが局所最適解であるとする。

不等式制約について、

gi(x+αs)=gi(x)+αgi(x)Ts+o(α)

十分小さいαではgi(x+αs)<0であり、不等式制約を満たすことがわかる。

等式制約について

hj(x+αs)=hj(x)+αhj(x)Ts+o(α)

十分小さいαではhj(x+αs)=0であり、等式制約を満たすことがわかる。

xは局所最適解であるので、十分小さいαでは下式が成り立つ。

f(x+αs)=f(x)+αf(x)Tsf(x)

しかし、f(x)Ts<0なので矛盾する。よって、sは存在しない。

&&& KKT条件
(2.1)f(x)+i=1myigi(x)+j=1lzihj(x)=0,(2.2)hj(x)=0,(2.3)gi(x)0,(2.4)yi0,   (2.5)yigi(x)=0 

&&&prf KKT条件の導出

式(3)より系1(2)が成り立たないことがわかる。よって、系1(1)が成り立つ。

f(x)+iI(x)yigi(x)+j=1lzihj(x)=0yi0

iI(x)のときyi=0とおけば、yigi(x)=0yigi(x)=0である。

f(x)+i=1myigi(x)+j=1lzihj(x)=0yi0yigi(x)=0

等式制約と不等式制約を満足する必要があることを思い出せば下式を得る。

hj(x)=0,gi(x)0

以上より、式(2.1)~(2.5)のKKT条件を得る。

引用

ラグランジュ双対関数からのKKT条件の導出

KKT条件をラグランジュ双対関数を用いて導出する。ラグランジュ双対関数とSlaterの制約に着目して、強双対定理を仮定してKKT条件を導出するのが基本的な方針である。

引用

不等式制約付き非線形計画のKKT条件

この節では、不等式制約付き非線形計画のKKT条件について触れる。
非線形計画は下式で与えるとする。

minf(x)(4)s.t.gi(x)0

このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。

(5.1)f(x)+i=1myigi(x)=0,(5.2)gi(x)0,(5.3)yi0,   (5.4)yigi(x)=0 

Fritz Johnの定理からのKKT条件の導出

KKT条件をFritz Johnの定理を用いて導出する。
局所最適解近傍に着目してGordanの二者択一の定理を用いてFritz Johnの定理を導出し、その後線形独立制約を想定してKKT条件を導出するのが基本的な方針である。はじめにFritz Johnの定理とGordanの二者択一定理を紹介し、Fritz Johnの定理を導出する。

Fritz Johnの定理

不等式制約つき問題の局所最適解xにおいて、fgiが微分可能ならば、(z0,z)(0,0)となる実数z0l次元ベクトルzが存在し、式(6)が成り立つ。

z0f(x)+i=1lzigi(x)=0,gi(x)0,zi0,(6)zigi(x)=0.

Gordanの二者択一定理

任意の行列Aに対して次の命題がいずれか一方が成り立つ。
(1) Ax>0を満たすxが存在する。
(2) ATy=0y0y0を満たすyが存在する。

Fritz Johnの定理の導出

xが局所最適解ならば式7を満たすベクトルsは存在しない。

f(x)Ts<0(7)gi(x)Ts<0 ,iI(x)

式7より、Ax>0を満たすxは存在しない。
ただし、

A=(f(x)Tg1(x)Tgk(x)T)

Gordanの二者択一定理(1)が成り立たないので(2)が成り立つ。つまり、ATy=0y0y0を満たすyが存在する。

ATy=(f(x),g1(x),,gk(x))(y0y1yk)=y0f(x)y1g1(x)ykgk(x)=0

まとめると、

y0f(x)+iI(x)yigi(x)=0

iI(x)のとき、yi=0とおけば、yigi(x)=0yigi(x)=0である。
iI(x)のときgi(x)=0なのでyigi(x)=0である。

不等式制約gi(x)0を満たす必要があることを思い出せば、Fritz Johnの定理を得る。

y0f(x)+i=1lyigi(x)=0,gi(x)0,yi0,yigi(x)=0.

KKT条件の導出

線形独立制約を想定する。Fritz Johnの定理よりy0=0と仮定すると、線形独立制約想定よりyi=0となり矛盾する。よって、y0>0である。yi=yi/y0と改めて書き直せばKKT条件をえる。

f(x)+i=1myigi(x)=0,gi(x)0,yi0,   yigi(x)=0

引用

おわりに

Slaterの制約想定を仮定するとラグランジュ双対関数において強双対定理がなぜ成り立つのかまだ理解できていないです。

引用

投稿日:2021424
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

hdk105
hdk105
14
15063
計測・制御・情報に興味があります. 備忘録として残していきます.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. はじめに
  2. 不等式制約と等式制約付き非線形計画のKKT条件
  3. Farkasの補題からのKKT条件の導出
  4. ラグランジュ双対関数からのKKT条件の導出
  5. 不等式制約付き非線形計画のKKT条件
  6. Fritz Johnの定理からのKKT条件の導出
  7. おわりに