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

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

弱双対性の幾何的な解釈と，凸最適化問題における強双対性とスレーターの条件の幾何的な解釈をまとめる

数学 数理最適化

本記事は以下の過去記事の内容を用います．

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

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


勉強を進めていて，最適化問題における弱双対性と強双対性の幾何的解釈について重要に感じたので，その内容をまとめておくことにしました．Boyd and Vandenberghe(2004)の5章3節をベースにしています．

=================================================================================

目次

{\displaystyle \; } 0. 準備
{\displaystyle \; } 1. 弱双対性の幾何的な解釈
{\displaystyle \;\;\; } 1.1. 関数の値域による方法
{\displaystyle \;\;\; } 1.2. 関数のエピグラフによる方法
{\displaystyle \; } 2. 凸最適化問題の強双対性
{\displaystyle \;\;\; } 2.1. スレーターの条件
{\displaystyle \;\;\; } 2.2. 証明と幾何的な解釈


[ 0. 準備 ]

冒頭の過去記事(ラグランジュ関数)の内容を必要とします．

同記事にある標準的な最適化問題を再掲します．{\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 f_0,\ldots,f_m } は凸関数，等式制約関数はアフィン関数です．

(0.2)
{\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 \ } と書く)


以下の記号を準備します．

(0.3){\displaystyle \;\;\; \mathcal{D}= \bigcap_{i=0}^m \mathrm{dom} \ f_i \; \cap \; \bigcap_{i=1}^p \mathrm{dom} \ h_i }

(0.4){\displaystyle \;\;\; x \in \mathbb{R}^n , \ x \preceq 0 \ \Leftrightarrow \ x_i \le 0, \ i = 1, \ldots,n }

(0.5){\displaystyle \;\;\; \mathbb{R}_+ = \mathbb{R} \cap [ 0 , \infty ) }



[ 1. 弱双対性の幾何的な解釈 ]

弱双対性の幾何的な解釈を二つの方法について示します．


[ 1.1. 関数の値域による方法 ]

不等式制約関数，等式制約関数，目的関数のとりうる値の集合を以下とします．

(1.1.1){\displaystyle \;\;\; \mathcal{G} = \{ \left( f_1(x), \ldots, f_m(x),h_1(x), \ldots, h_p(x), f_0(x) \right) \in \mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R} \ | \ x \in \mathcal{D} \} }


最適化問題(0.1)の最適値 {\displaystyle p^* } とラグランジュ双対関数 {\displaystyle g(\lambda,\nu) } は {\displaystyle \mathcal{G} } を用いて以下で表現できます．

(1.1.2){\displaystyle \;\;\; p^* = \inf \{ t \ | \ (u,v,t) \in \mathcal{G}, \ u \preceq 0, \ v = 0 \} }

(1.1.3){\displaystyle \;\;\; g(\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) }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(ラグランジュ関数)(1.4)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf \left\{ \left. \sum_{i=1}^m \lambda_i u_i +\sum_{i=1}^p \nu_i v_i + t \ \right| \ (u,v,t) \in \mathcal{G} \right\} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf \left\{ \left. (\lambda,\nu,1)^T (u,v,t) \ \right| \ (u,v,t) \in \mathcal{G} \right\} }

この下限 {\displaystyle \inf } が有限のとき以下の不等式を得ます．{\displaystyle \mathcal{G} } の支持超平面(supporting hyperplane)です(文献[2]にあります)．法線ベクトル(normal vector)の最後の項が {\displaystyle 1 } であり非零なので，垂直でない(nonvertical)支持超平面ということもあります．

(1.1.4){\displaystyle \;\;\; (\lambda,\nu,1)^T (u,v,t) \ge g(\lambda,\nu) }


ここで以下を仮定します．

(1.1.5){\displaystyle \;\;\; \lambda \succeq 0 }

すると弱双対性を得ます．

(1.1.6){\displaystyle \;\;\; p^* = \inf \{ t \ | \ (u,v,t) \in \mathcal{G}, \ u \preceq 0, \ v = 0 \} \;\;\; \because } (1.1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \inf \{ (\lambda,\nu,1)^T (u,v,t) \ | \ (u,v,t) \in \mathcal{G}, \ u \preceq 0, \ v = 0 \} \;\;\; \because } (1.1.5)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge \inf \{ (\lambda,\nu,1)^T (u,v,t) \ | \ (u,v,t) \in \mathcal{G} \} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = g(\lambda,\nu) \;\;\; \because } (1.1.3)


ここまでの関数の値域による解釈を，不等式制約一つのみのときの簡単な問題について以下に示します．

'--------------------------------------------------------------------------------------------------------------------------------------------
Figure 5.3 の解釈のメモ

