Duality problem of an infinite dimensional optimization problem

Question

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?

Answer 1

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.