エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめる

数学 数理最適化

数理最適化で扱う問題のなかで，凸最適化問題は応用上よく使われること，また，ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)は重要な概念であることはよく知られていると思います．それらを勉強するために読んだもののうち，Boyd and Vandenberghe(2004)の5章がとても好きなので，それをベースにして内容をまとめておくことにしました．準備として4章から用いた部分も少しあります．(凸最適化問題に限らない)主問題とそれに対するラグランジュ関数，ラグランジュ双対問題を設定し，KKT条件を導出していきます．

=================================================================================
[ 0. 準備 ]
標準的な最適化問題(optimization problem)を導入します．{\displaystyle x \in \mathbb{R}^n } です．

(0.1)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ f_i(x) \le 0 , \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; h_i(x) = 0, \;\;\; i=1,\ldots,p }

{\displaystyle \mathcal{D}= \bigcap_{i=0}^m \mathrm{dom} \ f_i \; \cap \; \bigcap_{i=1}^p \mathrm{dom} \ h_i } を最適化問題(0.1)の定義域(domain)といいます，{\displaystyle \mathrm{dom} } は関数の定義域です．点 {\displaystyle x \in \mathcal{D} } が {\displaystyle f_i(x) \le 0, \ i=1,\ldots,m, \ h_i(x) = 0, \ i=1,\ldots,p } をみたすとき，点 {\displaystyle x } は実行可能(feasible)といいます．少なくとも1点の実行可能な点が存在するとき問題(0.1)は実行可能といい，そうでないとき実行不可能(infeasible)といいます．すべての実行可能な点の集合を実行可能集合(feasible set)といいます．{\displaystyle f_0 : \mathbb{R}^n \to \mathbb{R} } を目的関数(objective function)といいます．{\displaystyle f_i(x) \le 0 } を不等式制約(inequality constraints)，{\displaystyle f_i : \mathbb{R}^n \to \mathbb{R} } を不等式制約関数(inequality constraint functions)，{\displaystyle h_i(x) = 0 } を等式制約(equality constraints)，{\displaystyle h_i : \mathbb{R}^n \to \mathbb{R} } を等式制約関数(equality constraint functions)といいます．


問題(0.1)の最適値(optimal value)を {\displaystyle p^* \in [ -\infty,\infty ] } と書くことにします．

(0.2){\displaystyle \;\;\; p^* = \inf \{ f_0(x) \ | \ f_i(x) \le 0, i=1,\ldots,m, \ h_i(x)=0,i=1,\ldots,p \} }

{\displaystyle p^* } が {\displaystyle \pm \infty } をとることを許容します．問題が実行不可能のとき，( {\displaystyle \inf \ \emptyset = \infty } という慣習にしたがい) {\displaystyle p^* = \infty } です．{\displaystyle f_0(x_k) \to - \infty,\ k \to \infty } となる実行可能な点 {\displaystyle x_k } が存在するとき {\displaystyle p^* = - \infty } であり，このとき問題(0.1)は下に有界でない(unbounded below)といいます．


{\displaystyle x = x^* } が実行可能な点で {\displaystyle f_0(x^*) = p^* } のとき {\displaystyle x^* } を最適点(optimal point)といい，すべての最適点の集合 {\displaystyle X_{\mathrm{opt}} } を最適集合(optimal set)といいます．

(0.3){\displaystyle \;\;\; X_{\mathrm{opt}} = \{ x \ | \ f_i(x) \le 0, i=1,\ldots,m, \ h_i(x)=0,i=1,\ldots,p, \ f_0(x)= p^* \} }

以下を明示しておきます．
(0.4){\displaystyle \;\;\; f_i(x^*) \le 0, \;\;\; i=1,\ldots,m }
(0.5){\displaystyle \;\;\; h_i(x^*) = 0, \;\;\; i=1,\ldots,p }

 

ある集合 {\displaystyle C } の2点を結ぶ線分が {\displaystyle C } に含まれるとき，すなわち任意の {\displaystyle x,y \in C } と任意の {\displaystyle \theta \in [ 0,1 ] } について以下が成り立つとき，{\displaystyle C } を凸集合(convex set)といいます．

(0.6){\displaystyle \;\;\; \theta x + (1 - \theta) y \in C }

