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

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

凸最適化問題における鞍点定理とミニマックス定理についてまとめる

数学 数理最適化

本記事は以下の過去記事で得た結果を用います．

ラグランジュ関数，ラグランジュ双対問題，最適性条件(KKT条件)のあらすじをまとめる - エンジニアを目指す浪人のブログ


勉強を進めていて，凸最適化問題における鞍点定理(saddle point theorem)とミニマックス定理(minimax theorem)を知りました．強双対性や最適性条件(KKT条件)とも関連する重要な内容なので，それらについてまとめておくことにしました．

文献[1]をベースにしてまとめますが，上の過去記事と整合させるため，記号はBoyd and Vandenberghe(2004)に合わせています．はじめに鞍点定理を論じるための準備を行います．つぎに鞍点定理を示して証明します．最後にミニマックス定理を示し鞍点定理との関連についてまとめます．

=================================================================================
記号を定義しておきます．
{\displaystyle \;\;\; \bar{\mathbb{R}} = \mathbb{R} \cup \{ \infty \} }
{\displaystyle \;\;\; \mathbb{R}_+ = [0 ,\infty ) }
{\displaystyle \;\;\; x, \ \bar{x} \in \mathbb{R}^n }
{\displaystyle \;\;\; \lambda, \ \bar{\lambda} \in \mathbb{R}^m }
{\displaystyle \;\;\; \nu, \ \bar{\nu} \in \mathbb{R}^p }
{\displaystyle \;\;\; \Omega = \{ x \in \mathbb{R}^n : f_i(x) \le 0, i=1,\ldots,m, \ h_i(x) = 0, i=1,\ldots,p \} }
{\displaystyle \;\;\; K = \mathbb{R}_+^m \times \mathbb{R}^p \subset \mathbb{R}^{m+p} }


以下の凸最適化問題(主問題) {\displaystyle \mathcal{P} }，ラグランジュ関数 {\displaystyle L : \mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} }， ラグランジュ双対関数 {\displaystyle g : \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} }，ラグランジュ双対問題 {\displaystyle \mathcal{Q} } を導入します．{\displaystyle f_0,f_1,\ldots,f_s } を {\displaystyle \mathbb{R}^n \to \bar{\mathbb{R}} } の微分可能な凸関数，{\displaystyle h_1,\ldots,h_p } を {\displaystyle \mathbb{R}^n \to \mathbb{R} } の微分可能なアフィン関数とします．

(1.1)
{\displaystyle \mathcal{P} \;\;\;\;\ \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 }

(1.2){\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) }

(1.3){\displaystyle \;\;\; g(\lambda,\nu) = \inf_{x} L(x,\lambda,\nu) = \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) }

(1.4)
{\displaystyle \mathcal{Q} \;\;\;\;\ \mathrm{maximize} \;\;\;\; g(\lambda,\nu) }
{\displaystyle \;\;\;\;\;\;\ \ \mathrm{subject \; to} \;\;\ \lambda \succeq 0 \;\;\; (\lambda_i \ge 0 , \ i=1,\ldots,m) }


以下の条件を定義しておきます．

定義 4.1 (スレーターの条件)
{\displaystyle f_i(\tilde{x}) \lt 0,i=1,\ldots,m } をみたすような {\displaystyle \tilde{x} \in \Omega } が存在するとき，{\displaystyle \Omega } はスレーターの条件を満たすという．

以下をみたす組 {\displaystyle (\bar{x},\bar{\lambda},\bar{\nu}) \in \mathbb{R}^n \times K } を {\displaystyle L } の鞍点(saddle point)といいます．

(1.5){\displaystyle \;\;\; L(\bar{x},\lambda,\nu) \le L(\bar{x},\bar{\lambda},\bar{\nu}) \le L(x,\bar{\lambda},\bar{\nu}), \;\;\; \forall \ (x,\lambda,\nu) \in \mathbb{R}^n \times K }


鞍点定理は凸最適化問題における鞍点の有用性を示すものです．その内容と証明を示します．
'--------------------------------------------------------------------------------------------------------------------------------------------
定理 5.1 (鞍点定理)
点 {\displaystyle (\bar{x},\bar{\lambda},\bar{\nu}) } がラグランジュ関数 {\displaystyle L } の鞍点となるような {\displaystyle (\bar{\lambda},\bar{\nu}) \in K } が存在するならば，{\displaystyle \bar{x} } は {\displaystyle \mathcal{P} } の解である．逆に，{\displaystyle \bar{x} } がスレーター条件をみたし {\displaystyle \mathcal{P} } の解であるならば，{\displaystyle L } の鞍点であるような {\displaystyle (\bar{\lambda},\bar{\nu}) \in K } が存在する．

