I would like to show $ \phi (b) = \inf \{f(x) : g(x) \leq b \}$ is convex when $f, g$ are convex.

This is equivalent to showing that

$$\inf \{f(x) : g(x) \leq ta+(1-t)b \} \leq t \inf \{f(x) : g(x) \leq a \} + (1-t)\inf \{f(x) : g(x) \leq b \}$$

where $t \in [0,1]$ (we will assume this infimum is finite for all values).

My thoughts:

WLOG let $a \leq ta + (1-t)b \leq b$ and $\phi (a) = f( \alpha), \phi (b) = f( \beta), \phi (ta+(1-t)b) = f( \gamma)$.

Then since the sets are contained in eachother, we have $f( \beta) \leq f(\gamma) \leq f(\alpha)$.

By convexity of $f$, $t f( \alpha) + (1-t) f( \beta) \geq f(t \alpha + (1-t) \beta)$ so it would be nice to show $f( \gamma) \leq f(t \alpha + (1-t) \beta)$, but I do not see why.

If $f$ has a minimum, by convexity this is a global minimum. If this minimum occurs inside (not on boundary) of the set for which $g(x) = ta + (1-t)b$ we can see the result quite easily. Else, the mimima for each case must occur on the boundaries of the sets. But then I do not see how to proceed.

Any help is appreciated.



Consider $x_1$, $x_2$ so that $g(x_1) \le a$ and $g(x_2) \le b$. Since $g$ is convex we have $$g( \lambda x_1 + (1-\lambda) x_2) \le \lambda g(x_1) + (1-\lambda) g(x_2) \le \lambda a + (1-\lambda) b$$

hence $\lambda x_1 + (1-\lambda) x_2$ is in the set $\{ x\ | \ g(x) \le \lambda a + (1-\lambda) b \}$.

From the definition of $\phi$ we get
$$\phi( \lambda a + (1-\lambda) b) \le f( \lambda x_1 + (1-\lambda) x_2)$$

However, since $f$ is convex we have $$f( \lambda x_1 + (1-\lambda) x_2)\le \lambda f(x_1) + (1-\lambda) f(x_2) $$

Therefore $$\phi( \lambda a + (1-\lambda) b) \le \lambda f(x_1) + (1-\lambda) f(x_2) $$

Now take first $\inf$ for $x_1 \in \{ x \ | g(x) \le a\}$ and get $$\phi( \lambda a + (1-\lambda) b) \le \lambda \phi(a) + (1-\lambda) f(x_2) $$ Now take another $\inf$.


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.