関数 {\displaystyle f : \mathbb{R}^n \to \mathbb{R} } の定義域 {\displaystyle \mathrm{dom} \ f } が凸集合で任意の {\displaystyle x,y \in \mathrm{dom} \ f } と任意の {\displaystyle \theta \in [ 0,1 ] } について以下が成り立つとき，{\displaystyle f } を凸関数(convex function)といいます．{\displaystyle - f } が凸関数のとき，{\displaystyle f } を凹関数(concave function)といいます．

(0.7){\displaystyle \;\;\; f( \theta x + (1 - \theta) y ) \le \theta f(x) + (1 - \theta) f(y) }

 

凸最適化問題(convex optimization problem)とは，以下の最適化問題のことです．目的関数と不等式制約関数 {\displaystyle f_0,\ldots,f_m } は凸関数，等式制約関数はアフィン関数(affine function)です．

(0.8)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ f_i(x) \le 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; a_i^T x = b_i, \;\;\; i=1,\ldots,p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; } (あるいは {\displaystyle \ A x = b \ } と書く)

 

関数 {\displaystyle f } が微分可能(すなわちその勾配 {\displaystyle \nabla f } が {\displaystyle \mathrm{dom} \ f } の各点で存在し，{\displaystyle \mathrm{dom} \ f } は開集合)であると仮定します．このとき，{\displaystyle f } が凸関数であることと，{\displaystyle \mathrm{dom} \ f } が凸集合かつ任意の {\displaystyle x,y \in \mathrm{dom} \ f } について以下が成り立つことは同値になります．

(0.9){\displaystyle \;\;\; f(y) \ge f(x) + \nabla f(x)^T (y - x) }

この事実の証明は省略しますが，直感的な解釈はBoyd and Vandenberghe(2004) figure 3.2.にあります．(0.9)より，{\displaystyle \nabla f(x)=0 } のときすべての {\displaystyle y \in \mathrm{dom} \ f } について {\displaystyle f(y) \ge f(x) } となります．すなわち微分可能な凸関数は勾配が {\displaystyle 0 } となる点で最小値をとることがわかります．

 


[ 1. ラグランジュ関数とラグランジュ双対関数 ]
標準的な最適化問題を考えます．これを主問題(primal problem)ということにします．

(1.1)(先ほどの(0.1)に同じ)
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x) }
{\displaystyle \mathrm{subject \; to} \;\;\ f_i(x) \le 0 , \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; h_i(x) = 0, \;\;\; i=1,\ldots,p }

定義域 {\displaystyle \mathcal{D} } は空集合でない，すなわち {\displaystyle \mathcal{D} \neq \emptyset } とします．(1.1)が凸最適化問題であることは仮定しません．(1.1)はつぎの問題として解釈することもできます．

(1.1)'
{\displaystyle \mathrm{minimize} \;\;\;\; f_0(x)+\sum_{i=1}^m I_{-}(f_i(x))+\sum_{i=1}^p I_{0}(h_i(x)) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; I_{-}(u)= \begin{cases} 0 \;\;\;\;\; u \le 0 \\ \infty \;\;\; u \gt 0 \end{cases}, \;\;\; I_{0}(u)= \begin{cases} 0 \;\;\;\;\; u = 0 \\ \infty \;\;\; u \neq 0 \end{cases} }


ラグランジュ双対性(Lagrangian duality)の基本的な考え方は(1.1)の不等式制約と等式制約を目的関数に組みいれることです．ラグランジュ関数(Lagrangian) {\displaystyle L:\mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R}, \ \mathrm{dom} \ L = \mathcal{D} \times \mathbb{R}^m \times \mathbb{R}^p } を以下で定義します．{\displaystyle \lambda \in \mathbb{R}^m ,\nu \in \mathbb{R}^p } をラグランジュ乗数(Lagrange multiplier)といいます．

(1.3){\displaystyle \;\;\; L(x,\lambda,\nu) = f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{i=1}^p \nu_i h_i(x) }


ラグランジュ双対関数(Lagrange dual function)(あるいは単に双対関数)を定義します．

