Kullback-Leiblerダイバージェンスに基づく不確実性集合

$$|\begin{array}{rl}\underset{q}{max}& f^{T}q\\ \text{s.t.}& \sum _{i=1}^n{q}_i\ln {\displaystyle \frac{q_i}{p_i}}\le ϵ\\ & 1^{T}q=1\\ & q_i>0,i=1,2,\cdots ,n\end{array}$$

主問題の標準形式に書き直すと

$$\begin{array}{}\text{(1)}& |\begin{array}{rl}\underset{q}{min}& -f^{T}q\\ \text{s.t.}& \sum _{i=1}^n{q}_i\ln {\displaystyle \frac{q_i}{p_i}}-ϵ\le 0\\ & 1^{T}q-1=0\\ & q_i>0,i=1,2,\cdots ,n\end{array}\end{array}$$

式(1)に対するLagrange関数は

$$\begin{array}{}\text{(2)}& L(q,\lambda ,\eta )=-f^{T}q+\lambda (\sum _{i=1}^n{q}_i\ln {\displaystyle \frac{q_i}{p_i}}-ϵ)+\eta (1^{T}q-1)\end{array}$$

である。ただし、双対変数を$(\lambda ,\eta )$としている。$\lambda$は不等式制約に対応し、$\lambda \ge 0$である。$\eta$は等式制約に対応する。

双対問題は
$$\begin{array}{}\text{(3)}& \underset{\lambda \ge 0,\eta }{max}\underset{q}{min}L(q,\lambda ,\eta )\end{array}$$

と定義される。
$\underset{q}{min}L(q,\lambda ,\eta )$は$q$に関する無制約最小化であるから、

$${\displaystyle \frac{\partial L(q,\lambda ,\eta )}{\partial q}}=0$$

以下細かい計算をしていく。
$$\begin{array}{rl}{\displaystyle \frac{\partial L(q,\lambda ,\eta )}{\partial q}}& ={\displaystyle \frac{\partial }{\partial q}}(-f^{T}q+\lambda (\sum _{i=1}^n{q}_i\ln {\displaystyle \frac{q_i}{p_i}}-ϵ)+\eta (1^{T}q-1))\\ & =-f+\lambda \left(\begin{array}{c}⋮\\ \ln {\displaystyle \frac{q_i}{p_i}}+1\\ ⋮\end{array}\right)+\eta \\ & =0\end{array}$$

よって、
$$-f_i+\lambda (\ln {\displaystyle \frac{q_i}{p_i}}+1)+\eta =0$$

式変形すると、
$$\ln {\displaystyle \frac{q_i}{p_i}}+1={\displaystyle \frac{f_i-\eta }{\lambda }}$$

よって、
$$\begin{array}{}\text{(4)}& \ln {\displaystyle \frac{q_i}{p_i}}={\displaystyle \frac{f_i-\eta }{\lambda }}-1\end{array}$$

$$\begin{array}{}\text{(5)}& q_i=p_i\exp ({\displaystyle \frac{f_i-\eta }{\lambda }}-1)\end{array}$$

$$\begin{array}{}\text{(6)}& \lambda \ne 0\end{array}$$

式(2)Lagrange関数を式(3)の双対問題に代入すれば、

$$\begin{array}{rl}\underset{\lambda \ge 0,\eta }{max}\underset{q}{min}L(q,\lambda ,\eta )& =\underset{\lambda \ge 0,\eta }{max}\underset{q}{min}-f^{T}q+\lambda (\sum _{i=1}^n{q}_i\ln {\displaystyle \frac{q_i}{p_i}}-ϵ)+\eta (1^{T}q-1)\\ & =\underset{\lambda \ge 0,\eta }{max}\underset{q}{min}(\cdots ,-f_i+\lambda \ln {\displaystyle \frac{q_i}{p_i}}+\eta ,\cdots )q-ϵ\lambda -\eta \\ & =\underset{\lambda \ge 0,\eta }{max}-\lambda \sum _{i=1}^n{p}_i\exp ({\displaystyle \frac{f_i-\eta }{\lambda }}-1)-ϵ\lambda -\eta (\because 式(4)、式(5))\\ & =\underset{\lambda \ge 0,\eta }{min}ϵ\lambda +\eta +\lambda \sum _{i=1}^n{p}_i\exp ({\displaystyle \frac{f_i-\eta }{\lambda }}-1)\\ & =\underset{\lambda >0,\eta }{min}ϵ\lambda +\eta +\lambda \sum _{i=1}^n{p}_i\exp ({\displaystyle \frac{f_i-\eta }{\lambda }}-1)(\because 式(6))\end{array}$$