2
$\begingroup$

Let $V : \mathbb{R}^n \rightarrow \mathbb{R}$ be (strictly) convex and continuously differentiable on $\mathbb{R}^n$. Show that for any $y \in \mathbb{R}^n$ and any $x \in \mathbb{R}^n$ $$ V(y) \geq V(x) + \nabla V(x)^\top(y-x) $$ For $n=1$ this implies that for any $x \in \mathbb{R}$ and for any $y \in \mathbb{R}$, $V(y)$ lies above the tangent line to $V$ at $x$.

$\endgroup$
  • $\begingroup$ What is your definition of convexity? $\endgroup$ – J.R. Feb 8 '14 at 18:26
  • $\begingroup$ You can reduce this to the onedimensional case by considering only the line through $x$ and $y$. Notice that $\nabla V(x)^T (y-x)$ is a directional derivative. $\endgroup$ – Christoph Feb 8 '14 at 18:27
2
$\begingroup$

$ \newcommand\R{\mathbb R} \newcommand\x{\mathbf x} \newcommand\y{\mathbf y} $Let $\gamma\colon\R\to\R^n$ be the curve defined by $t\mapsto \x+t(\y-\x)$, which is a straight line through $\gamma(0)=\x$ and $\gamma(1)=\y$. Further define $\widetilde V=V\circ \gamma:\R\to\R$.

Since $V\colon\R^n\to\R$ is differentiable, \begin{align} \nabla V(\x)\cdot (\y-\x) &= \lim_{h\to 0} \frac{V(\x+h(\y-\x))-V(\x)}{h} \\&= \lim_{h\to 0} \frac{V(\gamma(h))-V(\gamma(0))}{h} = \widetilde V'(0). \end{align}

Thus, your inequality can be expressed as $$ \widetilde V(1) \ge \widetilde V(0) + \widetilde V'(0). $$

It is easy to check that $\widetilde V$ is convex given that $V$ is convex.

After this, we have reduced everything to the claim foir $n=1$, $x=0$ and $y=1$.

Since $\widetilde V$ is convex, for all $t\in(0,1)$ we have $$ \widetilde V(t) \le (1-t) \widetilde V(0) + t\widetilde V(1) $$ which is equivalent to $$ \widetilde V(0) + \frac{\widetilde V(t)-\widetilde V(0)}{t} \le \widetilde V(1). $$ Letting $t\to 0$ gives the desired inequality.

$\endgroup$
1
$\begingroup$

This is true for any differentiable convex function. Let $f(t) = V(x + t (y-x))$ for $t \in [0,1]$.

First we establish an essentially equivalent (and fundamental) result that applies to all finite-valued convex functions: Suppose $x<y$, and let $R(x,y) = { f(x)-f(y) \over x-y }$. Then if $r < s<t$, we have $R(s,r) \le R(t,s)$.

To see this, note that if $s = \lambda t + (1-\lambda) r$, then $f(s) \le \lambda f(t) + (1-\lambda) f(r)$, or equivalently, $0 \le \lambda (f(t)-f(s)) + (1-\lambda) (f(r)-f(s))$. Since $\lambda = {s-r \over t-r}$ and $1-\lambda = { t-s \over t-r}$, substituting gives the result.

Now let $s = r+h$, where $0 < h < t-r$, then taking limits as $h \downarrow 0$ shows that $f'(r) \le R(t,r)$, or $f(t) \ge f(r) + f'(r) (t-r)$.

Choosing $t=1, r=0$ and noting that $f'(0) = \langle \nabla V(x), y-x \rangle$ yields the desired result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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