(1.4){\displaystyle \;\;\; g(\lambda,\nu) = \inf_{x \in \mathcal{D}} L(x,\lambda,\nu) = \inf_{x \in \mathcal{D}} \left( f_0(x)+\sum_{i=1}^m \lambda_i f_i(x) +\sum_{i=1}^p \nu_i h_i(x) \right) }

(1.3)が下に有界でないならば，(1.4)はその値に {\displaystyle - \infty } をとります．また定義より，(1.1)が凸最適化問題でなくてもラグランジュ双対関数(1.4)は凹関数です．そのことを示します．よく知られている性質(文献[2]Proposition 2.16.に証明があります) {\displaystyle \inf (f_1 + f_2) \ge \inf f_1 + \inf f_2 } を使うと，ある {\displaystyle \theta \in [ 0,1 ] } について

{\displaystyle \;\;\; \theta g(\lambda_1,\nu_1) + (1-\theta)g(\lambda_2,\nu_2) = \theta \inf_{x \in \mathcal{D}} L(x,\lambda_1,\nu_1) + (1-\theta)\inf_{x \in \mathcal{D}} L(x,\lambda_2,\nu_2) }
{\displaystyle \;\;\;\;\;\; \le \inf_{x \in \mathcal{D}} \left( \theta L(x,\lambda_1,\nu_1) + (1-\theta) L(x,\lambda_2,\nu_2) \right)= g( \theta \lambda_1 + (1-\theta) \lambda_2,\theta \nu_1 + (1-\theta) \nu_2 ) }

であるので，{\displaystyle g(\theta,\nu)} はつねに凹関数です．


{\displaystyle \lambda \succeq 0 }，すなわちベクトル {\displaystyle \lambda } の各要素 {\displaystyle \lambda_i \ge 0 } のとき，すべての {\displaystyle u } について {\displaystyle \lambda_i u \le I_{-}(u), \ \nu_i u \le I_{0}(u) } です．これと(1.1)'(1.4)から以下が成り立ち，{\displaystyle \lambda \succeq 0 } のときラグランジュ双対関数 {\displaystyle g(\lambda,\nu) } は最適値 {\displaystyle p^* } の下界になっていることがわかります．

(1.5){\displaystyle \;\;\; g(\lambda,\nu) \le p^* \;\;\;\;\;\; \mathrm{if} \;\;\; \lambda \succeq 0 }

{\displaystyle g(\lambda,\nu)= - \infty } のとき，(1.5)は成り立ちますが意味を成しません．{\displaystyle \lambda \succeq 0, \ (\lambda,\nu) \in \mathrm{dom} \ g } をみたすとき，すなわち {\displaystyle g(\lambda,\nu) \gt - \infty } のときラグランジュ双対関数は {\displaystyle p^* } の(意味のある)下界となります．このとき {\displaystyle (\lambda,\nu) } は双対実行可能(dual feasible)といいます．

 


[ 2. ラグランジュ双対問題 ]
以下の問題をラグランジュ双対問題(Lagrange dual problem)といいます．

(2.1)
{\displaystyle \mathrm{maximize} \;\;\;\; g(\lambda,\nu) }
{\displaystyle \mathrm{subject \; to} \;\;\ \lambda \succeq 0 }

この問題は {\displaystyle g(\lambda,\nu) } が凹関数で {\displaystyle \lambda \succeq 0 } が凸集合であるので(主問題が凸最適化問題か否かにかかわらず)凸最適化問題です．(2.1)の最適値を {\displaystyle d^* }，そのときの {\displaystyle (\lambda,\nu) } を最適点 {\displaystyle (\lambda^*,\nu^*) } とします．以下を明示しておきます．

(2.2){\displaystyle \;\;\; \lambda_i^* \ge 0, \;\;\; i=1,\ldots,m }

(1.5)もあわせて考えると {\displaystyle d^* } は {\displaystyle p^* } の最良の下界なので，(主問題が凸最適化問題か否かにかかわらず)以下が成り立ちます．

(2.3){\displaystyle \;\;\; d^* \le p^* }

この性質を弱双対性(weak duality)といいます．主問題が下に有界でない({\displaystyle p^* = - \infty })とき，双対実行可能でない({\displaystyle d^* = - \infty }) でなければなりません．逆に，ラグランジュ双対問題が上に有界でない({\displaystyle d^* = \infty })とき，主問題が実行不可能({\displaystyle p^* = \infty })でなければなりません．もし

