# Given a real function $g$ satisfying certain conditions, can we construct a convex $h$ with $h \le g$?

The following is Exercise 8 from Chapter 3 of Rudin's Real and Complex Analysis (not a homework problem, just for fun).

Let $g$ be a positive function on $(0, 1)$ such that $g(x) \to \infty$ as $x \to 0$. Does there exist a convex function $h$ on $(0, 1)$ such that $h \le g$ and $h(x) \to \infty$ as $x \to 0$?

This seems true, but I can't show it. All I've been able to do is to reduce the problem to $g$ being a monotone step function or a strictly monotone piecewise-linear function but this doesn't seem to get me anywhere. I'm not sure how to use the property of $g$ to construct the explicit $h$.

-
Isn't your strictly monotone piecewise-linear function already convex? It would seem to me it has to be (else I've been working too long already...) – Sam Jul 9 '11 at 20:23
@Sam: It needn't be: it might have consecutive pieces with slopes $-2,-1,-5$, for instance. – Brian M. Scott Jul 9 '11 at 20:56
@Brian: Thanks for clearing that up! – Sam Jul 9 '11 at 21:17

I am going to give you a hint toward an argument, and then en explanation of a) intuition about convex functions, and b) why constructing the most optimal convex function $h$ might not be possible.

First, the hint. For any non-empty family of functions $\{f_\alpha\}_{\alpha\in I}$ bounded above by some function $g$, we can construct a supreme function $f=\sup\{f_\alpha\}$ given by $f(x)=\sup_{\alpha\in I}\{f_\alpha(x)\}$. This is a generalization of the least upper bounder property from sets of numbers to sets of real-valued functions.

A property which you might not know about is that if the family of functions $\{f_\alpha\}$ consists of convex functions, then the supreme function $f=\sup\{f_\alpha\}$ is also convex. This allows you sufficient mileage to solve your problem with the following strategy:

