Suppose $X \subset \mathbb{R}^n$ is a convex set and $f: X \rightarrow \mathbb{R}$ is a function which is bounded from below. Let $x_0 \in X$ be a point.

Define $$a = \inf \{ \alpha f(x_1) + (1 - \alpha) f(x_2) | x_1, x_2 \in X,\,\, \alpha \in [0,1], \text{ and } \alpha x_1 + (1 - \alpha) x_2 = x_0\}$$ and $$b = \inf \{ \sum_{i = 1}^k \alpha_i f(x_i)| k \geq 1, \,\, x_1, \ldots, x_k \in X,\,\, \alpha_i \in [0,1], \,\, \sum_i \alpha_i = 1, \text{ and } \sum_i \alpha_i x_i = x_0\}.$$ Of course, $a \geq b$. My question is whether $a = b$? If $n = 1$ (so $X \subset \mathbb{R}$, I can show that $a = b$. Since I extensively used properties of convex combinations in $\mathbb{R}$, I am not sure it is also true in higher dimensional spaces. I can neither construct a counter-example. Can someone help me out?

Thank you!


I have deleted my previous 1/2 baked answer to this question.

This question is covered by section 17 of Rockafellar's Convex Analysis, in particular Corollary 17.1.5 on p.157. What the OP calls $b$ is what Rockafellar calls $(\operatorname{conv}f)(x_0);$ the OP's formula for $b$ appears at the bottom of R's p.36. The correct formula for $a$ in the case $n>1$ is the conclusion of Cor. 17.1.5: $$ (\operatorname{conv}f)(x) = \inf\left\{\sum_{i=1}^{n+1}\lambda_i f(x_i)\,\big| \sum_{i=1}^{n+1} \lambda_i x_i = x\right\}.\tag{*}$$

Here $\operatorname{conv}f$ is the pointwise supremum of all convex functions pointwise less than $f$.

The following counterexamples, based on Ashkan's example, show that the convex combinations in (*) need $n+1$ terms. Let $X\subset\mathbb R^n$ be a regular $n$-simplex, with vertex set $V=\{v_1,\dots,v_{n+1}\}$ and centroid $m=\sum_{i=1}^{n+1} v_i/ (n+1)$. Note that $m$ is at positive distance from each of the facets of $X$. Now define $f(x)=1$ for all $x\in X\backslash V$ and $f(v)=0$ for all $v\in V.$ Clearly $g = \operatorname{conv}f$ is the constant zero function. Now we try to approximate $g(m)$ with $n$-term sums of the form $S=\sum_{i=1}^n \lambda_i f(x_i),$ with $m=\sum_{i=1}^n \lambda_i x_i.$ If there is a $\lambda$ for which $S<\epsilon$, all but $\epsilon$ of the mass of $\lambda$ is concentrated on $V$. But $\lambda$ has only $n$ terms, so all but $\epsilon$ of the mass is concentrated on $n$ of the points of $V$. Hence $m$ is within distance $O(\epsilon)$ of one of the facets of $X$. Since $m$ is at positive distance from the facets, $S$ cannot be made arbitrarily close to $0.$


I found a counter example where $f$ defined on a compact convex set.

Let $f: \Bbb B \to \Bbb R$ and with

$$f(x)= \left\{\begin{matrix} -1 & x\in C \\ 1 & x \notin C \end{matrix}\right. $$

where $X= \Bbb B$ is the closed Unit ball in $\Bbb R^2$ and $C$ is the open left semicircle i.e. $$C= \{ (x,y) \in \Bbb R^2 ~ | ~ x^2 + y^2 = 1, ~~ x <0 \} $$

Then for $x_0 = 0$ observe that $a=0$ and $b < 0 $

P.S: Note that

$$b \leq \frac{1}{3}f(\frac{-\sqrt2}{2}, \frac{+\sqrt2}{2} ) + \frac{1}{3} f (\frac{-\sqrt2}{2}, \frac{-\sqrt2}{2}, ) + \frac{1}{3} f(1, 0) = - \frac{1}{3}, $$

Maybe you need assume continuity, however still I feel claim is not true!


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.