Proof: A function is convex iff it is convex when restricted to any line ..

Question

Let $f\colon \Bbb R^n\to \Bbb R$ be a function. Then, $f$ is convex if and only if the function $g\colon\mathbb{R} \to \mathbb{R}$ defined as $g(t) \triangleq f(x+tv)$, with domain $$ \operatorname{dom}(g)=\{t\mid x+tv \in \operatorname{dom}(f), x\in \operatorname{dom}(f), v\in \mathbb{R}^n\}, $$ is convex in $t$.

It says that: a function is convex if and only if it is convex when restricted to any line that intersects its domain. My question was how to prove it?

Reference: Steven Boyd, Convex Optimization, Cambridge University Press, Page 67.

Answer 1

Here's a simple solution. A function $f:\mathbb{R}^n\to\mathbb{R}$ is convex iff the set $\Gamma_f=\{(x_1,\cdots,x_n,y)| f(x_1,\cdots,x_n)\leq y \}\subseteq\mathbb{R}^{n+1}$ is convex.

Now consider the region above the graph of $g(t)$: $\Gamma_G=\{(t,y)| g(t)\leq y\}$. But this set is just the intersection of $\Gamma_f$ with the plane centered at $x$ generated by the vectors $(v,0)$ and $(0,1)$. Since linear subspaces are convex, $\Gamma_f$ is convex, and the intersection of two convex bodies is still convex, $\Gamma_g$ is convex and so $g$ is convex.

The reverse direction is similar. Suppose $f$ is not convex. Then $\Gamma_f$ is not convex, and there exist points $a,b\in\Gamma_f$ such that the line between $a,b$ is not entirely contained in $\Gamma_f$. Since by definition such a line cannot be vertical, it means that the projection of such a line on to the first $n$ coordinates is again a line, and so we may choose that as the line that $g$ picks out. But then $g$ is not convex for the same reason- the line between $a$ and $b$ is not wholly contained in $\Gamma_g$.

Answer 2

The "$\Rightarrow$" part is easy.

The other direction can be proven by contradiction: Assume that $f$ is not convex. Then, $\operatorname{dom}(f)$ is not convex or there exist $x,y \in \operatorname{dom}(f)$ and $\lambda \in (0,1)$ with $f( \lambda \, x + (1-\lambda) \, y ) > \lambda \, f(x) + (1-\lambda) \, f(y)$.

1. If $\operatorname{dom}(f)$ is not convex, there exist $x,y \in \operatorname{dom}(f)$ and $\lambda \in (0,1)$ with $\lambda \, x + (1-\lambda) \, y \not\in \operatorname{dom}(f)$. Now, set $v = y - x$ and use the $g$ as in the statement of the theorem. Then, it is easy to check that $\operatorname{dom}(g)$ is not convex, since it contains $0$ and $1$, but not $1-\lambda$.

2. In the other case, you can define $g$ in the same way and get $g(1-\lambda) > \lambda \, g(0) + (1-\lambda) \, g(1)$.

In both cases, we obtained a contradiction to the convexity of $g$.

Answer 3

I am always interested in proving math theorem intuitively, so here I am.
purpose: Assume $ f:\mathbb{R}^m \rightarrow \mathbb{R} $, $g:\mathbb{R} \rightarrow \mathbb{R}$, so the theorem indicates the convexity of $f$ equals the convexity of $g$, in other words, we can check the convexity of $f$ by checking the convexity of functions of one variable.
intuitive Prove: assume $f:\mathbb{R}^2 \rightarrow \mathbb{R}$, just like the figure1 shows below.f(x). we want to check the convexity of $f(x)$.

1. we cut out a cross-section of $f(x)$ just like figure1 shows.

2. Then we get a new function (red line) which we call $g(t)=f(x+tv)$, notice $ x+tv $ is a line if we fix x which located in domain of f and arbitrary v. so if we iterate every lines that intersects domain of $f(x)$, we could get infinite $g(t)$, if we make sure these $g(t)$ are convex, then the original function $f(x)$ is convex too.