Convex Analysis – Prove Function is Convex if Convex When Restricted to Any Line

convex optimizationconvex-analysis

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.

Best Answer

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.

Related Question