3
$\begingroup$

Let $f: \mathbb{R}\rightarrow\mathbb{R}$ be a twice-differentiable convex function. It can shown be that for any $x_0 \in \mathbb{R}$:

$f(x) \leq f(x_0) + (x-x_0)f'(x_0) + \frac{(x-x_0)^2}{2}$C

where $C = \arg \max_x f''(x)$ is the maximum curvature of $f(x)$ over its domain. This result has been proven here:

Bohning, D. and Lindsay, B.G., ``Monotonicity of quadratic-approximation algorithms'', Annals of the Institute of Statistical Mathematics, vol. 40, no. 4, pp. 641-663, 1988.

Is it possible to derive a quadratic lower bound as well using a similar idea? It seems intuitively possible with a small enough choice of curvature in the bound.

  • 4
    This is nothing more than Taylor's theorem with bounds on the second derivative. So the answer to your question is yes, with the exception that the lower bound may be 0 (eg, $f(x) = x$). – 2012-08-04

2 Answers 2

4

To elaborate on my comment, suppose $f: \mathbb{R}^n \to \mathbb{R}$ is $C^2$. Then Taylor's theorem gives $f(x) = f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \int_0^1 (1-t) (x-x_0)^T \frac{\partial^2 f (x_0+t (x-x_0))}{\partial x^2} (x-x_0) \, dt .$ Now suppose that $m \leq \frac{\partial^2 f (x)}{\partial x^2} \leq M$ on some convex set $K \subset \mathbb{R}^n$. Then is is easy to see that if $x,x_0 \in K$, then $f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \frac{m}{2} \|x-x_0\|^2 \leq f(x) \leq f(x_0) + \frac{\partial f (x_0)}{\partial x} (x-x_0) + \frac{M}{2} \|x-x_0\|^2 .$

This is true for any $f \in C^2$, not just convex $f$. If $f$ happens to be convex, then you know that $m=0$ will serve as a lower bound. By considering the convex function $f(x) = x^4$ near $0$, you can see that even a strictly convex function may have $m=0$ as the 'best' lower bound in some sense.

0

The last answer is correct, and it gives the lower bound. However, the comment about strictly convex can be confusing. If there is a lower bound $m$ on the second derivative, we call the function $m$-convex, and this is equivalent to convexity of $u(x) - mx^2/2$. Then, instead of using Taylor series, you can obtain the same lower bound using the supporting hyperplane condition. This is useful for technical reasons: $m$ convexity can hold without the function having second derivatives everywhere. For more information, see "Semiconcave Functions, Hamilton–Jacobi Equations, and Optimal Control"