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$

1 Answer 1

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$
14
  • $\begingroup$ In your answer, who is $\mathcal{M}^{+}$? $\endgroup$
    – user70004
    Jul 16, 2017 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$ Jul 18, 2017 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, 2017 at 21:32
  • $\begingroup$ @DiegoFonseca Sorry I missed your comment see my comment below. $\endgroup$
    – Henry.L
    Jul 18, 2017 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, 2017 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.