Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
    
You are not using Jensen's inequality but the definition of the convexity of a function. –  Did Apr 26 '13 at 8:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.