12
$\begingroup$

Let $\langle f_i \rangle _{i \in I}$ be a family of affine functions on a convex and compact set $\Omega \subset \mathbb{R^d}$ such that $f_i = a_i.x +b_i$ for $x \in \Omega$. Prove that f, defined by $f(x) = sup_{i \in I}f_i(x)$ for $x \in \Omega$ is a convex function. Explain this geometrically.

I understand that since f is in $C^1(\Omega)$, f is convex if $sup(a_ix + b_i) \le sup(a_iy+b_i) + a_i(x-y)$, but i am having trouble proving this.

$\endgroup$

2 Answers 2

22
$\begingroup$

Let $(g_i)_{i\in I}$ be a family of convex functions on a convex compact set $\Omega\subseteq \mathbb{R}^d$. We will show that the sup of this family is convex. We will use the standard definition of convexity.

Let $g:=\sup_{i\in I} g_i$.

Take $x,y\in\Omega$ and $t\in[0,1]$.

Fix $i\in I$. Since $g_i$ is convex and bounded above by $g$, we have $$ g_i(tx+(1-t)y)\leq tg_i(x)+(1-t)g_i(y)\leq tg(x)+(1-t)g(y). $$ Since the latter holds for every $i\in I$, we can take the sup and find $$ g(tx+(1-t)y)\leq tg(x)+(1-t)g(y). $$

This holds for every $x,y\in \Omega$ and every $t\in[0,1]$. So $g$ is convex.

Now every affine function $f_i$ is convex, so the result follows from the general case above.

Geometrically? A function is convex iff its epigraph is convex. See here for a definition of the epigraph. It is clear that the epigraph of $\sup g_i$ is the intersection of the epigraphs of all the $g_i$. Now the intersection of convex sets is convex, which yields a more geometric proof of the statement above.

$\endgroup$
9
  • $\begingroup$ I am wondering, when $g_i$ have non-identical domains, if the claim holds and can still be proved via epigraphs. Pointwise supremum of a convex function collection. $\endgroup$
    – antonio
    May 26, 2013 at 14:39
  • $\begingroup$ @antonio How do you define $\sup g_i$ if the $g_i$ don't have the same domain? $\endgroup$
    – Julien
    May 26, 2013 at 18:04
  • $\begingroup$ Well, I suppose there are two possibilities: one is defining $$ g(x) = \sup \{g_i(x) \mid i \in I, x\in \mathrm{dom}\, g_i \} $$ So, for every $x^0$, I include only the $g_i(x^0)$ value when the function is defined at $x^0$, like to say that, if a function is not defined at point, then the function does not exist there and so no value is (can be) included in the set. Another possibility is to assume the function is $+\infty$ when not defined. I don't know if there is some established convention ruling out these options. $\endgroup$
    – antonio
    May 26, 2013 at 18:49
  • $\begingroup$ @antonio I see your point, but I think the rule is: define $\sup g_i$ on the intersection of the domains of the $g_i$'s. I have never seen any advantage of doing otherwise. But maybe there are situations where this is helpful... $\endgroup$
    – Julien
    May 26, 2013 at 18:53
  • 2
    $\begingroup$ @antonio The best formal definition is essentially what you gave. Take $(f_i)_{i\in I}$ a family of functions from some set $X$ to $\mathbb{R}\cup\{+infty\}$. Then for every $x\in X$, define $(\sup_{i\in I}f_i)(x)$ to be the sup of the set of real numbers $\{f_i(x)\,;\,i\in I\}$. It belongs to $\mathbb{R}\cup \{+\infty\}$. It is defined as the least upper bound of the latter set. You can find that in any book on Real Analysis. $\endgroup$
    – Julien
    May 26, 2013 at 19:38
2
$\begingroup$

I can't comment because I don't have enough reputation, hence posting as an answer. I don't think $f \in C^1(\Omega)$. Easiest example is take $\Omega = [0,1]$, $I = \{1,2\}$. $f_1(x) = \frac12$ and $f_2(x) = x$. Then, $f(x) = \frac12$ if $x \le \frac12$ and $x$ if $x > \frac12$. In particular, at $\frac12$ there is a kink.

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