・実線は支持超平面(直線) {\displaystyle t = - \lambda u + g(\lambda)}
・{\displaystyle \lambda \succeq 0 } なので支持超平面(直線)は右下がり(あるいは水平)
・{\displaystyle \lambda } を決めると支持超平面の傾き {\displaystyle - \lambda } が決まる
・支持超平面を {\displaystyle \mathcal{G} } と接するようにとれば切片 {\displaystyle g(\lambda) } も決まる
・(1.1.4)からもわかるように支持超平面の法線ベクトル {\displaystyle (\lambda,1) } と点 {\displaystyle (u,t) \in \mathcal{G} } は支持超平面に対して同じ方向を向く
・(1.1.2)からもわかるように {\displaystyle p^* } は {\displaystyle (u,t) \in \mathcal{G} \cap (u \le 0) } における {\displaystyle t } の最小値である
'--------------------------------------------------------------------------------------------------------------------------------------------

'--------------------------------------------------------------------------------------------------------------------------------------------
Figure 5.4 の解釈のメモ

・{\displaystyle \mathcal{G} } は(見た目で明らかに)凸集合ではない
・{\displaystyle \lambda \succeq 0 } のなかから3つ {\displaystyle \lambda } を選んで図示している
・支持超平面(直線)のうち {\displaystyle t } 軸の切片が最大となるとき {\displaystyle \lambda = \lambda^* }
・その最大の切片が {\displaystyle t = d^* }
・双対ギャップ {\displaystyle p^* - d^* \gt } なので，強双対性は成り立たない
・{\displaystyle \mathcal{G} } が凸集合ならば強双対性 {\displaystyle p^* = d^* } が成り立ちそうに思える
'--------------------------------------------------------------------------------------------------------------------------------------------


[ 1.2. 関数のエピグラフによる方法 ]

集合 {\displaystyle \mathcal{A} } を定義します．{\displaystyle \mathcal{A} } は {\displaystyle \mathcal{G} } 上のすべての点を含むので，{\displaystyle \mathcal{G} } のエピグラフの一種と考えることができます．

(1.2.1){\displaystyle \;\;\; \mathcal{A} = \mathcal{G} + \left( \mathbb{R}_+^m \times \{ 0 \} \times \mathbb{R}_+ \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \{ (u,v,t) \ | \ \exists x \in \mathcal{D}, \; f_i(x) \le u_i,i=1,\ldots,m, \; h_i(x) = v_i,i=1,\ldots,p, \; f_0(x) \le t \} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \subseteq \mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R} }


最適化問題(0.1)の最適値 {\displaystyle p^* } は {\displaystyle \mathcal{A} } を用いて以下で表現できます．

(1.2.2){\displaystyle \;\;\; p^* = \inf \{ t \ | \ (u,v,t) \in \mathcal{G}, \ u \preceq 0, \ v = 0 \} \;\;\; \because } (1.1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf \{ t \ | \ (0,0,t) \in \mathcal{A} \} }

ここで以下を仮定します．

(1.2.3){\displaystyle \;\;\; \lambda \succeq 0 }

このときラグランジュ双対関数は以下です．

(1.2.4){\displaystyle \;\;\; g(\lambda,\nu) = \inf \left\{ \left. (\lambda,\nu,1)^T (u,v,t) \ \right| \ (u,v,t) \in \mathcal{G} \right\} \;\;\; \because } (1.1.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \inf \left\{ \left. (\lambda,\nu,1)^T (u,v,t) \ \right| \ (u,v,t) \in \mathcal{A} \right\} \;\;\; \because } (1.2.3)

この下限 {\displaystyle \inf } が有限のとき以下の不等式を得ます．{\displaystyle \mathcal{A} } の支持超平面です．

(1.2.5){\displaystyle \;\;\; (\lambda,\nu,1)^T (u,v,t) \ge g(\lambda,\nu) }


{\displaystyle \mathrm{bd} \ \cdot } は集合の境界(boundary)です(文献[3]にあります)．以下の弱双対性を得ます．

(1.2.6){\displaystyle \;\;\; (0,0,p^*) \in \mathrm{bd} \ \mathcal{A} \;\;\; \because } (1.2.2)

(1.2.7){\displaystyle \;\;\; p^* = (\lambda,\nu,1)^T (0,0,p^*) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \ge g(\lambda,\nu) \;\;\; \because } (1.2.5)(1.2.6)

強双対性 {\displaystyle p^* = d^* } が成り立つための必要十分条件は，ある {\displaystyle (\lambda,\nu) } について(1.2.7)の等号が成り立つ，すなわち境界上の点 {\displaystyle (0,0,p^*) \in \mathrm{bd} \ \mathcal{A} } で {\displaystyle \mathcal{A} } の垂直でない支持超平面が存在することです．


