4

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.

Amin
  • 2,103

3 Answers3

5

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.

C Lei
  • 171
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Community Sep 24 '21 at 13:57
  • 1
    While it is not really an answer to the question, I believe that it helps a lot to understand the statement. – Surb Sep 24 '21 at 16:18
3

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$.

Călin
  • 269
KReiser
  • 65,137
  • Dear @KReiser, thanks. But, I did not get your point completely. There are ambiguities that I couldn't trace the solution. In fact, I am new in this area. – Amin Jul 08 '16 at 07:22
  • Please point out exactly where you don't follow and I will do my best to add. – KReiser Jul 08 '16 at 07:29
  • You said, " 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)$." I did not get the point! I think you just didn't say elementary things. – Amin Jul 08 '16 at 07:34
  • The goal is to find a copy of $\Gamma_g$ inside $\Gamma_f$ so that I can reason easily. The way to do this is to find the copy of $\mathbb{R}\subset \mathbb{R}^n$ that $g$ picks out and then take the points of $\Gamma_f$ above that. This can be phrased as intersecting the plane $(x,0)+t(v,0)+u(0,1)$ where $t,u$ vary over all real numbers with $\Gamma_f$. The intersection of this plane with $\Gamma_f$ gives me an embedded copy of $\Gamma_g$, which I can then work with. – KReiser Jul 08 '16 at 07:43
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$.

gerw
  • 31,359
  • Dear @grew, could you please give me a tangible interpretation about this statement? – Amin Jul 08 '16 at 08:12
  • An interpretation could be: The definition of convexity only involves properties of $f$ on lines. Hence, it is sufficient to check (all) restrictions of $f$ to lines. – gerw Jul 08 '16 at 10:24
  • Concerning "$\Rightarrow$": This is really easy. Try to prove it yourself. – gerw Jul 08 '16 at 10:24
  • Just use definition of convexity, $f(\lambda x+(1-\lambda)y)\leq \lambda f(x) + (1-\lambda)f(y)$ – user85361 Jul 08 '16 at 12:49