(2.4){\displaystyle \;\;\; d^* = p^* }

が成り立つならば，強双対性(strong duality)が成り立つといいます．{\displaystyle p^* - d^* \ge 0 } を最適双対ギャップ(optimal duality gap)といいます．


以下の事実が成り立ちます．

事実.
主問題(1.1)が凸最適化問題であるとき，すなわち(0.8)であるとき，つぎのスレーターの条件(Slater's condition)が成り立つならば，強双対性が成り立つ．

スレーターの条件
以下が成り立つような {\displaystyle \tilde{x} \in \mathrm{relint} \ \mathcal{D} } が存在する．

(2.5){\displaystyle \;\;\; f_i(\tilde{x}) \lt 0, \;\;\; i=1,\ldots,m, \;\;\; A \tilde{x} =b }

証明.
省略．Boyd and Vandenberghe(2004) 5.3.2を参照．

{\displaystyle \mathrm{relint} \ \cdot } は相対的内部(relative interior)であり，以下の過去記事にあります．

内部と相対的内部の違いについて考える - エンジニアを目指す浪人のブログ

 

凸最適化問題においてスレーターの条件が成り立つとき，(0.8)の不等式制約と等式制約をみたす実行可能な点 {\displaystyle \tilde{x} \in \mathcal{D} } が存在します，すなわち {\displaystyle p^* \lt \infty } です．したがって，凸最適化問題においてスレーターの条件が成り立つことは，強双対性が成り立つことだけでなく，{\displaystyle p^* \gt - \infty } を仮定すれば，{\displaystyle g(\lambda^*,\nu^*) = d^* = p^* \in (-\infty,\infty) } となる双対実行可能な {\displaystyle (\lambda^*,\nu^*) } が存在することを意味しています．

 


[ 3. 最適性条件 ]
主問題(1.1)とラグランジュ双対問題(2.1)が実行可能と双対実行可能，すなわち {\displaystyle p^* \lt \infty, \ - \infty \lt d^* } となる最適点 {\displaystyle x^*, \ (\lambda^*,\nu^*) } が存在し，かつ強双対性が成り立つと仮定します．すると

(3.1)
{\displaystyle \;\;\; f_0(x^*) = g(\lambda^*,\nu^*) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\ \because } (2.4)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf_x \left( f_0(x) + \sum_{i=1}^m \lambda_i^* f_i(x) + \sum_{i=1}^p \nu_i^* h_i(x) \right) \;\;\;\;\;\; \because } (1.4)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(x^*) + \sum_{i=1}^m \lambda_i^* f_i(x^*) + \sum_{i=1}^p \nu_i^* h_i(x^*) \;\;\;\;\;\;\;\;\;\;\; \because \inf } の定義
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(x^*) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } (0.4)(0.5)(2.2)

となり，結果的に(3.1)の2つの不等号は等号となります．3行目の不等号が等号となるので，{\displaystyle x^* } は {\displaystyle L(x,\lambda^*,\nu^*) } を最小化することがわかります(他にも {\displaystyle L(x,\lambda^*,\nu^*) } を最小化する {\displaystyle x } が存在する場合があります)．4行目の不等号が等号となるので，

(3.2){\displaystyle \;\;\; \sum_{i=1}^m \lambda_i^* f_i(x^*) = 0 }

となり，総和の各項は非正なので，以下を得ます．

(3.2)'{\displaystyle \;\;\; \lambda_i^* f_i(x^*) = 0, \;\;\; i=1,\ldots,m }

この条件を相補性条件(complementary slackness condition)といいます; これは(強双対性が成り立つとき)任意の {\displaystyle x^*} と任意の {\displaystyle (\lambda^*,\nu^*) } について成り立ちます．相補性条件(3.2)'は以下2つの同値な条件(片方でよい)で表現することもできます．

(3.3){\displaystyle \;\;\; \lambda_i^* \gt 0 \; \Longrightarrow \; f_i(x^*) = 0 }

(3.3)'{\displaystyle \;\;\; f_i(x^*) \lt 0 \; \Longrightarrow \; \lambda_i^* = 0 }