ここまでのエピグラフによる解釈を，不等式制約一つのみのときの簡単な問題について以下に示します．



[ 2. 凸最適化問題の強双対性 ]

[ 2.1. スレーターの条件 ]

冒頭の過去記事(ラグランジュ関数)にある事実を再掲します．{\displaystyle \mathrm{relint} \ \cdot } は集合の相対的内部(relative interior)です(冒頭の過去記事(内部と相対的内部)にあります)．式番号は変更しています．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実.(再掲)

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

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

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


[ 2.2. 証明と幾何的な解釈 ]

いくつか仮定します．

'--------------------------------------------------------------------------------------------------------------------------------------------
仮定.

集合 {\displaystyle \mathcal{D} } は空集合でない内部を持つ，すなわち以下が成り立つ．

(2.2.1){\displaystyle \;\;\; \mathrm{relint} \ \mathcal{D} = \mathrm{Int} \ \mathcal{D} \;\;\; (\neq \emptyset ) }

{\displaystyle p \times n } 行列 {\displaystyle A } は行フルランク，すなわち以下が成り立つ．

(2.2.2){\displaystyle \;\;\; \mathrm{rank} A = p }

最適値は有限，すなわち以下が成り立つ．

(2.2.3){\displaystyle \;\;\; p^* \lt \infty }

'--------------------------------------------------------------------------------------------------------------------------------------------


スレーターの条件は凸最適化問題における強双対性を保証することを証明します．

凸最適化問題ならば {\displaystyle \mathcal{A} } は凸集合です．凸集合 {\displaystyle \mathcal{B} } を以下で定義します．

(2.2.4){\displaystyle \;\;\; \mathcal{B} \{ (0,0,s) \in \mathbb{R}^m \times \mathbb{R}^p \times \mathbb{R} \ | \ s \lt p^* \} }

{\displaystyle (u,v,t) \in \mathcal{A} \cap \mathcal{B} } と仮定します．{\displaystyle (u,v,t) \in \mathcal{B} } なので {\displaystyle u = 0, \ v = 0, \ t \lt p^* } です．{\displaystyle (u,v,t) \in \mathcal{A} } なので {\displaystyle \exists x, \ f_i(x) \le 0, i=1,\ldots,m, \ Ax-b=0, \ f_0(x) \le t \;\; ( \lt p^* ) } です．これは {\displaystyle p^* } が主問題の最適値であることに矛盾します．したがって以下が成り立ちます．

(2.2.5){\displaystyle \;\;\; \mathcal{A} \cap \mathcal{B} = \emptyset }


分離超平面定理(separating hyperplane theorem)(文献[4]にあります)より，以下をみたす {\displaystyle (\tilde{\lambda},\tilde{\nu},\mu) \neq 0, \ \alpha } が存在します．

(2.2.6){\displaystyle \;\;\; (u,v,t) \in \mathcal{A} \ \Rightarrow \ \tilde{\lambda}^T u + \tilde{\nu}^T v + \mu t \ge \alpha }

(2.2.7){\displaystyle \;\;\; (u,v,t) \in \mathcal{B} \ \Rightarrow \ \tilde{\lambda}^T u + \tilde{\nu}^T v + \mu t \le \alpha }

ここで(2.2.6)より {\displaystyle \;\;\; \tilde{\lambda} \succeq 0, \ \mu \ge 0 } を得ます．(そうでないと {\displaystyle \tilde{\lambda}^T u + \mu t } は {\displaystyle \mathcal{A} } 上でいくらでも小さくなってしまう)(2.2.7)は単に {\displaystyle \mu t \le \alpha, \forall t \lt p^* } なので {\displaystyle \mu p^* \lt \alpha } したがって {\displaystyle \mu p^* \le \alpha } を得ます．これらをあわせて以下を得ます．

(2.2.8){\displaystyle \;\;\; \sum_{i=1}^m \tilde{\lambda}_i f_i(x) + \tilde{\nu}^T (Ax-b) + \mu f_0(x) \ge \alpha \ge \mu p^*, \;\;\; x \in \mathcal{D}, \; \tilde{\lambda} \succeq 0, \ \mu \ge 0 }


{\displaystyle \mu \gt 0 } を仮定します．(2.2.8)より以下を得ます．

(2.2.9){\displaystyle \;\;\; \sum_{i=1}^m \left( \frac{\tilde{\lambda}_i}{\mu} \right) f_i(x) + \left( \frac{\tilde{\nu}}{\mu} \right)^T (Ax-b) + f_0(x) \ge p^*, \;\;\; x \in \mathcal{D}, \; \tilde{\lambda} \succeq 0, \ \mu \gt 0 }

