Higher Order

From Taylor's theorem with Lagrange form of the remainder discussed in [A:Taylor] it follows that $$f(x)\leq g_p(x,y)+\frac{1}{(p+1)!}\sup_{0\leq\lambda\leq 1}<\mathcal{D}^{p+1}f(x+\lambda(y-x)),(x-y)^{p+1}>,$$ where $g_p$ is the $p-$degree Taylor polynomial at $y$.

If all elements of the array in $\frac{1}{(p+1)!}\mathcal{D}^{p+1}f(x+\lambda(y-x))$ are less than $\kappa$ in absolute value for all $x,y$ and $\lambda$, then this implies $$f(x)\leq g_p(x,y)+\kappa\left\{\sum_{i=1}^n|x_i-y_i|\right\}^{p+1}$$

We can also use the Frobenius norm and Cauchy-Schwartz to obtain $$f(x)\leq g_p(x,y)+\kappa(x,y)\|x-y\|^{p+1},$$ where $$\kappa(x,y)\mathop{=}\limits^{\Delta}\frac{1}{(p+1)!}\sup_{0\leq\lambda\leq 1}\|\mathcal{D}^{p+1}f(x+\lambda(y-x))\|.$$ Of course it remains to be seen if these formulas actually lead to useful majorization algorithms. For higher $p$ they will undoubtedly have fast convergence, but the optimizations in each iteration involve higher order multivaruate polynomials and look pretty daunting.