0
大学数学基礎解説
文献あり

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

131
0
$$$$
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} $$

参考文献

[1]
S.Boyd and L.Vandenberghe, Convex Optimization
投稿日:2022818

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

hdk105
hdk105
14
13652
計測・制御・情報に興味があります. 備忘録として残していきます.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中