Nesterov Majorization

Suppose $f$ is a function with third derivatives that are bounded in the sense that $$\langle\mathcal{D}^3f(x),(x-y)^3\rangle\leq K_3\|x-y\|^3.\tag{1}$$ It is sufficient for this that the Hessian is Lipschitz continuous with Lipschitz constant $K_3$. Majorization based on $(1)$ was first discussed in an important article by Nesterov and Polyak [2006]

Under these conditions we have the majorizer $$g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\frac12(x-y)'\mathcal{D}^2f(y)(x-y)+\frac16K_3\|x-y\|^3.$$ The term $\|x-y\|^3$ is convex in $x$, but the majorizer $g$ itself is generally not convex, although it is convex whenever $f$ is. Majorizer $g$ has continuous first derivatives $$\mathcal{D}_1g(x,y)=\mathcal{D}f(y)+\mathcal{D}^2f(y)(x-y)+\frac12K_3\|x-y\|(x-y),$$ and for $x\not= y$ the second derivative is $$\mathcal{D}_{11}g(x,y)=\mathcal{D}^2f(y)+\frac12K_3\|x-y\|\left(I+\frac{(x-y)(x-y)'}{(x-y)'(x-y)}\right).$$ It follows that $$\mathcal{D}^2f(y)+\frac12K_3\|x-y\|\lesssim\mathcal{D}_{11}g(x,y)\lesssim\mathcal{D}^2f(y)+K_3\|x-y\|,$$ and thus, by the squeeze theorem, $$\lim_{x\rightarrow y}\mathcal{D}_{11}g(x,y)=\mathcal{D}^2f(y).$$