証明.
点 {\displaystyle (\bar{x},\bar{\lambda},\bar{\nu}) \in \mathbb{R}^n \times K } が {\displaystyle \mathcal{P} } についての鞍点のとき，(1.5)の左側より

(※){\displaystyle \;\;\; \sup_{ (\lambda,\nu) \in K} L(\bar{x},\lambda,\nu) = \sup_{(\lambda,\nu) \in K} \left( f_0(\bar{x}) + \sum_{i=1}^m \lambda_i f_i(\bar{x}) + \sum_{i=1}^p \nu_i h_i(\bar{x}) \right) \le L(\bar{x},\bar{\lambda},\bar{\nu}) }

が成り立つ．

{\displaystyle f_i(\bar{x}) \gt 0 } となるある {\displaystyle i \in \{1, \ldots, m \} } について左辺の {\displaystyle \sup } を得るために {\displaystyle \lambda_i \to \infty } とすると左辺は {\displaystyle \infty } となり矛盾である，したがって {\displaystyle f_i(\tilde{x}) \le 0, \ i=1,\ldots,m } でなければならない．つぎに {\displaystyle h_i(\bar{x}) \neq 0 } となるある {\displaystyle i \in \{1, \ldots, p \} } について左辺の {\displaystyle \sup } を得るために {\displaystyle \nu_i \to \mathrm{sgn}(h_i(\bar{x}))) \infty } とすると左辺は {\displaystyle \infty } となり矛盾である({\displaystyle \mathrm{sgn}(\cdot) } の定義は文献[2]にあります)，したがって {\displaystyle h_i(\tilde{x}) = 0, \ i=1,\ldots,p } でなければならない．これらの結果より {\displaystyle \bar{x} \in \Omega } を得る．{\displaystyle \sup } の定義と {\displaystyle (\bar{\lambda},\bar{\nu}) \in K } より

{\displaystyle \;\;\; \sup_{ (\lambda,\nu) \in K} L(\bar{x},\lambda,\nu) \ge L(\bar{x},\bar{\lambda},\bar{\nu}) }

であるので，これと(※)より

(※※){\displaystyle \;\;\; \sup_{ (\lambda,\nu) \in K} L(\bar{x},\lambda,\nu) = L(\bar{x},\bar{\lambda},\bar{\nu}) }

を得る．したがって

{\displaystyle \;\;\; \sup_{ (\lambda,\nu) \in K} L(\bar{x},\lambda,\nu) = \sup_{(\lambda,\nu) \in K} \left( f_0(\bar{x}) + \sum_{i=1}^m \lambda_i f_i(\bar{x}) + \sum_{i=1}^p \nu_i h_i(\bar{x}) \right) \;\;\; \because } (1.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{(\lambda,\nu) \in K} \left( f_0(\bar{x}) + \sum_{i=1}^m \lambda_i f_i(\bar{x}) \right) \;\;\; \because h_i(\bar{x})=0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f_0(\bar{x}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because \lambda_i \ge 0, f_i(\bar{x}) \le 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = L(\bar{x},\bar{\lambda},\bar{\nu}) \;\;\;\;\;\;\;\;\; \because } (※※)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \inf_x L(x,\bar{\lambda},\bar{\nu}) \;\;\;\;\; \because } (1.5)の右側
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \inf_{x \in \Omega} L(x,\bar{\lambda},\bar{\nu}) \;\;\;\; \because \Omega \subset \mathbb{R}^n }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \inf_{x \in \Omega} f_0(x) \;\;\;\;\;\;\;\;\;\;\; \because \lambda_i \ge 0, \ f_i(\bar{x}) \le 0, \ h_i(\bar{x})=0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(\bar{x}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because \Omega \subset \mathbb{R}^n}

であり，3行目と最終行に {\displaystyle f_0(\bar{x}) } があることからすべての不等号は等号となる．最後の不等号が等号となるので {\displaystyle \bar{x} } は {\displaystyle \mathcal{P} } の解である．

逆を示す． {\displaystyle \bar{x} } においてスレーターの条件が成り立ち {\displaystyle \mathcal{P} } の解であるとする．冒頭で示した過去記事で導いた以下の事実を用いる．引用する．

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

これにより任意の {\displaystyle y \in K } について以下を得る．

