Kullback-Leiblerダイバージェンスに基づく不確実性集合
$$ \mathcal{Q}(\epsilon) = \{ q\in \mathbb{R^n} : 1^Tq=1, q\geq0, \sum_{i=1}^nq_i\ln\dfrac{q_i}{p_i}\leq\epsilon \} $$
$$ \max_{\mathbb{Q}\in\mathcal{Q}}\mathbb{E}_{\mathbb{Q}}[f] = \left| \begin{aligned} \max_{q} \quad & f^Tq\\ \textrm{s.t.} \quad & \sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}\leq\epsilon\\ & 1^Tq=1 \\ & q_i>0, i=1,2,\cdots,n \end{aligned} \right. $$
は以下のように簡約化される。
$$ \max_{\mathbb{Q}\in\mathcal{Q}}\mathbb{E}_{\mathbb{Q}}[f] = \min_{\lambda>0,\eta} \{ \epsilon\lambda+\eta +\lambda\sum_{i=1}^{n}p_i\exp\left(\dfrac{f_i-\eta}{\lambda}-1\right) \} $$
$$ \left| \begin{aligned} \max_{q} \quad & f^Tq\\ \textrm{s.t.} \quad & \sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}\leq\epsilon\\ & 1^Tq=1 \\ & q_i>0, i=1,2,\cdots,n \end{aligned} \right. $$
主問題の標準形式に書き直すと
$$ \left| \begin{aligned} \min_{q} \quad & -f^Tq\\ \textrm{s.t.} \quad & \sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}-\epsilon\leq 0\\ & 1^Tq-1=0 \\ & q_i>0, i=1,2,\cdots,n \end{aligned} \right.\tag{1} $$
式(1)に対するLagrange関数は
$$ L(q,\lambda,\eta) = -f^Tq +\lambda\left(\sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}-\epsilon\right) +\eta\left(1^Tq-1\right) \tag{2} $$
である。ただし、双対変数を$(\lambda,\eta)$としている。$\lambda$は不等式制約に対応し、$\lambda\geq0$である。$\eta$は等式制約に対応する。
双対問題は
$$
\max_{\lambda\geq0,\eta}\min_{q}L(q,\lambda,\eta)
\tag{3}
$$
と定義される。
$\min_{q}L(q,\lambda,\eta)$は$q$に関する無制約最小化であるから、
$$ \dfrac{\partial L(q,\lambda,\eta)}{\partial q}=0 $$
以下細かい計算をしていく。
$$
\begin{aligned}
\dfrac{\partial L(q,\lambda,\eta)}{\partial q}
&=\dfrac{\partial}{\partial q}\left(-f^Tq
+\lambda\left(\sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}-\epsilon\right)
+\eta\left(1^Tq-1\right)\right)\\
&=-f
+\lambda
\left(
\begin{array}{c}
\vdots \\
\ln\dfrac{q_i}{p_i}+1\\
\vdots
\end{array}
\right)
+\eta\\
&=0
\end{aligned}
$$
よって、
$$
-f_i+\lambda\left(\ln\dfrac{q_i}{p_i}+1\right)+\eta=0
$$
式変形すると、
$$
\ln\dfrac{q_i}{p_i}+1=\dfrac{f_i-\eta}{\lambda}
$$
よって、
$$
\ln\dfrac{q_i}{p_i}=\dfrac{f_i-\eta}{\lambda}-1
\tag{4}
$$
$$ q_i=p_i\exp\left(\dfrac{f_i-\eta}{\lambda}-1\right) \tag{5} $$
$$ \lambda\neq0 \tag{6} $$
式(2)Lagrange関数を式(3)の双対問題に代入すれば、
$$ \begin{aligned} \max_{\lambda\geq0,\eta}\min_{q}L(q,\lambda,\eta) &= \max_{\lambda\geq0,\eta}\min_{q} -f^Tq +\lambda\left(\sum_{i=1}^{n}q_i\ln\dfrac{q_i}{p_i}-\epsilon\right) +\eta\left(1^Tq-1\right)\\ &= \max_{\lambda\geq0,\eta}\min_{q} \left(\cdots,-f_i+\lambda\ln\dfrac{q_i}{p_i}+\eta,\cdots\right)q -\epsilon\lambda-\eta\\ &= \max_{\lambda\geq0,\eta} -\lambda \sum_{i=1}^np_i\exp\left(\dfrac{f_i-\eta}{\lambda}-1\right) -\epsilon\lambda-\eta \ \ (\because 式(4)、式(5))\\ &= \min_{\lambda\geq0,\eta} \epsilon\lambda+\eta +\lambda \sum_{i=1}^np_i\exp\left(\dfrac{f_i-\eta}{\lambda}-1\right)\\ &= \min_{\lambda>0,\eta} \epsilon\lambda+\eta +\lambda \sum_{i=1}^np_i\exp\left(\dfrac{f_i-\eta}{\lambda}-1\right) \ \ (\because 式(6)) \end{aligned} $$
