Convex hull of a convex curve as an infinite intersection of convex hull of triangles

convex-analysisconvex-hullspolytopes

Let $f(x)$ be a univariate convex curve (say $f(x) = x^2$) and let the domain be bounded. The goal is to prove that the convex hull of this curve in its domain can be expressed as an infinite intersection of convex hull of triangles. The sequence of convex hull is constructed as follows:

  1. Uniformly partition the domain into $k$ partitions
  2. Construct a triangle in each partition using the two tangents at the
    extreme points of the partition and the secant joining the extreme
    points,
  3. Take the convex hull of the resulting $k$ triangles. Let the convex
    hull formed at iteration $k$ be denoted by $A_k$.

Now, we want to prove $\cap_k A_k = \operatorname{conv}(y=f(x))$.
Any help is appreciated.

An example is shown for <span class=$k=2$ and $f(x) = x^2$ in the domain $[-2, 2]$">

Best Answer

Let me assume that the domain in question is the interval $[a,b]$. Let me denote by $G:=\{ (x,f(x)): \ x\in [a,b]\}$ the graph of $f$. Since $G \subset A_k$ by convexity of $f$, it holds $conv(G) \subset A_k$.

Let $f$ be bounded on the interval $[a,b]$. Then it is Lipschitz continuous there. Since you are talking about tangents, let me assume that $f$ is differentiable on the interval. Since $f$ is differentiable and Lipschitz continuous, we have $|f'(x)|\le L$ for all $x\in [a,b]$.

At step $k$, we partition the interval $[a,b]$ into $k$ subintervals of length at most $h_k$, with $h_k \to0$ for $k\to \infty$.

Let $[x_1,x_2]$ an interval of the partition. Then the two lines below the graph that define the corresponding triangle can be described by the mappings $$ x\mapsto f(x_1) + f'(x_1)(x-x_1) $$ and $$ x\mapsto f(x_2) + f'(x_2)(x-x_2). $$ Let $x\in [x_1,x_2]$. Then the distance of a point on the triangle can be bounded from above $$ | f(x) - (f(x_1) + f'(x_1)(x-x_1))|, $$ i.e., by the distance of the corresponding point of one the lines to the graph.

And by the mean value theorem, $$ |f(x) - (f(x_1) + f'(x_1)(x-x_1))| = |(f'(\xi)- f'(x_1))(x-x_1)| \le L |\xi-x_1| \cdot |x-x_1| \le L |x_2-x_1|^2 \le L h_k^2. $$ That is, the distance from an point $x$ below the graph in some triangle to the graph tends to zero for $k\to \infty$. If $x$ is a point in some triangle and above the graph then $x\in conv(G)$ anyway.

Let now $x \in \cap A_k \setminus conv(G)$. Then for all $k$, $x$ is in some of these constructed triangles and below the graph. By the arguments above $dist(x,G) \le Lh_k^2 \to0$. So $x\in G$, a contradiction, and we have $ \cap A_k \subset cong(G)$.

Related Question