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

Wasserstein距離に基づく分布的ロバスト最適化の凸最適化問題への帰着

1861
0
$$$$

1. はじめに

この記事は、文献[2]の式変形の備忘録として残したものです。式番号は論文にあわせておりますのでご注意ください。

ルベーグ積分、関数解析、凸解析および測度論的確率論を勉強しはじめた段階なので、間違った理解をしているところがあると思います。見つけた際は、間違いをご指摘頂ければ幸いです。

2. Wasserstein距離とは

Wasserstein距離は、輸送問題に着想を得た分布間の距離尺度のことである。連続型分布$\mathbb{Q}:=\gamma(・)$と、離散型分布である経験分布$\mathbb{P}:=p$の間に限定して考える。

Wasserstein距離のイメージ図 Wasserstein距離のイメージ図

図1のように、$\mathbb{P}$から$\mathbb{Q}$へと確率を移動する輸送問題を考え、単位輸送費用が$\|z-Y_i\|_p$で与えられた場合の最小費用がダイバージェンス$d(\mathbb{Q}|\mathbb{P})$を与える。

3. 分布的ロバスト最適化とは

事前には認知が難しい事後での不整合に対し、最悪ケースのずれがあったとしても最適解の実行可能性やある種の最適性を担保しようとする最適化モデリングをロバスト最適化という。

ロバスト最適化の比較を図に示す。

ロバスト最適化の比較 ロバスト最適化の比較

ロバスト最適化の中でも想定する確率分布の不確実性を考慮したものを分布的ロバスト最適化という。

分布的ロバスト最適化は、経験分布$\hat{\mathbb{P}}_N$の不確実性を集合で表し、その集合の中で最悪ケースの期待コストの最小化を目指す。

$$ \inf_{x}\sup_{\mathbb{Q}\in\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)} \mathbb{E}^{\mathbb{Q}}[l(\xi)] $$

不確実性集合$\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)$は、下式で与えられる。

$$ \mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N) := \{\mathbb{Q}\in\mathcal{M}(\Xi): d_{W}(\hat{\mathbb{P}}_N,\mathbb{Q})\leq\epsilon\}. \tag{6} $$

経験分布$\hat{\mathbb{P}}_N$を中心とした半径$\epsilon$のWasserstein球とみることができる。

4. 最悪ケースの期待コスト問題の凸最適化問題への帰着

式(10)の最悪ケースの期待コスト問題が凸最適化問題に帰着することができることをみていく。

$$ \sup_{\mathbb{Q}\in\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)} \mathbb{E}^{\mathbb{Q}}[l(\xi)] \tag{10} $$

仮定4.1 (Convexity)

不確実性集合$\Xi\subset\mathbb{R}^m$は凸で閉であるとする。
$l_k$はproperであり、凸であり、下半連続であるとする。
さらに、$l_k$$-\infty$ではないとする。

Convex reduction

仮説4.1において、任意の$\epsilon\geq 0$において、式(10)の最悪ケースの期待コスト問題は式(11)の凸最適化問題の最適値に等しい。

$$ \left| \begin{aligned} \inf_{\lambda,s_i,z_{ik},v_{ik}} \quad & \lambda\epsilon + \dfrac{1}{N}\sum_{i=1}^N s_i\\ \textrm{s.t.} \quad & \left[-l_k\right]^*(z_{ik}-v_{ik})+\sigma_{\Xi}(v_{ik})-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i\\ & \|z_{ik}\|_*\leq \lambda \\ \end{aligned} \right. \tag{11} $$

ここで、$\|z_{ik}\|_*$$z_{ik}$の双対ノルムである。

4.1 定理1で使う道具の紹介

この節では、定理1の証明に入る前に、証明でつかう定義や補題を紹介する。
関数解析、凸解析および測度論的確率論はまだ勉強しはじめたばかりなので間違いがあればご指摘ください。

$$ \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) =\dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi\in\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) $$

まず、以下の不等式の証明をする。

$$ \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \geq\dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi\in\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) $$

$$ \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \\ = \sup \Biggl\{\dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \mid \mathbb{Q}_i\in\mathcal{M}(\Xi) \ \ \mathrm{for} \ i =1 ,2,\cdots , N \Biggr\} \\ = \dfrac{1}{N}\sum_{i=1}^{N} \sup \Biggl\{ \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \mid \mathbb{Q}_i\in\mathcal{M}(\Xi) \Biggr\} \\ \geq \dfrac{1}{N}\sum_{i=1}^{N} \sup \Biggl\{ \int_{\Xi} \left( l(\zeta)-\lambda\|\zeta-\hat{\xi}_i\| \right) \delta_\xi(d\zeta) \mid \xi\in\Xi \Biggr\} \\ =\dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi\in\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) $$

次に以下の不等式を証明する。

$$ \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \leq \dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi\in\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) $$