以下では，{\displaystyle f_0,\ldots,f_m,h_1,\ldots,h_p } が微分可能(したがってそれらの定義域は開集合)であると仮定します．主問題(1.1)が凸最適化問題であることは(まだ)仮定しません．

主問題(1.1)とラグランジュ双対問題(2.1)が実行可能と双対実行可能，すなわち {\displaystyle p^* \lt \infty, \ - \infty \lt d^* } となる最適点 {\displaystyle x^*, \ (\lambda^*,\nu^*) } が存在し，かつ強双対性が成り立つと仮定します．このとき(3.1)の直後に述べたように {\displaystyle x^* } は {\displaystyle L(x,\lambda^*,\nu^*) } を最小化するので，(制約なし最小化問題についての)最適性の1次の必要条件(文献[3]THEOREM 1.1.1 に証明があります)よりその勾配は {\displaystyle x = x^* } で {\displaystyle 0 }，すなわち以下でなければなりません．

(3.4){\displaystyle \;\;\; \nabla f_0(x^*)+\sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) +\sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0 }


ここまでの議論を整理します．主問題(1.1)とラグランジュ双対問題(2.1)が実行可能と双対実行可能，すなわち {\displaystyle p^* \lt \infty, \ - \infty \lt d^* } となる最適点 {\displaystyle x^*, \ (\lambda^*,\nu^*) } が存在すると仮定します．すると(0.4)(0.5)(2.2)は成り立ちます．強双対性が成り立つと仮定すると(3.2)'は必要条件です．強双対性が成り立つことと {\displaystyle f_0,\ldots,f_m,h_1,\ldots,h_p } が微分可能であることを仮定すると(3.4)は必要条件です．したがって以下を得ます．

(3.5)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; f_i(x^*) \le 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; h_i(x^*) = 0, \;\;\; i=1,\ldots,p }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lambda_i^* \ge 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \lambda_i^* f_i(x^*) = 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\; \nabla f_0(x^*)+\sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) +\sum_{i=1}^p \nu_i^* \nabla h_i(x^*) = 0 }

これをカルーシュ・キューン・タッカー条件(Karush-Kuhn-Tucker condition)(あるいはKKT条件)といいます．

まとめると，目的関数，不等式制約関数，等式制約関数が微分可能な任意の(凸最適化問題でなくてもよい)最適化問題は，実行可能かつ双対実行可能かつ強双対性が成り立つ(主問題とラグランジュ双対問題の最適点が存在する)ならばその最適点はKKT条件(3.5)をみたしていなければなりません．すなわちKKT条件は最適点 {\displaystyle x^*, \ (\lambda^*,\nu^*) } が存在し最適双対ギャップが {\displaystyle 0 } であるための必要条件です．


主問題(1.1)が凸最適化問題のとき，すなわち(0.8)であるとき，KKT条件はそれをみたす点が最適点でありかつ最適双対ギャップが {\displaystyle 0 } であるための十分条件です．いいかえると，{\displaystyle f_i } が凸関数で {\displaystyle h_i } がアフィン関数，さらに {\displaystyle \tilde{x},\tilde{\lambda},\tilde{\nu} } が以下のKKT条件

(3.6)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; f_i(\tilde{x}) \le 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; h_i(\tilde{x}) = 0, \;\;\; i=1,\ldots,p }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \tilde{\lambda}_i \ge 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \tilde{\lambda}_i f_i(\tilde{x}) = 0, \;\;\; i=1,\ldots,m }
{\displaystyle \;\;\;\;\;\;\; \nabla f_0(\tilde{x})+\sum_{i=1}^m \tilde{\lambda}_i \nabla f_i(\tilde{x}) +\sum_{i=1}^p \tilde{\nu}_i \nabla h_i(\tilde{x}) = 0 }

をみたす任意の点であるとき， {\displaystyle \tilde{x}, \ (\tilde{\lambda},\tilde{\nu}) } は主問題とラグランジュ双対問題の最適点となり，最適双対ギャップは {\displaystyle 0 } となります．このことを示します．

