[Math] Prove the supremum of the set of affine functions is convex

convex optimizationmultivariable-calculusnonlinear optimizationoptimizationreal-analysis

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.

Best Answer

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.