A certain min/max equality

51 Views Asked by At

Denote the set of positive integers by $\mathbb{N}$, the set of real numbers by $\mathbb{R}$, and the set of non-negative real numbers by $\mathbb{R}_+$. For every pair $i, j \in \mathbb{N}$, denote by $[i .. j]$ the set $\{k \in \mathbb{N}\ |\!:\ i \leq k\leq j\}$.

For every $n \in \mathbb{N}$ denote the Euclidean topology on $\mathbb{R}^n$ by $\mathcal{T}_n$, and for every $A \subseteq \mathbb{R}^n$ denote by $\mathcal{T}_n(A)$ the topology induced on $A$ by $\mathcal{T}_n$.

For every $n \in \mathbb{N}$, denote by $I_n$ the unit square in $\mathbb{R}^n$, i.e. $I_n := [0,1]^n$. For every $n \in \mathbb{N}$ denote by $\mathbf{1}_n$ the $n$-tuple $\mathbf{1}_n := (\underbrace{1, 1, \dots, 1}_n)$ (note that we have $\mathbf{1}_n \in I_n$).

For every $n \in \mathbb{N}$ and for every $\mathbf{a} = (a_1, \dots, a_n) \in \mathbb{R}^n$ we denote by $\sum \mathbf{a}$ the sum of $\mathbf{a}$'s components, i.e. $\sum \mathbf{a} := \sum_{i = 1}^n a_i$. For every $n \in \mathbb{N}$ and for every $\mathbf{a} = (a_1, \dots, a_n), \mathbf{b} = (b_1, \dots, b_n) \in \mathbb{R}^n$ we write $\mathbf{a} \geq \mathbf{b}$ iff $a_i \geq b_i$ for every $i \in [1..n]$.

For every $n \in \mathbb{N}$ and for every function $f: A\subseteq\mathbb{R}^n\rightarrow\mathbb{R}$, we call $f$ (1) monotonic iff whenever $\mathbf{a}, \mathbf{b} \in A$ are such that $\mathbf{a} \geq \mathbf{b}$, we have $f(\mathbf{a}) \geq f(\mathbf{b})$, (2) positive-homogeneous iff $f(c\mathbf{a}) = cf(\mathbf{a})$ whenever $c\in\mathbb{R}_+$ and $\mathbf{a}, c\mathbf{a} \in A$.

Let $n \in \mathbb{N}$. Let $A \subseteq I_n$ be such that $\mathbf{1}_n \in A$, and let $v:A\rightarrow\mathbb{R}_+$ be a function that is (1) monotonic, (2) $\mathcal{T}_n(A)/\mathcal{T}_1$-continuous, and (3) Lispschitz in the sense that there exists some $K \in \mathbb{R}$ such that $v(\mathbf{a}) \leq K\sum \mathbf{a}$ for every $\mathbf{a} \in A$.

Denote by $L$ the set of all concave, monotonic, and positive-homogeneous functions $f:\mathbb{R}_+^n\rightarrow\mathbb{R}$ such that $f(\mathbf{a}) \geq v(\mathbf{a})$ for every $\mathbf{a} \in A$. (Concavity is to be understood w.r.t. the standard real vector space on $\mathbb{R}^n$.)

I would like to show that the following holds. For every $\mathbf{b} \in \mathbb{R}_+^n$, $$ \inf_{f\in L}f(\mathbf{b}) = \sup \{\sum_{i=1}^k c_i v(\mathbf{a}_i)\ :\!|\ \big((c_1, \dots, c_k), (\mathbf{a}_1, \dots, \mathbf{a}_k)\big) \in \Gamma\}, $$ where $\Gamma$ is the set consisting of all pairs $\big((c_1, \dots, c_k), (\mathbf{a}_1, \dots, \mathbf{a}_k)\big) \in \cup_{m \in \mathbb{N}}(\mathbb{R}_+^m\times A^m)$ such that $\mathbf{b} \geq \sum_{i=1}^k c_i \mathbf{a}_i$.


This question is a self-contained restatement of an unproved claim that appears in the following article (equation "(5)" on p. 169).

I'd appreciate any hints, suggestions or proof sketches, as well as full-blown proofs.