はじめに
計測・制御・情報の最適化問題は、多くが式(1)のような凸最適化問題に帰着します。
\begin{eqnarray}
\min_x & &f(x) \\
\text{s.t.} & &g(x)=0\\
& &r(x)\leq 0
\end{eqnarray}
\tag{1}
本記事では、この凸最適化問題のラグランジュ双対問題の強双対性について説明します。
- ラグランジュ双対問題の強双対性について1/2では、分離定理と弱双対性を説明する。
- ラグランジュ双対問題の強双対性について2/2では、強双対性を説明する。
ラグラジアン$L(x,\lambda,\nu)$を導入します。
L(x,\lambda,\nu) = f(x)+\sum_{i=1}^{l}\lambda_i h_i(x) + \sum_{j=1}^{m}\nu_j r_j(x)
ラグランジュ双対関数$g(\lambda,\nu)$を導入します。
g(\lambda,\nu) = \inf_{x} L(x,\lambda,\nu)
このとき、ラグランジュ双対問題は下式で与えられます。
\begin{eqnarray}
\max_{\lambda,\nu} & &g(\lambda,\nu) \\
\text{s.t.} & &\lambda\geq 0
\end{eqnarray}
\tag{2}
ラグランジュ双対問題？という方は、下記事でコトバを紹介しています。
ラグランジュ双対問題の強双対性について直感的にわからないんだよなぁという方は、下記事でイラストを用いて説明しています。
分離定理
定理1
$C$と$D$を$\mathbb{R}^n$の空でない凸集合とし、$C\cap D=\phi$とする。
このとき、ある$a\in\mathbb{R}^n (a\neq 0)$と$b\in\mathbb{R}$があり、
$x\in C$ならば$a^Tx-b\leq 0$、$x\in D$ならば$a^Tx-b\geq 0$となる。
証明
集合$A$を導入する。
A = \lbrace c-d\in\mathbb{R}^n|c\in C, \ d\in D\rbrace
$a_1,a_2\in A$とすると、$\lambda\in [0,1]$において、
\begin{eqnarray}
\lambda a_1 + (1-\lambda)a_2
&=&\lambda( c_1-d_1)+(1-\lambda)( c_2-d_2)\\
&=&\lbrace\lambda c_1 + (1-\lambda)c_2\rbrace - \lbrace\lambda d_1 + (1-\lambda)d_2\rbrace\\
&\in& A\ \left( \because \lambda c_1 + (1-\lambda)c_2 \in C, \lambda d_1 + (1-\lambda)d_2\in D\right)
\end{eqnarray}
よって、$A$は凸集合である。
step1 $0\notin \text{cl}A$
$0\notin \text{cl}A$とする。このとき、ある正の最小距離$r$が存在して、$\lVert c-d\rVert =r>0$となるように、$c\in C$と$d\in D$をとる。
r=\text{dist}(C,D) = \text{inf}\lbrace\lVert c-d\rVert \ | \ c\in C, d\in D\rbrace
関数$h$を導入する。
h(x) = (d-c)^T\left(x-\dfrac{d+c}{2}\right)
このとき、集合$C$と$D$は、
C\subset \lbrace x\in\mathbb{R}^n|h(x)\leq 0\rbrace
D\subset \lbrace x\in\mathbb{R}^n|h(x)\geq 0\rbrace
$D$が成り立つことを、背理法を用いて証明する。
D\subset \lbrace x\in\mathbb{R}^n|h(x)< 0\rbrace
$h(u)<0$となる$u\in D$を仮定する。
h(u) = (d-c)^T\left(u-\dfrac{d+c}{2}\right)<0
(d-c)^T(u-d)<-\dfrac{1}{2}\lVert d-c\rVert^2<0
$u,d \in D$であるので、$\lambda u +(1-\lambda)d\in \text{cl}D$である。
$\lambda u +(1-\lambda)d$と$c$との距離を$\varphi(\lambda)$とおく。
\varphi(\lambda) = \lVert \lambda u +(1-\lambda)d -c\rVert^2
\dfrac{\varphi(\lambda)}{d\lambda}|_{\lambda=0} = 2(d-c)^T(u-d) < 0
ここで、$\lVert \lambda u +(1-\lambda)d -c\rVert^2<\lVert c-d\rVert=r$が成り立ち、最小距離$r$の定義と矛盾する。よって、$D$が成り立つ。
$C$が成り立つことを、背理法を用いて証明する。
C\subset \lbrace x\in\mathbb{R}^n|h(x)> 0\rbrace
$h(u)>0$となる$u\in C$を仮定する。
h(u) = (d-c)^T\left(u-\dfrac{d+c}{2}\right)>0
(d-c)^T(u-c)>\dfrac{1}{2}\lVert d-c\rVert^2>0
$u,c \in C$であるので、$\lambda u +(1-\lambda)c\in \text{cl}C$である。
$\lambda u +(1-\lambda)c$と$d$との距離を$\varphi(\lambda)$とおく。
\varphi(\lambda) = \lVert \lambda u +(1-\lambda)c -d\rVert^2
\dfrac{\varphi(\lambda)}{d\lambda}|_{\lambda=0} = 2(c-d)^T(u-c) < 0
ここで、$\lambda\rightarrow 0$としても、$\lVert \lambda u +(1-\lambda)d -c\rVert^2<\lVert c-d\rVert=r$が成り立ち、最小距離$r$の定義と矛盾する。よって、$C$が成り立つ。
step2 $0\in \text{cl}A$
$z_k\notin A$かつ$z_k\rightarrow0\in \text{cl} Aとなるような$点列$\lbrace z_k\rbrace_{k=1}^{\infty}$がとれる。
step1より、
a_k^Tx+b_k \leq 0 \ \ (\forall x\in A)
a_k^Tz_k+b_k \geq 0
とできる。両辺を差分することで、
a_k^T(z_k-x) \geq 0
$k\rightarrow\infty$とすることで、
a^T(-x) \geq 0 \ \ (\forall x\in A)
a^Tx \leq a^Ty \ \ (\forall x\in C,\forall y\in D)
$b=\sup_{x\in C}a^Tx$とおけば、
a^Tx-b \leq a^Ty-b \ \ (\forall x\in C,\forall y\in D)
\sup_{x\in C} a^Tx-b \leq \sup_{x\in C} a^Ty-b \ \ (\forall x\in C,\forall y\in D)
b-b \leq a^Ty-b \ \ (\forall x\in C,\forall y\in D)
0 \leq a^Ty-b \ \ (\forall y\in D)
$b=\sup_{x\in D}a^Tx$とおけば、
a^Tx-b \leq a^Ty-b \leq 0 \ \ (\forall x\in C,\forall y\in D)
a^Tx-b\leq 0 \ \ (\forall x\in C)
主張を得た。
弱双対性
定理2
主問題の最適値$p^\ast$、双対問題の最適値$d^\ast$とする。
このとき、$d^\ast\leq p^\ast$である。
証明
\begin{eqnarray}
g(\lambda,\nu)
&=& \inf_{x} L(x,\lambda,\nu)\\
&=& \inf_{x} \lbrace f(x)+\sum_{i=1}^{l}\lambda_i h_i(x) + \sum_{j=1}^{m}\nu_j r_j(x)\rbrace\\
&\leq& \inf_{x} f(x) \ \ \left(\because \sum_{i=1}^{l}\lambda_i h_i(x) \leq 0 , \ \sum_{j=1}^{m}\nu_j r_j(x)=0\right)\\
&=&p^\ast
\end{eqnarray}
よって、$d^\ast\leq p^\ast$である。
参考文献
- カーネル法入門、福水健次、朝倉書店
- 凸解析と最適化理論、田中謙輔、牧野書店
- 非線形最適化の基礎、福島雅夫、朝倉書店
- Convex Optimization、S. Boyd、L. Vandenberghe、CAMBRIDGE UNIVERSITY PRRESS