# Euclidean Metric and Convexity

Question: Consider the Euclidean metric space $(\mathbb{R}^n , \Vert\cdot \Vert)$.

Let $X\subset \mathbb{R}^n$ and $f\colon X \to \mathbb{R}$.

$X$ is said to be a convex set if for every $x,y \in X$ and $t \in (0,1)$, we have $tx+(1-t)y \in X$.

$f$ is said to be a convex function at $x\in X$ if for every $y \in X$ and $t\in(0,1)$, $tx+(1-t)y\in X$ implies $f(tx+(1-t)y) \le tf(x) +(1-y)f(y)$.

$f$ is said to be a convex function if it is a convex function at every $x \in X$.

Prove the following statements:

1. If X is a convex set, then $f\colon X \in \mathbb{R}$ is a convex function iff $\{ (x,y) \in X \times \mathbb{R} \mid f(x) \le y \}$ is a convex set.

2. If $X$ is open in $\mathbb{R}^n$ and $f$ is convex and differentiable at $x \in X$, then $$f(y)-f(x) \ge Df(x)\cdot (y-x)$$ for every $y\in X$, where $Df(x)$ is the derivative of $f(x)$ at $x$.

3. If $X$ is open in $\mathbb{R}^n$ and $f$ is convex and twice differentiable at $x \in X$, then $D^2f(x)$ is positive semidefinite.

EDIT :

I am deleting how I tried Part 1 as I got my mistake and now it is solved.

Part 2 and Part 3 are still unsolved

-
It was asked in an exam in the year 2006. the first part is being asked again and again and I am clueless. – Mathy Jun 23 '13 at 10:36

For parts 2) and 3), we can use the trick of reducing to the case where we have a convex function of a single variable. Let $y \in X$, and introduce the convex function $g:[0,1] \to \mathbb R$ defined by $$g(t) = f(x + t(y-x)).$$

2) Because $g$ is a function of a single variable, it's easy to show that $$g'(0) \leq g(1) - g(0).$$

By the chain rule, $g$ is differentiable and $$g'(0) = Df(x)(y-x).$$ This shows that $$Df(x)(y-x) \leq f(y) - f(x).$$

3) Because $g$ is a function of a single variable, it's easy to show that $$g''(0) \geq 0.$$ By the chain rule, $$g''(0) = (y-x)^T D^2f(x) (y - x).$$ We see that $$(y-x)^T D^2f(x) (y-x) \geq 0$$ for all $y \in X$. It follows that $D^2f(x)$ is positive semi-definite.

-
and how to show that $g'(0) \le g(1) -g(0)$ and $g''(0) \ge 0$ ?? – Mathy Jun 25 '13 at 22:41
$g'(0) \leq g(1) - g(0)$ becomes very plausible if you draw a picture. (And the picture can be made into a rigorous proof.) A picture also makes it seem clear that $g'(t)$ is increasing on $[0,1]$, which implies that $g''(0) \geq 0$. (Again the picture can be made into a rigorous proof.) To prove these things, you can start by showing that $a < b < c$ implies $\frac{g(b) - g(a)}{b-a} \leq \frac{g(c) - g(b)}{c - b}$ (which also seems plausible when you draw a picture). – littleO Jun 25 '13 at 22:50
To prove $\frac{g(b) - g(a)}{b-a} \leq \frac{g(c) - g(b)}{c - b}$, let $L$ be the function whose graph is a line segment connecting $(a,g(a))$ and $(c,g(c))$. Note that $\frac{L(b) - g(a)}{b-a} = \frac{g(c) - L(b)}{c - b} = \text{slope of line segment}$. Now $g(b) \leq L(b)$ gives us the desired inequality. (The left side gets smaller and the right side gets larger.) – littleO Jun 25 '13 at 23:15

