Euclidean Metric and Convexity

Question

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

Answer 1

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 \begin{equation} g(t) = f(x + t(y-x)). \end{equation}

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

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

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

Answer 2

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.

Answer 3

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.