# Show $\phi (b) = \inf \{f(x) : g(x) \leq b \}$ is convex when $f, g$ are convex

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.

## 1 Answer

HINT:

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$.