5
$\begingroup$

Let $f_1(x), f_2(x), \ldots, f_n(x)$ be a set of convex functions. We define $f(x)$ as

$$ f(x) = \underset{i}{\text{max}} \left\{ f_i(x) \right\}. $$

enter image description here

How do I show that $f(x)$ is also convex, and the domain of $f$ is intersection of the domains of $f_i$?

$\endgroup$
8
$\begingroup$

Well, the domain of $f$ must be the intersection of the domains of the constituent functions, otherwise the $\max$ cannot be defined.

More generally, suppose $f_\alpha :C \to \mathbb{R}$ is a family of convex functions, with $\alpha \in A$, some index set, and let $f(x) = \sup_{\alpha \in A} f_{\alpha}(x)$.

Then, for any $\alpha \in A$, $\lambda \in [0,1]$, \begin{eqnarray} f_\alpha(\lambda x + (1-\lambda) y) &\le& \lambda f_\alpha(x) + (1-\lambda) f_\alpha(y) \\ & \le & \sup_{\alpha' \in A} (\lambda f_{\alpha'}(x) + (1-\lambda) f_{\alpha'}(y)) \\ & \le & \sup_{\alpha' \in A} \lambda f_{\alpha'}(x) + (1-\lambda) \sup_{\alpha' \in A}f_{\alpha'}(y) \\ &=& \lambda f(x) + (1-\lambda) f(y) \end{eqnarray}

How taking the supremum of the left hand side gives the desired result: $$f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y)$$

Alternatively, you could note that $\operatorname{epi} f = \cap_{\alpha \in A} \operatorname{epi} f_\alpha$, and that the intersection of convex sets is convex.

$\endgroup$
3
$\begingroup$

Since it is given that all $f_i(x)$ are convex, we can write the following inequality using Jensen's Inequality.

$$ f_i(\theta x_1 + (1-\theta)x_2) \le \theta f_i(x_1) + (1-\theta)f_i(x_2); \qquad \theta \in [0,1] $$

We take maximum of the both sides.

$$ \underset{i}{\text{max}} \left\{ f_i(\theta x_1 + (1-\theta)x_2) \right\} \le \underset{i}{\text{max}} \left\{ \theta f_i(x_1) + (1-\theta)f_i(x_2) \right\} \qquad \ldots \text{(I)} $$

It is clear that

$$ \underset{i}{\text{max}} \left\{\theta f_i(x_1) + (1-\theta)f_i(x_2) \right\} \le \underset{i}{\text{max}} \left\{\theta f_i(x_1) \right\} + \underset{i}{\text{max}} \left\{(1-\theta)f_i(x_2) \right\}. \qquad \ldots \text{(II)} $$

Substitiute $\text{(II)}$ into $\text{(I)}$:

$$ \underset{i}{\text{max}} \left\{ f_i(\theta x_1 + (1-\theta)x_2) \right\} \le \underset{i}{\text{max}} \left\{\theta f_i(x_1) \right\} + \underset{i}{\text{max}} \left\{(1-\theta)f_i(x_2) \right\} \qquad \ldots \text{(III)} $$

From the definition of $f(x)$ in the OP we can write $\text{(III)}$ as

$$ f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2). \qquad \ldots \text{(IV)} $$

Being able to write $f(x)$ in the form $\text{(IV)}$ implies that it is convex.

$\endgroup$
  • $\begingroup$ You are not using Jensen's inequality but the definition of the convexity of a function. $\endgroup$ – Did Apr 26 '13 at 8:24
  • $\begingroup$ And the definition of a convex function is the Jensen's inequality ! $\endgroup$ – Saradhi Apr 22 '16 at 9:22
0
$\begingroup$

Hint: $f_j(t a + (1-t) b) \le t f_j(a) + (1-t) f_j(b)$ for $0 \le t \le 1$. Note that $\max_j (t f_j(a) + (1-t) f_j(b)) \le t \max_j f_j(a) + (1-t) \max_j f_j(b)$...

$\endgroup$

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.