{\displaystyle \;\;\;\;\;\; \Rightarrow \ \inf_{x \in \mathcal{D}} \left\{ \sum_{i=1}^m \left( \frac{\tilde{\lambda}_i}{\mu} \right) f_i(x) + \left( \frac{\tilde{\nu}}{\mu} \right)^T (Ax-b) + f_0(x) \right\} \ge p^*, \;\;\; \tilde{\lambda} \succeq 0, \ \mu \gt 0 }

{\displaystyle \;\;\;\;\;\; \Leftrightarrow \ g \left(\tilde{\lambda}/\mu,\tilde{\nu}/\mu \right) \ge p^*, \;\;\; \tilde{\lambda} \succeq 0, \ \mu \gt 0 }

これと弱双対性 {\displaystyle g(\lambda,\nu) \le p^* } より {\displaystyle g(\lambda,\nu) = p^* } です．したがって {\displaystyle \mu \gt 0 } のとき強双対性 {\displaystyle p^* = d^* \; ( \gt - \infty) } が成り立ちます．


{\displaystyle \mu = 0 } を仮定します．(2.2.8)より以下を得ます．

(2.2.10){\displaystyle \;\;\; \sum_{i=1}^m \tilde{\lambda}_i f_i(x) + \tilde{\nu}^T (Ax-b) \ge 0, \;\;\; x \in \mathcal{D}, \; \tilde{\lambda} \succeq 0, \ \mu = 0 }

{\displaystyle \;\;\;\;\;\; \Rightarrow \ \sum_{i=1}^m \tilde{\lambda}_i f_i( \tilde{x} ) \ge 0, \;\;\; \tilde{\lambda} \succeq 0, \ \mu = 0 \;\;\; \because } 事実.(再掲)(スレーターの条件)

{\displaystyle \;\;\;\;\;\; \Rightarrow \ \tilde{\lambda} = 0 \;\;\; \because f_i (\tilde{x}) \lt 0, \ i = 1,\ldots,m }

{\displaystyle (\tilde{\lambda},\tilde{\nu},\mu) \neq 0 } と {\displaystyle \tilde{\lambda} = 0, \ \mu=0 } より {\displaystyle \tilde{\nu} \neq 0 } です．(2.2.10)は以下となります．

(2.2.11){\displaystyle \;\;\; \tilde{\nu}^T (Ax-b) \ge 0, \;\;\; x \in \mathcal{D} }

ここで {\displaystyle \tilde{\nu}^T (A \tilde{x} -b) = 0 } であり事実.(再掲)と(2.2.1)より {\displaystyle \tilde{x} \in \mathrm{Int} \ \mathcal{D} } なので，(2.2.11)より {\displaystyle A^T \tilde{\nu}= 0 } でない限り {\displaystyle \exists x \in \mathcal{D} , \ \tilde{\nu}^T (A x -b) \lt 0 } が成り立ちます．したがって {\displaystyle A^T \tilde{\nu}= 0, \ \tilde{\nu} \neq 0 } でなければなりませんがこれは {\displaystyle A^T } が列フルランクであることすなわち(2.2.2)に矛盾します．したがって {\displaystyle \mu \neq 0 } であり，分離超平面は垂直にはなりません．


ここまでの強双対性の証明の幾何的解釈を，不等式制約一つのみのときの簡単な問題について以下に示します．

'--------------------------------------------------------------------------------------------------------------------------------------------
Figure 5.5 の解釈のメモ

・{\displaystyle \lambda \succeq 0 } なので支持超平面(直線)は右下がり(あるいは水平)
・{\displaystyle \mathcal{A} } (と {\displaystyle \mathcal{B} }) は凸集合
・{\displaystyle \mathcal{A} } と {\displaystyle \mathcal{B} } を分離する超平面は 点 {\displaystyle (0,p^*) } での {\displaystyle \mathcal{A} } の支持超平面
・スレーターの条件は支持超平面を垂直でないものにする(すなわち法線ベクトルを {\displaystyle (\lambda^*,1) } にする)という意味がある

'--------------------------------------------------------------------------------------------------------------------------------------------

=================================================================================

以上，弱双対性の幾何的な解釈と，凸最適化問題における強双対性とスレーターの条件の幾何的な解釈をまとめました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Supporting hyperplane のページ https://en.wikipedia.org/wiki/Supporting_hyperplane
[3] Wikipedia Boundary (topology) のページ https://en.wikipedia.org/wiki/Boundary_(topology)
[4] Wikipedia Hyperplane separation theorem のページ https://en.wikipedia.org/wiki/Hyperplane_separation_theorem