$$ \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \\ \leq \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \int_{\Xi} \sup_{\xi^{\prime}\in\Xi} \left( l(\xi^{\prime})-\lambda\|\xi^{\prime}-\hat{\xi}_i\| \right) \mathbb{Q}_i(d\xi) \\ = \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi^{\prime}\in\Xi} \left( l(\xi^{\prime})-\lambda\|\xi^{\prime}-\hat{\xi}_i\| \right) \int_{\Xi} \mathbb{Q}_i(d\xi) \\ = \dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi^{\prime}\in\Xi} \left( l(\xi^{\prime})-\lambda\|\xi^{\prime}-\hat{\xi}_i\| \right) \sup_{\mathbb{Q}_i\in\mathcal{M}(\Xi)} \int_{\Xi} \mathbb{Q}_i(d\xi) \\ = \dfrac{1}{N}\sum_{i=1}^{N} \sup_{\xi^{\prime}\in\Xi} \left( l(\xi)-\lambda\|\xi-\hat{\xi}_i\| \right) $$

よって、等号が成立する。

双対ノルム

xのノルム$\|x\|$の双対ノルムを以下で定義する。

$$ \|x\|_* :=\max_{\|y\|\leq1}\langle y,x\rangle $$

$l^p$の共役空間はノルム空間$l^q$に等しい距離同型である。
ただし、$1< p<\infty$で、$q$$p$の共役指数、すなわち、
$$ \dfrac{1}{p}+\dfrac{1}{q}=1 $$
を満たすものである。

$f$がノルム空間$l^p$上の有界な線形汎関数であるための必要十分条件は、$a\in l^q$が存在して、
$$ f(x) = \langle x,a \rangle $$
が成り立つことである。

しかも、$\|f\|=\|a\|_q$が成り立つことである。

簡単に書くと
$$ \|x\|_{p*} = \max_{\|y\|_p\leq1}\langle y,x\rangle = \|x\|_q $$

共役関数

$H$をHilbert空間とし、関数$f:H\rightarrow (-\infty,\infty]$を真であるとする。このとき、$H$上の$f^*$

$$ f^*(x^*)=\sup_{x\in H}\{\langle x,x^*\rangle-f(x)\} $$

で定義する。$f^*$$f$の共役関数といわれる。

epi-sum, inf-convolution

$E$を線形空間とし、$f,g:E\rightarrow (-\infty,\infty]$をsublinearとする。

$$ (f \boxplus g)(x)=\inf_{x\in E}\{f(x)+g(x-z)\}, \ \forall x \in E $$

で定義される$(f \boxplus g)$$f$$g$によるepi-sumまたはinf-convolutionという。

$E$を線形区間とし、$f,g:E\rightarrow (-\infty,\infty]$をproperな凸関数とする。また、

$$ (f \boxplus g)(x)=\inf_{x\in E}\{f(x)+g(x-z)\}>-\infty, \ \forall x \in E $$

とする。

このとき、$(f\boxplus g)(x):E\rightarrow(-\infty,\infty]$
はproperな凸関数となる。さらに、$(f\boxplus g)^*=f^*+g^*$である。

凸解析と不動点近似のp156 定理4.4.2を参照してください。

$\sigma_{\Xi}(v_{ik}):=[\chi_{\Xi}]^*(v_{ik})$とおく。

$$ \begin{aligned} \lbrack-l_k+\chi_{\Xi}\rbrack^{*}(z_{ik}) &= \inf_{v_{ik}} \left( [-l_k]^*(z_{ik}-v_{ik})+[\chi_{\Xi}]^*(v_{ik}) \right)\\ &= \inf_{v_{ik}} \left( [-l_k]^*(z_{ik}-v_{ik})+\sigma_{\Xi}(v_{ik}) \right) \end{aligned} $$

$$ \left( \inf_{v_{ik}} \left( [-l_k]^*(z_{ik}-v_{ik})+[\chi_{\Xi}]^*(v_{ik}) \right) \right)^*\\ = \left( [\chi^*_{\Xi}\boxplus(-l^*_k)](z_{ik}) \right)^*\\ = \left(\chi^*_{\Xi}(z_{ik})\right)^*+\left(-l^*_k(z_{ik})\right)^*\\ = \chi^{**}_{\Xi}(z_{ik})-l_k^{**}(z_{ik})\\ = \chi_{\Xi}(z_{ik})-l_k(z_{ik})\\ = -l_k(z_{ik})+\chi_{\Xi}(z_{ik})\\ = (-l_k+\chi_{\Xi})(z_{ik}) (ここの行は正しいかわからないです、ごめんなさい) $$

4.2 定理1の証明

