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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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)$

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.