(3.6)が成り立っているとします．(3.6)の最初の2つの条件より主問題は {\displaystyle \tilde{x} } で実行可能，すなわち {\displaystyle p^* \lt \infty } となります．(3.6)の3つめの条件 {\displaystyle \tilde{\lambda}_i \ge 0 } と凸関数の非負加重和はまた凸関数であること(文献[4]Rule1に証明があります)より，{\displaystyle L(x, \tilde{\lambda},\tilde{\nu}) } は {\displaystyle x } についての凸関数です; (3.6)の最後の条件はその勾配が {\displaystyle x = \tilde{x} } で {\displaystyle 0 } であることを意味しています，したがって(0.9)の直後に述べた事実により {\displaystyle L(x, \tilde{\lambda},\tilde{\nu}) } は {\displaystyle x = \tilde{x} } で最小値をとります，すなわち {\displaystyle g(\tilde{\lambda},\tilde{\nu}) = L(\tilde{x}, \tilde{\lambda},\tilde{\nu}) } を得ます．最終的に，

(3.7)
{\displaystyle \;\;\; g(\tilde{\lambda},\tilde{\nu}) = L(\tilde{x}, \tilde{\lambda},\tilde{\nu}) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f_0(\tilde{x}) + \sum_{i=1}^m \tilde{\lambda}_i f_i(\tilde{x}) + \sum_{i=1}^p \tilde{\nu}_i h_i(\tilde{x}) \;\;\;\;\;\;\;\;\;\;\; \because } (1.3)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f_0(\tilde{x}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } (3.6)の2つめの条件と4つめの条件

となり，最適双対ギャップは {\displaystyle 0 }，すなわち {\displaystyle \tilde{x}, (\tilde{\lambda},\tilde{\nu}) } は最適値であることが得られます．

まとめると，目的関数，不等式制約関数，等式制約関数が微分可能な任意の凸最適化問題は，KKT条件をみたす任意の点 {\displaystyle \tilde{x}, (\tilde{\lambda},\tilde{\nu}) } は強双対性をみたす最適点となります．

 

上で導出した十分条件は，凸最適化問題ではKKT条件をみたさない最適値が存在することを意味しています．(凸でなくてもよい)任意の最適化問題ではKKT条件は必要条件でした．凸最適化問題であるという条件を追加すると強双対性をみたす最適値が存在することがゆるい条件となり，KKT条件が(相対的に)きつい条件となり十分条件となるので，それをみたさない最適値が存在するということです．

使いやすくするために，先ほどの事実.を用います．目的関数，不等式制約関数，等式制約関数が微分可能なスレーターの条件をみたす凸最適化問題を考えます．スレーターの条件(2.5)は({\displaystyle p^* \gt - \infty } を仮定すれば) {\displaystyle g(\lambda^*,\nu^*) = d^* = p^* \in (-\infty,\infty) } となる双対実行可能な {\displaystyle (\lambda^*,\nu^*) } が存在することを意味しています．したがってKKT条件(3.5)(の導出と同様にこれ)を得ることができるので，このときKKT条件は必要条件で(も)あることがわかります．

まとめると，目的関数，不等式制約関数，等式制約関数が微分可能なスレーターの条件をみたす凸最適化問題は，KKT条件は最適点 {\displaystyle x^*, \ (\lambda^*,\nu^*) } が存在し最適双対ギャップが {\displaystyle 0 } であるための必要十分条件です，いいかえると，最適双対ギャップが {\displaystyle 0 } であり(必ず)KKT条件をみたす最適点が存在します．
=================================================================================

以上，Boyd and Vandenberghe(2004)の5章をベースにして，ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめました．

 

参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] University of California, Davis  John K. Hunter先生のノート https://www.math.ucdavis.edu/~hunter/m125b/ch2.pdf
[3] University of Washington  Jim Burke先生のノート https://sites.math.washington.edu/~burke/crs/516/notes/ch1.pdf
[4] Princeton University  Amir Ali Ahmadi先生のノート http://www.princeton.edu/~amirali/Public/Teaching/ORF363_COS323/F14/ORF363_COS323_F14_Lec6.pdf
[5] Stanford University  Stephen Boyd先生のノート https://stanford.edu/class/ee364a/lectures/duality.pdf
[6] Mathematics Stack Exchange http://math.stackexchange.com/questions/379543/kkt-and-slaters-condition
[7] Wikipedia  Karush–Kuhn–Tucker conditionsのページ https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions