In lecture 3 of the course Convex Optimization conducted by Stephen Boyd at 21 minutes mark he says that a function is convex if its convex when we restrict it to a line. What does he mean by restricting a function to a line?
Secondly his exact statement is that a function $f:R^n\to R$ is convex if $g:R\to R$ is convex where
$$
g(t) = f(x+tv), \{x \in dom(f), t \in dom(g),v \in R^n\}
$$
My doubt regarding this is that won't any function on real space be convex since it would just be a line?
Please correct me if I am wrong.
Best Answer
1] By restricting it to a line means, basically, you draw line in the domain of the function; then you evaluate your function only along that line.
2] Imagine a paraboloid $f:\mathbb{R}\times\mathbb{R} \mapsto \mathbb{R}$ defined by $f(x,y) = \frac{x^2}{a^2} + \frac{y^2}{b^2}$.
$\hskip2in$
Now, if you draw a line in the domain and evaluate this paraboloid only along that line, it would look like a parabola. Analytically, if you want to check how the function would be along the x-axis, then substitute y = 0 in the equation above and you get $f(x,y) = \frac{x^2}{a^2}$ which you might know is the equation for the parabola. Now, a parabola is convex and since every line in the domain here would give you a parabola, a paraboloid is convex. On the other hand, if you take a hyperbolic paraboloid:
$\hskip2in$
You draw a line in the domain in one direction, it would look like a parabola and you draw a line in the domain in another direction, it would look like an inverted parabola. Now, inverted parabolas are concave and not convex. Therefore, hyperbolic paraboloids are not convex.