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.

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.

share|improve this question
2  
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$). –  copper.hat Aug 4 '12 at 1:03

1 Answer 1

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.

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.