I'm trying to do an exam question for a Masters level optimisation course.
The question is as follows
Consider the following function: $f(x)=x^{r}(x \in \mathbb{R}) .$ Show that there exists a real number $0<\delta<1, \text { and a natural number } r \text { (i.e } r=1,2, \ldots)$ such that $f$ is convex has a unique global minimum and that the Newton algorithm applied to this function satisfies the following:$$ \ \left|x_{k+1}-x^{\star}\right| \geq(1-\delta)\left|x_{k}-x^{\star}\right| \ $$ Where $x_{k}$ denotes the $k^{t h}$ iterate of the Newton algorithm (you may assume that $\left.x_{0}>0\right)$ and $x^{\star}$ denotes the optimal solution.
Now I think perhaps I am supposed to be finding an example that diverges but is a nice fn. I
I previously thought that if I say r = 2, $ \delta$ = 1/2 that exists and I easily can prove $f(x) = x^2$ has a unique global minimum at $x^{\star}$=0. (positive second derivative so convex, and first = 0 at 0.
Newton's method in the case we are taught, to minimise a fn, is $\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-\nabla^{2} \boldsymbol{f}\left(\boldsymbol{x}_{k}\right)^{-1} \nabla \boldsymbol{f}\left(\boldsymbol{x}_{k}\right)$
In this case 1-D so ${x}_{k+1} = {x}_{k} - {x}_{k} = 0$ . |I really don't think this is what the question was getting at. And looking at it again as $x_0$ > 0, so this wouldn't work anyway.
hint: If Newton's method converges quadratically, then your inequality will probably not hold. Also, there are some nice theorems stating precisely when Newton's method converges quadratically (e.g. the Hessian at that the solution is nonsingular). If these conditions fail, then convergence of Newton's method may be slower. This proof appeals to Banach's fixed point theorem (as suggested earlier), which relies heavily on the inequality you've got above (i.e. showing that your iteration is a Banach contraction). I suggest checking out your book's theorems on the rate of convergence of Newton's method, and using those hypotheses to inform how you could "break" such a result.