Prove convexity when restricted to a line

Question

One of several ways to check convexity is when the function is restricted to a line (p.67-68, Boyd's and Vandenberghe's book on Convex Optimization): A function $f$ is convex if and only if for all $x\in\text{dom}f$ and all $v$, the function $g(t)=f(x+tv)$ is convex (on its domain, $\left\{t\mid x+tv\in\text{dom}f\right\}$).

I'd like to prove this rather simple thing, but since I'm a novice when it comes to proofs, I'd appreciate your take on it.

One straightforward way is to check whether the second derivative is positive semidefinite, but this is only a sufficient condition and also requires the function to be twice differentiable: $$g(t)=f(x+tv) \\ g'(t)=f'(x+tv)v \\ g''(t)=f''(x+tv)v^2$$ which is positive semidefinite since $f$ is convex (i.e., $f''\geq 0$).

Another and probably the preferred way:

($\Rightarrow$): If $f(x)$ is convex, then $f(y)$ is also convex for any $y=x+tv$ that belongs to the same domain as $x$.

($\Leftarrow$): Only if $f(x+tv)$ is convex, is $f(x)$ convex. This follows from the fact that if $f(x+tv)$ is convex for $x+tv$ for any $t$, then it is also convex for $t=0$, in which case the result follows.

Answer 1

The second part of your proof is incorrect. Convexity is not a pointwise property, but a property of the function on a specific set (its domain in most cases). So, saying "it is also convex for $t=0$" is inaccurate.

I would simply use definition of convexity to prove this part:

($\Leftarrow$) Let us take $x_1,x_2\in\text{dom}f$. We need to show that for every $\alpha\in[0,1]$ \begin{equation} \alpha f(x_1)+(1-\alpha)f(x_2)\geq f(\alpha x_1+(1-\alpha)x_2). \end{equation} Now, since $g(t)=f(x+vt)$ is convex for all $x\in\text{dom}f$ and all $v$, for every $\alpha\in[0,1]$: \begin{align} \alpha g(t_1)+(1-\alpha)g(t_2)&\geq g(\alpha t_1+(1-\alpha)t_2) \\ \alpha f(x+vt_1)+(1-\alpha)f(x+vt_2)&\geq f(x+v(\alpha t_1+(1-\alpha)t_2)) \end{align} let us take $x=x_1$, $v=x_2-x_1$, $t_1=0$ and $t_2=1$, and assign them to the last inequality: \begin{equation} \alpha f(x_1)+(1-\alpha)f(x_2)\geq f(\alpha x_1+(1-\alpha)x_2) \end{equation} and therefore $f$ is convex.

Answer 2

I want to add the ($\implies$) part to Gilad's answer.

Consider multivariate, real-valued function $f$. For any $x \in \mathrm{dom} f$ and $v \in \mathbb{R}^{n}$,

The proof of $f$ convex $\implies$ $g$ convex, where

$g(t)=f( x+tv )$ and $G = \left\{ t \in \mathbb{R} : x+tv \in \mathrm{dom}f \right\} \subset \mathbb{R}$ is the domain of $g$,

can be done directly from definition: For any $a,b \in G$ and $\alpha \in [0,1]$, $$g(\underbrace{\alpha a + ( 1-\alpha ) b }_{t}) = f( x + (\underbrace{ \alpha a + ( 1-\alpha ) b }_{t})v ) = f( \underbrace{\alpha x + ( 1-\alpha ) x}_{x} + \alpha av + ( 1-\alpha ) bv)$$ $$=f( \alpha ( x + av ) + ( 1-\alpha ) ( x+bv ) ) \leq \alpha f( x+av ) + ( 1- \alpha ) f(x + bv) = \alpha g( a ) + ( 1-\alpha ) g( b )$$ (using convexity of $f$ with $x=( x+av ), y=( x+bv)$)

Alternatively, assume towards a contradiction that $g( t ) = f( x + tv )$ isn't convex: $\exists a,b, \in G$ and $\exists \alpha \in [0,1]$ such that (*) $$g( \alpha a + (1-\alpha ) b) > \alpha g( a ) + ( 1-\alpha ) g( b )$$ Yet, $g( \alpha a + ( 1 - \alpha ) b ) = f( x + ( \alpha a + ( 1-\alpha ) b)v ) = f( \alpha ( x + av ) + ( 1- \alpha ) (x+bv) ) \leq \alpha f( x + av ) + ( 1 - \alpha ) f( x + bv ) = \alpha g( a ) + ( 1 - \alpha ) g( b )$ which contradicts (*) hence $g$ is convex.

For reference, related two questions below have alternative proofs:

• Poof- A function is convex iff it is convex when restricted to a any line that intersects its domain.
• Convexity vs convexity on every line

Answer 3

Generally we know that a function is convex it is convex even after we restrict it to a line. "Restricting a function to a line" simply means that you draw a line in the domain of that function and evaluate the function along that line. To understand this, consider the case of a well curve. A well curve is just another paraboloid we can define by this equation: z=x^2/16 + y^2/9. We may visualize the graph as a curve in R2 space or a surface in R3 space. In 3D space the well curve will cast a shadow in the xy-plane forming the 2D plane of its domain. If one such 2D plane cuts through the well curve, the trace formed by the intersection of the plane with the paraboloid will be a convex/ non convex shape (a parabola for instance). If that shape's function g is convex then the initial 3D function is also convex. We call the trace or the parabola a line because imagine slicing the paraboloid from the top, from that viewpoint it will appear to be just a straight line (only when we view it from the side we realise that it is a parabolic curve). By the way if you sliced through a hyperbolic paraboloid you wouldn't get a parabola as a trace infacet it would be a hyperbola. So far we know that g is convex but it must also be a univariate function to satisfy the two requirements of this theorem. In 3D there were 3 variables: x,y and z but when we looked at the domain there were only x and y variables defining the function. Now since we are working in the domain we could put either x or y =0 and that would give us the equation in one variable making it a univariate function also.