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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

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|cite|improve this answer

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|cite|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
    
And the definition of a convex function is the Jensen's inequality ! – Saradhi Apr 22 at 9:22

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|cite|improve this answer

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.