For the part you're asking about, note that the convexity of $A$ means that $$t(x_0,y_0) + (1-t)(x_1,y_1) \in A$$ whenever $(x_0,y_0) \in A$ and $(x_1,y_1) \in A$, and $t \in [0,1]$. Let $x, y \in X$. To somehow get $f$ into play, note first that $(x,f(x)) \in A$ and $(y,f(y)) \in A$. Then for every $t \in [0,1]$, $$t(x,f(x)) + (1-t)(y,f(y)) = (tx+(1-t)y,tf(x)+(1-t)f(y)) \in A.$$ Writing out the definition of $A$, this says that $$f(tx+(1-t)y) \leq tf(x)+(1-t)f(y),$$ for all $t \in [0,1]$, which means that $f$ is convex.

-
thank you so much. You explained in such a simple way that it appears to be so obvious. Thanx for pointing out my mistake. Please help me with 2nd and 3rd part as well. – Mathy Jun 23 '13 at 11:31
can you please help me with part 2 and 3. may be a hint.. anything please. – Mathy Jun 23 '13 at 18:05

1) Note that the set $\{(X,y)\in X\times \mathbb{R}\,;\, f(x)\leq y\}$ is called the epigraph of $f$. Other than $f$ is convex iff its epigraph is convex (fulglede explained it. I suggest you also draw a picture in the case $X=\mathbb{R}$ to see why this is intuitively clear), we have that $f$ is lower semicontinuous iff its epigraph is closed.

Note: via the introduction of the function $g(t)=f(x_t)$ below, 2) and 3) just amount to the well-known characterizations of convexity in terms of the first and the second derivatives for a real-valued function of the real variable. In other terms, we restrict to two-dimensional sections of the epigraph of $f$, which remain convex. Note that 2) simply says that the (epi)graph is above a tangent plane, when such a tangent plane exists.

2) Fix $y\in X$. Consider the function $g(t)=f((1-t)x+ty)=f(x+t(y-x))$ which is defined on some open interval $I$ containing $[0,1]$, since the segment $[x,y]=\{x_t=x+t(y-x)\,;\,t\in[0,1]\}$ is contained in the open set $X$. By composition and chain rule, $g$ is differentiable at $0$ with $g'(0)=Df_{g(0)}(g'(0))=Df_x(y-x)$.

Now the key remark is that $g$ is convex on $I$. Indeed, for $a,b\in I$ and $t\in [0,1]$ $$x_{(1-t)a+tb}=x+((1-t)a+tb)(y-x)= (1-t)x_a+tx_b$$ which is not surprising in view of the note above, or since $t\longmapsto x_t=x+t(y-x)$ is affine whence preserves barycenters. Therefore, by convexity of $f$, $$g((1-t)a+tb)=f((1-t)x_a+tx_b)\leq (1-t)f(x_a)+tf(x_b)=(1-t)g(a)+tg(b).$$ Now as is well-known, if $g$ is convex then the chord slopes at $0$ are nondecreasing. In particular, if $g$ is differentiable at $0$, we get $$Df_x(y-x)=g'(0)\leq \frac{g(1)-g(0)}{1-0}=f(y)-f(x)\qquad \forall y\in X.$$

3) Fix $y\in X$ again. Now, by composition and chain rule again, $g$ is twice differentiable at $0$, and $g''(0)=D^2f_x(y-x,y-x)$. Since $g$ is convex on $I$ and twice differentiable at $0$, we get $$D^2f_x(y-x,y-x)=g''(0)\geq 0\qquad \forall y\in X.$$ For $y=x+h$ with $h\in\mathbb{R}^n$ sush that $\|h\|$ be small engouh (say $\|h\|\leq r$, where $r>0$ exists because $U$ is open and contains a ball centered at $x$). This yields $D^2f_x(h,h)\geq 0$. Whence $D^2f_x(h,h)=\frac{\|h\|^2}{r^2}D^2f_x(\frac{rh}{\|h\|},\frac{rh}{\|h\|})\geq 0$ for every $h\in\mathbb{R}^n\setminus\{0\}$. That is $D_2f_x$ is positive semidefinite.

-