0
$\begingroup$

I was reading this lecture on convex functions and I came across this

$f\colon \Bbb R^n\to \Bbb R$ is convex if and only if the function $g\colon \Bbb R\to \Bbb R$, $g(t) = f(x+tv)$, $\operatorname{dom}g=\{t\mid x+tv \mbox{ belongs to domain of }f\}$ is convex in $t$ for any $x$ belongs to the domain of $f$, $v$ belongs to $\Bbb R^n$.

So, I am a bit confused how this function of line is chosen. I mean $t$ and $v$ both are arbitrary as mentioned by the lecturer. But I want to visualize how this line looks like. I mean does it lie in the function itself.

  • 1
    The idea is that if I have to check convexity of a function, I just have take a plane and slice the function in every which way possible and see if that slice looks convex or not. Since that slice is just a curve, it is very easy to check for convexity. The g(t) parameterization captures this notion of the slice of the function.2012-06-17
  • 0
    can you elaborate what you mean by slicing a function? I mean how can I get a line when I slice a function by a plane?2012-06-17
  • 0
    When I say slice, I mean look at the intersection of that plane with the function.2012-06-17
  • 0
    I didn't get it. When I get the intersection, how come that is a line then? I could be anything for eg it could be a circle?2012-06-17
  • 0
    I mean the lecturer said that it is restriction of a convex function to a line. Does it mean that we will select an arbitrary line and view the function and see if that satisfies the convexity. But I am not sure how g(t) is a line. It is just a function of t. But it could be non linear as well. So how come it is a line?2012-06-17
  • 0
    >> Does it mean that we will select an arbitrary line ## Yes. >> But I am not sure how g(t) is a line. It is just a function of t. But it could be non linear as well. So how come it is a line? ## g(t) isn't a line, x + tv is the line.2012-06-17
  • 0
    So x+tv is a line just like Ax+b = 0 equation. But still. I didn't get after using g(t) are we checking the convexity of a totally different function g(t). I don't get how g(t) and f are related? Can you give a good example?2012-06-17
  • 0
    Ok, consider a well curve in 3D. Now, its domain is a 2D plane. Now, draw a line on this 2D domain and look at the function values only along this line. That will be a curve (It probably will look like a vertical parabola). Now, the theorem is if you can show that for all such lines in the domain, if the resulting curve of f is convex, then the entire f is convex and vice versa.2012-06-17
  • 0
    Also how come x+tv is a line. v and x both are vectors of dimension n. So how come x+tv is a line?2012-06-17
  • 0
    Again, consider a usual 2D plane. Take two points x = [1 1] and v = [2 2]. Now, consider x + tv and vary the value of t, what do you see?2012-06-17

3 Answers 3

2

Assume that $n=d+1$. The graph $\Gamma=\{(x,f(x))\mid x\in\mathbb R^d\}$ of $f$ is a $d$-dimensional subset of $\mathbb R^{d+1}=\{(x,z)\mid x\in\mathbb R^d,z\in\mathbb R\}$. Consider a line $L_0\subset\mathbb R^{d+1}$ included in the hyperplane $\{(x,0)\mid x\in\mathbb R^d\}\subset\mathbb R^{d+1}$, say the line $L_0=\{(x_0+tv_0,0)\mid t\in\mathbb R\}$ passing through $x_0$ with direction $v_0\ne0$.

Then, $L_0$ defines a vertical plane $P_0=L_0\times\mathbb R=\{(x_0+tv_0,z)\mid t\in\mathbb R,z\in\mathbb R\}\subset\mathbb R^{d+1}$ and, by definition, $P_0\cap \Gamma=\{(x_0+tv_0,f(x_0+tv_0)\mid t\in\mathbb R\}$.

On the other hand, the graph $G_0$ of the function $g_0:\mathbb R\to\mathbb R$, $t\mapsto g_0(t)=f(x_0+tv_0)$ is $G_0=\{(t,f(x_0+tv_0))\mid t\in\mathbb R\}\subset\mathbb R^2$. There is a natural bijection $\pi_0:P_0\to\mathbb R^2$ defined by $\pi_0(x_0+tv_0,z)=(t,z)$. One sees that $\pi_0(\Gamma)=G_0$.

The result says that $f$ is convex if and only if every $g_0$ is convex. This translates in terms of epigraphs as follows.

Recall that the epigraph of $f$ is $\Gamma^+=\{(x,z)\mid x\in\mathbb R^d,z\in\mathbb R,z\geqslant f(x)\}$. The epigraph of $g_0$ is $G_0^+=\{(t,z)\mid t\in\mathbb R,z\in\mathbb R,z\geqslant g_0(t)\}=\{(t,z)\mid t\in\mathbb R,z\in\mathbb R,z\geqslant f(x_0+tv_0)\}$. Thus, $\Gamma^+\subset\mathbb R^{d+1}$, $G_0^+\subset\mathbb R^2$, $\pi_0(\Gamma^+)=G_0^+$, and $f$ is a convex function if and only if $\Gamma^+$ is a convex subset of $\mathbb R^{d+1}$. The result is that this happens if and only if every $G_0^+$ is a convex subset of $\mathbb R^{2}$.

Finally, each line $L_0$ defines a hyperplane $P_0$ which may be seen as a slice of $\mathbb R^{d+1}$ cutting the epigraph $\Gamma^+$ through $G_0^+$ thanks to the identification between $P_0$ and $\mathbb R^2$ provided by $\pi_0$. The convexity of $f$ is defined through its behaviour on the lines only, hence $f$ is a convex function if and only if $\Gamma^+$ is a convex set if and every if every $G_0^+$ is a convex set if and only if every $g_0$ is a convex function.

2

By definition, a function $f:\Omega\to{\mathbb R}$ on a convex domain $\Omega\subset{\mathbb R}^n$ is convex if for any two points $x$, $y\in\Omega$ and any $\tau\in[0,1]$ one has $$f\bigl((1-\tau)x+\tau y\bigr)\leq(1-\tau) f(x)+\tau f(y)\ .$$ As this condition involves only two points $x$, $y\in\Omega$ and the points on the segment $[x,y]$ at a time, it can be rewritten as a condition on pullbacks $$g(t):=f(x+ t v)\qquad (x\in\Omega, v\in{\mathbb R}^n)$$ (imagine $v:=y-x$). Such pullbacks should be convex as a function of $t$ for all choices of $x\in\Omega$ and $v\in{\mathbb R}^n$.

0

Let us consider $f(x,y) = x^2+y^4$ defined on $\mathbb R^2$. To claim that $f$ is convex, we mean that for any $(x,y), (u,v)$, the function $$ g(t) := (x+tu)^2+(y+tv)^4 $$ is a convex function of one variable. No matter what starting point $(x,y)$ you choose, and no matter what direction $(u,v)$ you choose, you get a convex function.

  • 0
    Lets make it simple. Suppose a convex function f(x) = x^2. What could be the g(t) in this case? I mean what is the relation of g(t) and f(x)? Where does this function g(t) lie. I mean does it lie on the surface of function f(x).2012-06-17
  • 0
    $g$ is a function of one real variable. In all these cases. $f$ is a function of $n$ real varaiables. If $f(x) = x^2$ is a function of one real variable, what do we get? We get lots of functions $g$, namely all functions of the form $g(t) = (a+bt)^2$.2012-06-17