Site cover image

Site icon imageNov’s AI Blog

プログラミングや数理最適化，深層学習の話題について紹介するブログ．スパース正則化の基礎研究と、ニューラルネットワークやテンソル分解への応用に取り組んでいます．
2022-10-23
ProofConvex Optimization

🥍強双対定理の証明

はじめに

強双対定理の証明を紹介します

「機械学習プロフェッショナルシリーズ 統計的学習理論」の付録Bに載っているものが元となっています

詳しくはそちらを参照ください

統計的学習理論
ていねいな説明が感動的！ しっかり、よくわかる！学習手法を使いこなすには、確率・統計に根ざした基礎理論が不可欠。「カーネル法」「サポートベクトルマシン」「ブースティング」などの重要概念の自然な導入を図
Favicon of the bookmark site
https://www.kspub.co.jp
Site image of the bookmark

主張

ラグランジュ関数 L(x,λ)=f(x)+∑j=1mλjhj(x)=f(x)+λTh(x)L(x, \lambda) = f(x) + \sum_{j = 1}^m \lambda_j h_j(x) = f(x) + \lambda^T h(x) において，∃x∈D,∀j∈{1,⋯ ,m},hj(x)<0\exists x\in D, \forall j \in \{1, \cdots, m\}, h_j(x) < 0 （スレイター制約想定）を満たすとき

max⁡λ≥0min⁡x∈RdL(x,λ)=min⁡x∈Rdmax⁡λ≥0L(x,λ)\displaystyle\max_{\lambda \geq 0}\min_{x \in \mathbb R^d} L(x, \lambda) = \min_{x \in \mathbb R^d}\max_{\lambda \geq 0} L(x,\lambda)

が成り立つ

以下，d∗d^* と p∗p^* を次で定義する

d∗:=max⁡λ≥0min⁡x∈RdL(x,λ),p∗:=min⁡x∈Rdmax⁡λ≥0L(x,λ)\displaystyle d^* := \max_{\lambda \geq 0}\min_{x \in \mathbb R^d} L(x, \lambda),\quad p^* := \min_{x \in \mathbb R^d}\max_{\lambda \geq 0} L(x,\lambda)

証明の前準備

以下の定理を導入した上で証明を行います

  1. 弱双対定理
  2. 凸集合の超平面分離定理

弱双対定理

主張

max⁡λ≥0min⁡x∈RdL(x,λ)≤min⁡x∈Rdmax⁡λ≥0L(x,λ)\displaystyle\max_{\lambda \geq 0}\min_{x \in \mathbb R^d} L(x, \lambda) \leq \min_{x \in \mathbb R^d}\max_{\lambda \geq 0} L(x,\lambda)

証明

🚫 Arrow icon of a page linkPost not found

凸集合の超平面分離定理

主張

S,T(≠∅)⊂Rd,S∩T=∅S, T (\neq \emptyset) \subset \mathbb R^d, S\cap T = \emptyset のとき

∃a(≠0)∈Rd,b(≠0)∈R s.t. {x∈S  ⟹  aTx≥bx∈T  ⟹  aTx≤b\exists a(\neq 0)\in \mathbb R^d, b(\neq 0) \in \mathbb R \text{ s.t. } \begin{cases} x\in S \implies a^Tx\geq b\\ x\in T \implies a^Tx\leq b \end{cases}

証明

TODO

証明

まず，集合 AA を

A={(u,t)∈Rd×R∣∃x∈Rd,u≥h(x)∧t≥f(x)}A = \{(u, t) \in \mathbb R^d \times \mathbb R \mid \exists x \in \mathbb R^d, u \geq h(x) \land t\geq f(x)\}

とおくと

p∗=min⁡{t∣(0,t)∈A}p^* = \min\{t\mid (0, t) \in A\}

が成り立つ

これは p∗p^* に対応する不等式制約付き最適化問題から分かる

min⁡x∈Rdf(x)s.t. hj(x)≤0, ∀j∈{1,⋯ ,m}\displaystyle\min_{x\in\mathbb R^d} f(x) \quad \text{s.t.}\ h_j(x) \leq 0 ,\ \forall j \in \{1,\cdots,m\}

スレイター制約想定より，p∗<∞p^* < \infty であり， p∗=−∞p^* = -\infty のとき 🚫 Arrow icon of a page linkPost not found より d∗=−∞d^* = -\infty で主張が成り立つから，以下では p∗∈Rp^* \in \mathbb R と仮定する

次に集合 BB を

B={(0,t′)∈Rd×R∣t′<p∗}B = \{(0,t') \in \mathbb R^d \times \mathbb R \mid t' < p^*\}

とすると A∩B=∅A \cap B = \emptyset である

ここで 🚫 Arrow icon of a page linkPost not found より

（Q. Aが凸集合であることの証明）

{(u,t)∈A  ⟹  aTu+a0t≥b(u′,t′)∈B  ⟹  aTu′+a0t′≤b\begin{cases} (u, t) \in A \implies a^Tu + a_0 t \geq b\\ (u', t') \in B \implies a^Tu' + a_0 t' \leq b \end{cases}

を満たす (a,a0)(≠0)∈Rd×R,b(≠0)∈R(a, a_0) (\neq 0) \in \mathbb R^d \times \mathbb R, b(\neq 0) \in \mathbb R が存在する

そのような (a,a0),b(a, a_0), b を選ぶと

∀(u,t)∈A,(u′,t′)∈Bs.t. aTu+a0t≥aTu′+a0t′=u′=0a0t′(1)\forall(u, t) \in A, (u', t') \in B \quad \text{s.t.}\ a^T u + a_0 t \geq a^T u' + a_0 t' \underset{u' = 0}{=} a_0 t' \quad(1)

が成り立つ

集合 AA の定義から (u,t)(u, t) は任意に大きい値を取るため (a,a0)≥0(a, a_0) \geq 0 でなければ (1)(1) が成り立たない

(1)(1) と p∗=sup⁡t′∈Bt′p^* = \sup_{t' \in B} t' より aTu+a0t≥a0p∗a^T u + a_0 t \geq a_0 p^* であり，(h(x),f(x))∈A(h(x), f(x)) \in A から

aTh(x)+a0f(x)≥a0p∗(2)a^Th(x) + a_0 f(x) \geq a_0 p^* \quad(2)

が成り立つ

また，a0=0a_0 = 0 のとき (2)(2) より ∀x∈Rd,aTh(x)≥0\forall x \in \mathbb R^d, a^Th(x) \geq 0 であるが スレイター制約想定 から a=0a = 0 が成り立ち (a,a0)≠0(a, a_0) \neq 0 と矛盾

ゆえに，a0>0a_0 > 0 であり (2)/a0  ⟺  aTa0h(x)+f(x)≥p∗\displaystyle (2) / a_0 \iff \frac{a^T}{a_0} h(x) + f(x) \geq p^* が成り立つ

したがって，min⁡x∈RdL(x,aa0)≥p∗\displaystyle \min_{x\in\mathbb R^d} L\left(x, \frac{a}{a_0}\right) \geq p^* となり， d∗≥min⁡x∈RdL(x,aa0)d^* \geq \displaystyle \min_{x\in\mathbb R^d} L\left(x, \frac{a}{a_0}\right) であるから d∗≥p∗d^* \geq p^* が成り立つ

これと 🚫 Arrow icon of a page linkPost not found を合わせて d∗=p∗d^* = p^* である

まとめ

以上が強双対定理の証明でした

AA が凸集合であることの証明は自明でないと思われますが、私の理解が及んでおらず、載せるに至っていないので割愛します

ProofConvex Optimization