5
$\begingroup$

Reading the paper in this Link (see pag 13) with the objective of understanding a topic related to stochastic optimization I came across a problem in demonstrating one of the theorems. The situation is the following:

The context: Let $(\Xi,\mathcal{E})$ be a measurable space where $\Xi\subseteq \mathbb{R}^{m}$, $\widehat{\xi}_{i}\in \Xi$ for $i=1,\ldots,N$ and $\ell(\xi):=\max_{k\leq K}\ell_{k}(\xi)$ where $\ell_{k}:\Xi\rightarrow \mathbb{R}$ are functions. We denote by $\mathcal{M}(\Xi)$ the set of probability distributions supported on $\Xi$. We consider the infinite optimizatión program \begin{align} & \left\{\begin{array}{cl} {\displaystyle\sup_{\mathbb{Q}_{i}\in\mathcal{M}(\Xi)} }&{\displaystyle \frac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\ell(\xi)\mathbb{Q}_{i}(d\xi)} \\ \mbox{s.t.} & {\displaystyle \frac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\left\|\xi-\widehat{\xi}_{i}\right\|\mathbb{Q}_{i}(d\xi)\leq \varepsilon.} \end{array} \right. \tag{P} \end{align}

We know that the dual problem is

\begin{align} & \left\{\begin{array}{cl} {\displaystyle\inf_{\lambda} }&{\displaystyle \sup_{\mathbb{Q}_{i}\in\mathcal{M}(\Xi)}\left(\frac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\ell(\xi)\mathbb{Q}_{i}(d\xi) +\lambda \varepsilon -\lambda \frac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\left\|\xi-\widehat{\xi}_{i}\right\|\mathbb{Q}_{i}(d\xi) \right)} \\ \mbox{s.t.} & {\displaystyle \lambda \geq 0.} \end{array} \right. \tag{D} \end{align}

We denote $\mathrm{Val(P)}$ and $\mathrm{Val(D)}$ the optimals values of $\mathrm{(P)}$ and $\mathrm{(D)}$ respectively.

Assumption: The paper I am reading establishes the following assumption:

Assumption 1. [Convexity] The uncertainty set $\Xi\subseteq \mathbb{R}^{m}$ is convex and closed, and the negative constituent functions $-\ell_{k}$ are proper, convex and lower semicontinuous for all $k\leq K$. Moreover, se assume that $\ell_{k}$ is not identically $-\infty$ on $\Xi$ for all $k\leq K$.

The problem: If the convexity Assumption 1 holds, I need to show that we have strong duality, that is, I need to show that $\mathrm{Val(P)}=\mathrm{Val(D)}.$

Remark: According to the paper I am reading this is a consequence of a extended version of well-known strong duality result for moment problems, in this sense, the paper cite the following work:

A. Shapiro, On duality theory of conic linear problems, in Semi-Infinite Programming, M. A. Goberna and M. A. L´opez, eds., Kluwer Academic Publishers, 2001, pp. 135–165

In this work, in Proposition 3.4, they show strong duality for the optimization problem $$ \left\{\begin{array}{cl} \max_{\mu\in\mathcal{C}} & \left\langle \varphi, \mu \right\rangle \\ \mbox{s.t.} & \mathcal{A}\mu-b \in K \end{array} \right. \tag{1} $$ where the context of $\mathrm{(1)}$ is the following:

enter image description here enter image description here enter image description here enter image description here

Is (P) a particular case of (1)? If the answer is yes, then how can I make this evident?

$\endgroup$
2
$\begingroup$

Yes. $\mathcal{M}(\Xi)$ is the space of all probability measures defined on the measure space $\Xi$ with Levy distance and superscript means usual direct product of spaces.

${\displaystyle \frac{1}{N}\sum_{i=1}^{N}\int_{\Xi}\left\|\xi-\widehat{\xi}_{i}\right\|\mathbb{Q}_{i}(d\xi)\leq \varepsilon}$ can be rewritten as $\mathcal{A}(\mathbb Q)=\mathcal{A}(\mathbb{Q}_i)_{i=1,\cdots,N}=\frac{1}{N}\sum_{i=1}^N\mathcal{A}_{\hat\xi_i}\mathbb{Q}_{i}$ You can verify that $$\mathcal{A}_{\hat\xi_i}:\mathcal{M}(\Xi)^N\rightarrow \mathbb R, \mathbb{Q}\mapsto \int_{\Xi}\left\|\xi-\widehat{\xi}_{i}\right\|\mathbb{Q}_i(d\xi)$$ is linear in $\mathbb{Q}$ and the sum of linear operators is still linear.

So $\mathcal{A}:\mathcal{M}(\Xi)^N\rightarrow\mathbb R$ is a linear operator and the constraint is $\mathcal{A}(\mathbb{Q}_i)_{i=1,\cdots,N}-0\in \{r\in\mathbb{R} : 0\le r\le K\}$

Now the inner product is just the dual product $\langle\varphi,(\mathbb{Q})_{i=1,\cdots N}\rangle=\int_{\Xi}\varphi (d\mathbb{Q_1}+\cdots+d\mathbb{Q_N})$. Here $\varphi=(\varphi_1(\omega)\cdots\varphi_N(\omega))\in L(\Xi)$ the space of all integrable real functions defined on $\Xi$, but with the setting of (P), you are just choosing a special case that $\varphi(\omega)=(\varphi_1(\omega)\cdots\varphi_N(\omega))=(\frac{1}{N}l(\omega),\cdots,\frac{1}{N}l(\omega))$. In short the inner product is defined on $L(\Xi)\times \mathcal{M}(\Xi)^N=L(\Xi)\times \oplus_{i=1}^N \mathcal{M}(\Xi)$

$\endgroup$
  • $\begingroup$ In your answer, who is $\mathcal{M}^{+}$? $\endgroup$ – user70004 Jul 16 '17 at 21:19
  • $\begingroup$ @Henry.L I would also like to know an answer to Diego's question. The bonus is yours if you can specify your answer. $\endgroup$ – matematicaActiva Jul 18 '17 at 21:09
  • $\begingroup$ @matematicaActiva Sorry for the late reply, I obviously missed Diego's comment for some reason, $\mathcal{M}(\Theta)$ is the space of all probability measures endowed with Levy distance. $\endgroup$ – Henry.L Jul 18 '17 at 21:32
  • $\begingroup$ @DiegoFonseca Sorry I missed your comment see my comment below. $\endgroup$ – Henry.L Jul 18 '17 at 21:32
  • $\begingroup$ @Henry.L In the context of (1) we have the $\mathcal{A}:\mathcal{X}\rightarrow \mathbb{R}^{p}$. Of your answer I deduce that $\mathcal{X}=\mathcal{M}(\Xi)^{N}$, but this raises doubts me because in the context of (1) we have that $\mathcal{X}$ is the linear space of signed measures generates by $\mathcal{M}^{+}$. $\endgroup$ – user70004 Jul 18 '17 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.