{\displaystyle \;\;\; L(\bar{x},\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(\bar{x}) + \sum_{i=1}^p \nu_i h_i(\bar{x}) \;\;\; \because } (1.2)
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = f_0(x) + \sum_{i=1}^m \lambda_i f_i(\bar{x}) \;\;\;\;\; \because h_i(\bar{x})=0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le f_0(\bar{x}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because \lambda_i \ge 0, \ f_i(\bar{x}) \le 0 }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = L(\bar{x},\bar{\lambda},\bar{\nu}) \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 双対ギャップ {\displaystyle 0 }

冒頭で示した過去記事で導いた以下の事実を用いる．引用する．(3.6)は過去記事で用いている数式番号である．

(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}) } を得ます．

これより {\displaystyle L(\bar{x},\bar{\lambda},\bar{\nu}) \le L(x,\bar{\lambda},\bar{\nu}) } であり，上の結果もあわせて {\displaystyle L(\bar{x},\lambda,\nu) \le L(\bar{x},\bar{\lambda},\bar{\nu}) \le L(x,\bar{\lambda},\bar{\nu}) } を得る．(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------

{\displaystyle \sup,\ \inf } の定義より

{\displaystyle \;\;\;\;\;\; \sup_{y \in K} \inf_{x \in \mathbb{R}^n} L(x,\lambda,\nu) \le \inf_{x \in \mathbb{R}^n} \sup_{y \in K} L(x,\lambda,\nu) }

が常に成り立ちます．一方で，{\displaystyle (\bar{x},\bar{\lambda},\bar{\nu} ) } が {\displaystyle L } の鞍点のとき

{\displaystyle \;\;\;\;\;\; \inf_{x \in \mathbb{R}^n} \sup_{y \in K} L(x,\lambda,\nu) \le \sup_{y \in K} L(\bar{x},\lambda,\nu) \le L(\bar{x},\bar{\lambda},\bar{\nu}) \le \inf_{x \in \mathbb{R}^n} L(x,\bar{\lambda},\bar{\nu}) \le \sup_{(\lambda,\nu) \in K} \inf_{x \in \mathbb{R}^n} L(x,\lambda,\nu) }

が成り立ちます．したがって，{\displaystyle L } の鞍点が存在するとき，以下が成り立ちます．この結果をミニマックス定理といいます．

{\displaystyle \;\;\;\;\;\; \sup_{y \in K} \inf_{x \in \mathbb{R}^n} L(x,\lambda,\nu) = \inf_{x \in \mathbb{R}^n} \sup_{y \in K} L(x,\lambda,\nu) }

証明.で示したように

{\displaystyle \;\;\;\;\;\; \sup_{y \in K} L(x,\lambda,\nu) = \begin{cases} \infty & \mathrm{if} \;\;\; x \notin \Omega \\ f_0(x) & \mathrm{if} \;\;\; x \in \Omega \end{cases} }

であるので，

{\displaystyle \;\;\;\;\;\; \inf_{x \in \mathbb{R}^n} \sup_{y \in K} L(x,\lambda,\nu) = \inf_{x \in \Omega} f_0(x) }

を得ます．これはミニマックス定理の右辺が {\displaystyle \mathcal{P} } を意味していることを示しています．(1.3)より

{\displaystyle \;\;\;\;\;\; \inf_{x \in \mathbb{R}^n} L(x,\lambda,\nu) = g(\lambda,\nu) }

であるので，

{\displaystyle \;\;\;\;\;\; \sup_{y \in K} \inf_{x \in \mathbb{R}^n} L(x,\lambda,\nu) = \sup_{y \in K} g(\lambda,\nu) }

を得ます．これはミニマックス定理の左辺が {\displaystyle \mathcal{Q} } を意味していることを示しています．以上の議論より，ミニマックス定理は主問題とラグランジュ双対問題の最適値が等しいこと，すなわち強双対性が成り立つことを意味しています．

まとめると，{\displaystyle (\bar{x},\bar{\lambda},\bar{\nu}) } が {\displaystyle L } の鞍点のとき，{\displaystyle \bar{x} } は主問題の最適点となり，{\displaystyle (\bar{\lambda},\bar{\nu}) } はラグランジュ双対問題の最適点となり，それぞれの最適値は等しくなります．
=================================================================================

以上，凸最適化問題における鞍点定理とミニマックス定理についてまとめました．強双対性やKKT条件との関連についても明らかになってきたと思います．


参考文献
[1] University of Washington James V. Burke 先生のノート https://sites.math.washington.edu/~burke/crs/516/notes/undergraduate-nco.pdf
[2] Wikipedia Sign function のページ https://en.wikipedia.org/wiki/Sign_function
[3] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.