$$ \begin{aligned} \sup_{\mathbb{Q}\in\mathbb{B}_{\epsilon}(\hat{\mathbb{P}}_N)} \mathbb{E}^{\mathbb{Q}}[l(\xi)] &= \left| \begin{aligned} \sup_{\mathbb{Q_i}\in\mathcal{M}(\Xi)} \quad & \dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}l(\xi)\mathbb{Q}_i(d\xi)\\ \textrm{s.t.} \quad & \dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}\|\xi-\hat{\xi}_{i}\|\mathbb{Q}_i(d\xi)\leq\epsilon\\ \end{aligned} \right.\\ &= \sup_{\mathbb{Q_i}\in\mathcal{M}(\Xi)} \inf_{\lambda\geq 0} \dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}l(\xi)\mathbb{Q}_i(d\xi) + \lambda\left(\epsilon-\dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}\|\xi-\hat{\xi}_{i}\|\mathbb{Q}_i(d\xi)\right) \\ &\leq \inf_{\lambda\geq 0} \sup_{\mathbb{Q_i}\in\mathcal{M}(\Xi)} \dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}l(\xi)\mathbb{Q}_i(d\xi) + \lambda\left(\epsilon-\dfrac{1}{N}\sum_{i=1}^N\int_{\Xi}\|\xi-\hat{\xi}_{i}\|\mathbb{Q}_i(d\xi)\right) \ \ (12a) \\ &= \inf_{\lambda\geq 0} \sup_{\mathbb{Q_i}\in\mathcal{M}(\Xi)} \lambda\epsilon +\dfrac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\left(l(\xi)-\lambda\|\xi-\hat{\xi}_{i}\|\right)\mathbb{Q}_i(d\xi) \\ &= \inf_{\lambda\geq 0} \lambda\epsilon +\dfrac{1}{N}\sum_{i=1}^{N}\sup_{\xi\in\Xi}\left(l(\xi)-\lambda\|\xi-\hat{\xi}_{i}\|\right) \ \ (\because 補題2) \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l(\xi)-\lambda\|\xi-\hat{\xi}_{i}\|\right)\leq s_i, \forall i\leq N\\ & \lambda \geq 0\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l_k(\xi)-\max_{\|z_{ik}\|_*\leq\lambda}\langle z_{ik},\xi-\hat{\xi}_i\rangle\right)\leq s_i, \forall i\leq N,\forall k\leq K\\ & \lambda \geq 0\\ \end{aligned} \right. \\ &\leq \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\min_{\|z_{ik}\|_*\leq\lambda}\sup_{\xi\in\Xi}\left(l_k(\xi)-\langle z_{ik},\xi-\hat{\xi}_i\rangle\right)\leq s_i, \forall i\leq N,\forall k\leq K\\ & \lambda \geq 0\\ \end{aligned} \ \ (12e) \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l_k(\xi)-\langle z_{ik},\xi-\hat{\xi}_i\rangle\right)\leq s_i, \forall i\leq N,\forall k\leq K\\ & \lambda \geq 0\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l_k(\xi)-\langle z_{ik},\xi-\hat{\xi}_i\rangle\right)\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l_k(\xi)-\langle z_{ik},\xi\rangle\right)+\langle z_{ik},\hat{\xi}_i\rangle\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(l_k(\xi)+\langle z_{ik},\xi\rangle\right)-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(\langle z_{ik},\xi\rangle-(-l_k(\xi))\right)-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &\sup_{\xi\in\Xi}\left(\langle z_{ik},\xi\rangle-(-l_k(\xi)+\chi_{\Xi}(\xi))\right)-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i} \quad & \lambda\epsilon+\dfrac{1}{N}\sum_{i=1}^{N}s_i\\ \textrm{s.t.} \quad &[-l_k+\chi_{\Xi}]^*(z_{ik})-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i, \forall i\leq N,\forall k\leq K\\ & \|z_{ik}\|_*\leq\lambda\\ \end{aligned} \right. \\ &= \left| \begin{aligned} \inf_{\lambda,s_i,z_{ik},v_{ik}} \quad & \lambda\epsilon + \dfrac{1}{N}\sum_{i=1}^N s_i\\ \textrm{s.t.} \quad & \left[-l_k\right]^*(z_{ik}-v_{ik})+\sigma_{\Xi}(v_{ik})-\langle z_{ik},\hat{\xi}_i\rangle\leq s_i\\ & \|z_{ik}\|_*\leq \lambda \\ \end{aligned} \right. \ \ (\because 補題4) \end{aligned} $$

仮定4.1のもとで、式(12a)と式(12e)の不等号が等号になることを示す。仮定4.1のもとで、式(12a)は強双対性より等号が成立する。仮定4.1のもとで、minimax定理より式(12e)は等号が成立する。

よって、仮説4.1において、任意の$\epsilon\geq 0$において、式(10)の最悪ケースの期待コスト問題は式(11)の凸最適化問題の最適値に等しい。

参考文献

[2]
P.M.Esfahani, D.Kuhn, Data-driven distributionally robust optimization using the Wasserstein metric:performance guarantees and tractable reformulations, Springer
[3]
R. Chen and I. C. Paschalidis, Distributionally Robust Learning
投稿日:2022830
OptHub AI Competition

この記事を高評価した人

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

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

バッジはありません。

投稿者

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

コメント

他の人のコメント

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