2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dieter Kadelka Jun 30 at 13:57
  • $\begingroup$ @DieterKadelka Sorry for the confusion. I have added illustrations for the notation. $\endgroup$ – Eggplant Jul 7 at 2:21
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! This perfectly answers my question. $\endgroup$ – Eggplant Jul 7 at 2:22

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.