# Duality problem of an infinite dimensional optimization problem

I am reading the paper "OPTIMAL INEQUALITIES IN PROBABILITY THEORY: A CONVEX OPTIMIZATION APPROACH" by BERTSIMAS and POPESCU. In the paper, the authors derived a duality problem for an infinite-dimensional optimization problem. I am not sure how to derive the following:

The primal is:

$$\max_\mu \quad \int_S \textbf{1}d\mu$$

subject to $$\int_\Omega \bar z^kd\mu=\sigma_\kappa$$, $$\forall \kappa\in J_k$$.

The dual is:

$$\min_{y\in \mathcal{R}^{|J_k|}} \quad \sum_{\kappa\in J_k}y_\kappa \sigma_\kappa$$

subject to $$g(\bar z)=\sum_{\kappa\in J_k}y_\kappa\bar z^\kappa\geq 1$$, $$\forall \bar z \in S$$, and $$g(\bar z)=\sum_{\kappa\in J_k}y_{\kappa}\bar z^\kappa\geq 0$$, $$\forall \bar z\in\Omega$$.

In the above, $$\mu$$ is a probability measure and $$S\subseteq \Omega\subseteq\mathcal{R}^n$$. Moreover, $$\bar z=(z_1,\ldots,z_n)'$$, $$\kappa=(k_1,\ldots,k_n)'$$, $$\bar z^\kappa=z_1^{k_1}\cdots z_n^{k_n}$$, and $$J_k=\{ \kappa=(k_1,\ldots,k_n)'|k_1+\cdots+k_n\leq k,~k_j\in\mathcal{Z}_+,~j=1,\ldots,n \}.$$ Could anyone tell me how to deal with this kind of infinite-dimensional optimization problem?

• Is the formulation "subject to $\int_\Omega \bar z^k d\mu = \sigma_\kappa, \kappa \in J_k$ correct? This would imply that $\int_\Omega \bar z^k d\mu$ has different values $\sigma_\kappa$, if $|J_k| > 1$.And what is $\bar z \in S$? A function? Not everyone has access to the paper. Please be more specific. – Dieter Kadelka Jun 30 '20 at 13:57
• @DieterKadelka Sorry for the confusion. I have added illustrations for the notation. – Eggplant Jul 7 '20 at 2:21

This is a special case (with $$f=1_S$$) of the duality $$s=i,\tag{1}$$ where $$s:=\sup\Big\{\int f\,d\mu\colon\mu\text{ is a measure, }\int g_j\,d\mu=c_j\ \;\forall j\in J\Big\},$$ $$i:=\inf\Big\{\sum b_j c_j\colon f\le\sum b_jg_j\Big\},$$ $$\int:=\int_\Omega$$, $$\sum:=\sum_{j\in J}$$, $$f$$ and the $$g_j$$'s are given measurable functions, the $$c_j$$'s are given real numbers, and $$J$$ is a finite set such that (say) $$0\in J$$, $$g_0=1$$, and $$c_0=1$$, so that the restriction $$\int g_0\,d\mu=c_0$$ means that $$\mu$$ is a probability measure.

In turn, (1) is a special case of the von Neumann-type minimax duality $$IS=SI,\tag{2}$$ where $$IS:=\inf_b\sup_\mu L(\mu,b),\quad SI:=\sup_\mu\inf_b L(\mu,b),$$ $$\inf_b$$ is the infimum over all $$b=(b_j)_{j\in J}\in\mathbb R^J$$, $$\sup_\mu$$ is the supremum over all probability measures $$\mu$$ over $$\Omega$$, and $$L$$ is the Lagrangian given by the formula $$L(\mu,b):=\int f\,d\mu-\sum b_j\Big(\int g_j\,d\mu-c_j\Big) =\int \Big(f-\sum b_j g_j\Big)\,d\mu+\sum b_j c_j.$$

Indeed, $$\inf_b L(\mu,b)=\int f\,d\mu$$ if $$\int g_j\,d\mu=c_j$$ for all $$j$$, and $$\inf_b L(\mu,b)=-\infty$$ otherwise. So, $$SI=s.\tag{3}$$

On the other hand, $$IS=i.\tag{4}$$ Indeed, \begin{align} IS&=\inf_b\Big\{\Big[\sup_\mu \int \Big(f-\sum b_j g_j\Big)\,d\mu\Big]+\sum b_j c_j\Big\} \\ &=\inf_b\Big\{\Big[\sup\Big(f-\sum b_j g_j\Big)\Big]+\sum b_j c_j\Big\}, \end{align} which is clearly no greater than $$i$$. On the other hand, if for some $$b$$ we have $$s_b:=\sup\big(f-\sum b_j g_j\big)\in\mathbb R$$, then $$f\le\sum \tilde b_jg_j$$ and $$\sum\tilde b_jc_j=s_b+\sum b_jc_j=\Big[\sup\Big(f-\sum b_j g_j\Big)\Big]+\sum b_j c_j,$$ where $$\tilde b_j:=b_j+s_b\,1_{j=0}$$. So, $$i$$ is no greater than $$\inf_b\big\{\big[\sup\big(f-\sum b_j g_j\big)\big]+\sum b_j c_j\big\}=IS$$. Thus, (4) is verified as well.

So, by (3) and (4), (1) indeed follows from (2).

In turn, the von Neumann-type minimax duality (2) follows under general conditions when $$L(\mu,b)$$ is affine in $$\mu$$ and in $$b$$ (as it is in our case). A necessary and sufficient condition for the minimax duality $$\inf_y\sup_x F(x,y)=\sup_x \inf_y F(x,y)$$ whenever $$F(x,y)$$ is concave in $$x$$ and convex in $$y$$ was given in this paper.

• Thanks a lot! This perfectly answers my question. – Eggplant Jul 7 '20 at 2:22