はじめに
前回、ラグランジュ双対問題の強双対性について1/2では、分離定理と弱双対性を説明しました。本記事では、ラグランジュ双対問題の強双対性について説明します。
強双対性
定義(Slater条件)
相対的内点があるとする。つまり、$\tilde{x}\in\text{relint}\mathcal{D}$があるとする、h_i(\tilde{x})<0 \ \ (1\leq i \leq l)r_j(\tilde{x})=a_j^T\tilde{x}+b_j=0 \ \ (1\leq j \leq m)
定理3
主問題が凸最適化問題であり、Slater条件を満たすとする。
このとき、ある$\lambda^\ast\geq0$と$\nu^\ast\in\mathbb{R}^m$があり、g(\lambda^\ast,\nu^\ast)=d^\ast=p^\astが成り立つ。
証明
$\mathbb{R}^l\times\mathbb{R}^m\times\mathbb{R}$の部分集合$\mathcal{A}$を導入する。
\mathcal{A}
=\lbrace (u,v,t)\in\mathbb{R}^l\times\mathbb{R}^m\times\mathbb{R}|
x\in\mathcal{D}, \
u_i\geq h_i(x), \
v_j=r_j(x), \
t\geq f(x)\rbrace
主問題の最適値は、
p^\ast = \inf\lbrace t \in\mathbb{R}|(0,0,t)\in\mathcal{A}\rbrace
を満たす。
Slater条件より$p^\ast<\infty$である。
$p^\ast=-\infty$のとき、弱双対性より$p^\ast=d^\ast=-\infty$であるので、$p^\ast$が有限値の場合を考える。
$\mathbb{R}^l\times\mathbb{R}^m\times\mathbb{R}$の凸集合$\mathcal{B}$を導入する。
\mathcal{B} = \lbrace(0,0,s)\in\mathbb{R}^l\times\mathbb{R}^m\times\mathbb{R}| s<p^\ast\rbrace
$\mathcal{A}\cap \mathcal{B}=\phi$であるので、分離定理が適用できる。
\begin{eqnarray}
(u,v,t)&\in \mathcal{A} \implies \lambda^Tu + \nu^Tv+\mu t\geq \alpha\\
(u,v,t)&\in \mathcal{B} \implies \lambda^Tu + \nu^Tv+\mu t\leq \alpha
\end{eqnarray}
$\mathcal{A}$の$u$と$t$は、いくらでも大きくできるが、下から$\alpha$で抑えているので、$\lambda\geq 0$と$\mu\geq 0$という条件が必要である。
$(u,v,t)\in \mathcal{B}$とすると、$t<p^\ast$である。
$\mu\geq 0$より、$\mu p^\ast>\mu t$である。
\begin{eqnarray}
&\lambda^Tu + \nu^Tv+\mu t\leq \alpha\\
&\mu t\leq \alpha \ \ (\because 簡略化)\\
&\mu p^\ast\leq \alpha \ \ (\because t\rightarrow p^\ast)
\end{eqnarray}
よって、
\sum_{i=1}^{l}\lambda_{i}h_{i}(x)+\sum_{j=1}^{m}\nu_{j}r_{j}(x)+\mu f(x)\geq
\mu p^\ast
$\mu\neq 0$のとき、
\sum_{i=1}^{l}\dfrac{\lambda_{i}}{\mu}h_{i}(x)+\sum_{j=1}^{m}\dfrac{\nu_{j}}{\mu}r_{j}(x)+ f(x)\geq
p^\ast
弱双対性より、
p^\ast
\geq
g(\lambda^\ast,\nu^\ast)
=
\sum_{i=1}^{l}\dfrac{\lambda_{i}}{\mu}h_{i}(x)+\sum_{j=1}^{m}\dfrac{\nu_{j}}{\mu}r_{j}(x)+ f(x)\geq
p^\ast
よって、強双対性をえる。
g(\lambda^\ast,\nu^\ast)=d^\ast=p^\ast
$\mu= 0$のとき、
\sum_{i=1}^{l}\lambda_{i}h_{i}(x)+\sum_{j=1}^{m}\nu_{j}r_{j}(x)\geq
0
\tag{2}
Slater条件の$r_j(x) = 0$から
\sum_{i=1}^{l}\lambda_{i}h_{i}(x)\geq
0
Slater条件の$h_i(x)<0$と、$\lambda_i\geq0$であるので、$\lambda_i=0$となる。
よって、式(2)は、
\sum_{j=1}^{m}\nu_{j}r_{j}(x)=\nu^T(Ax+b)\geq0
Slater条件の$r_j(\tilde{x}) = 0$から、
\sum_{j=1}^{m}\nu_{j}r_{j}(\tilde{x})=\nu^T(A\tilde{x}+b)=0
もし、$\nu^TA\neq 0$であるならば、$x^\prime\in B(\tilde{x},\varepsilon)$において、$\nu^T(Ax^\prime+b)$が正負をとりうるため、Slater条件を満たさなくなる。
よって、$\nu^TA= 0$でなければならない。さらに、$A$は逆行列をとれるため、$\nu = 0$をえる。
しかし、分離定理より、$(\lambda,\nu,\mu)\neq0$であるので矛盾する。
よって、$\mu\neq 0$である。
参考文献
- カーネル法入門、福水健次、朝倉書店
- 凸解析と最適化理論、田中謙輔、牧野書店
- 非線形最適化の基礎、福島雅夫、朝倉書店
- Convex Optimization、S. Boyd、L. Vandenberghe、CAMBRIDGE UNIVERSITY PRRESS