Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

3 Answers 3

up vote 2 down vote accepted
+100

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.

share|improve this answer
    
and how to show that $g'(0) \le g(1) -g(0)$ and $g''(0) \ge 0$ ?? –  Mathy Jun 25 '13 at 22:41
1  
$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
1  
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.

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.