1. Show that the supreme function of bounded above convex functions is convex.
2. Show that there exists a convex function $h$ such that $h\leq g$ when $g$ is bounded below. This shows that the family of convex functions bounded above by $g$ has a supreme convex function $f$.
3. Show that if a convex function $h$ such that $h\leq g$ is bounded above by some number $M\leq g(x)$ for some $x$, then there exists a convex function $h'$ such that $h<h'\leq g$ and $\sup_x\{h'(x)\}=M$.
4. (non-constructive) The previous step establishes that the supreme convex function $f$ (whose existence you know of non-constructively) must be not bounded above by any number $M\leq g(x)$ for some $x$. Since $f$ is in fact dominated by $g$, show that for every $a$, $g(x)\to\infty$ as $x\to a$ implies $f(x)\to\infty$ as $x\to a$ (i.e. that every pole of $g$ demands a pole of $f$; you can do this by clever domain restriction to domains where $g$ would have only one pole).
5. (constructive) Use the construction of 2. to define an infinite sequence of bounded convex functions $h_1<h_2<\dots$ with supremums increasing to infinity which will converge to an unbounded convex function dominated by $g$.

Second, the intuition. A good way to think about convex functions is that $h$ is convex on $(0,1)$ if and only if the epigraph $E_h=\{(x,y)\colon y\geq h(x)\}$ (the set of all points in $(0,1)\times\mathbb R$ that lie on or above the graph of $h$) is convex.

Epigraphs are pretty cool, and useful. For example, we can express the statement $h\leq g$ as the statement that the epigraph of $h$ contains the epigraph of $g$. To see this, note that $(x,y)\in E_g$ if and only if $y\geq g(x)$, and the assumption that $g(x)\geq h(x)$ then implies that $y\geq h(x)$ and hence $(x,y)\in E_h$.

For another example, suppose that $f=\sup\{f_\alpha\}$ is the supreme function of some bounded above family. In terms of epigraphs, we have $E_f=\bigcap_{\alpha\in I}E_{f_\alpha}$, i.e. taking supremums of functions is the same as intersecting their epigraphs. This also shows why we need the condition that the family of functions is bounded above by some other function -- if we don't have that condition, then the intersection of the epigraphs could end up missing certain lines. For example, if our family of functions was $0$ everywhere except at $a$ where $f_i(a)=i$, then the intersection of the epigraphs would be everything above $y=0$ except for the line $x=a$.

Using epigraphs we can also easily see that the supreme of a family of bounded above convex functions is a convex functions, since then we are simply intersecting closed convex sets (epigraphs are always closed sets), and convexity theory tells us that arbitrary intersection of convex sets gives us a convex set.

Additionally, we can almost construct the supreme convex function $f$ bounded above by $g$: it is the function whose epigraph is the closed convex hull of the epigraph of $g$. This then is the problem with determining $f$ explicitly, namely determining the boundary of the closed convex hull of a closed set is (or seems to me) difficult to do so in a useful way (you could just look at how horizontal lines intersect the epigraph of $g$, fill in segments between points of intersection, and keep track of data, but that seems painful and difficult to use to show that $f$ is unbounded in a way different from what I sketched above).

-
So, if I understand this right, I may construct a sequence of functions $h_n$, each of which is convex and dominated by $g$, such that $\lim_{x \to 0} \sup h_n (x) \to \infty$, and this will do the job? I actually recall having shown that the $\sup$ of a convex collection of functions is convex, so this gets the job done nicely. – guy Jul 9 '11 at 23:23

I think the answer is yes. Define a sequence $\{\delta_n\}$ as follows: $0<\delta_{n+1}<\delta_n<1$, $\delta_{n}-\delta_{n+1}\geq \delta_{n+1}-\delta_{n+2}$,$^{\dagger}$ and $g(x)>n$ on $(0,\delta_n)$; we can also arrange it so that $\delta_n\to0$. Define lines $\ell_n(x)$ by $$\ell_n(x)=\frac{1}{\delta_{n+1}-\delta_n}(x-\delta_n)+n-1,$$ so that $g(x)>\ell_n(x)$ on $(0,\delta_n)$, and the slope of $\ell_{n+1}(x)$ is not greater than that of $\ell_n(x)$. Define $h(x)$ by $h(x)=0$ on $[\delta_1,1)$ and $$h(x)=\ell_n(x)\qquad(x\in[\delta_{n+1},\delta_n)).$$ Then $h(x)$ is convex because its slope is clearly nondecreasing, and it is continuous. But also $$\lim_{x\to0}{h(x)}=\lim_{n\to\infty}h(\delta_{n+1})=\lim_{n\to\infty}\left(\frac{1}{\delta_{n+1}-\delta_n}(\delta_{n+1}-\delta_n)+n-1\right) =\infty.$$

$^{\dagger}$ To see that we can get $\delta_n-\delta_{n+1}\geq\delta_{n+1}-\delta_{n+2}$, let $\{\epsilon_n\}$ be any sequence satisfying the other conditions, let $n$ be the least integer for which $\epsilon_n-\epsilon_{n+1}<\epsilon_{n+1}-\epsilon_{n+2}$, and choose $k$ large enough so that $\epsilon_{n}-\epsilon_{n+k}\geq\epsilon_{n+k}-\epsilon_{n+k+1}$ (such $k$ exists because $2\epsilon_{n+k}-\epsilon_{n+k+1}\to0$); take $\delta_i=\epsilon_i$ for $i\leq n$, $\delta_{n+1}=\epsilon_{n+k}$, $\delta_{n+2}=\epsilon_{n+k+1}$, and proceed (e.g., by induction).

-
Thank you Nick. I deleted the wrong answer. – niyazi Jul 9 '11 at 21:35

Consider the epigraph of $g$, which is the set of all points which lie on or above the graph of $g$; formally ${\rm epi}(g) = \{ (x,y) ~|~ x \in (0,1), y \geq g(x) \}$. Let $h$ be a function whose epigraph is the closure of the convex hull of ${\rm epi}(g)$. Then $h$ does the trick.

To argue this we need to show: (1) there exists a function $h$ with the above property (2) $h \leq g$ (3) $h(x) \rightarrow \infty$ as $x \rightarrow 0$. (4) $h$ is convex.

The easiest are (2) and (4). (2) is equivalent to the assertion that ${\rm epi}(g) \subset {\rm epi}(h)$, which follows from the definition of $h$. As for (4), the convexity of a function is equivalent to the convexity of its epigraph, and the convex hull of any set is convex; moreover, the closure of a convex set is convex.

Point (3) is not difficult either; simply reformulate the assertion that $g(x) \rightarrow \infty$ as $x \rightarrow 0$ as follows: for any $N>0$, there is a small enough interval $[0,\delta]$ such that if $x$ lies in this interval then $g(x) \geq N$. But by definition of $h$ this implies that $h(x) \geq N$ for $x \in [0,\delta]$, so $h(x)$ goes to infinity as $x \rightarrow 0$ as well.

To demonstrate (1), define $h(x)$ to be first point on the vertical line going through $(x,0)$ which is in ${\rm cl} ({\rm epi}~ g)$; let us agree to call the latter set $H$. We must now argue that the points in $H$ are precisely those which lie above the graph of $h$. That each point in $H$ lies above the graph of $h$ follows by definition of $h$. To get the other direction - that every point above the graph of $h$ is in $H$ - observe that every point above the graph of $h$ lies above a point in $H$, and it is not too hard to argue it must consequently be in $H$ itself.

-
+1 I really like this answer; I definitely learned a new approach to questions like this. – Nick Strehlke Jul 13 '11 at 21:38