Second Order

We can take this one step further. Obviously $f(x)\leq f(y)+(x-y)'\nabla f(y)+ \frac{1}{2}\sup_{0\leq\lambda\leq 1} (x-y)'\nabla^2f(y+\lambda(x-y)) (x-y).$ The main problem with these approaches based on the mean value theorem is that the majorizing function may not be simple. Nevertheless the approach can also be used to arrive at bounds which are computationally convenient.

For a univariate cubic $f(x)=a+bx+\frac12 cx^2+\frac16 dx^3$ we find the majorization $\begin{multline*} f(x)\leq f(y)+f'(y)(x-y)+\frac12(x-y)^2\max_{0\leq\lambda\leq 1}\left(c+ d(x+\lambda(y-x))\right)=\\=f(y)+f'(y)(x-y)+\frac12(x-y)^2 \begin{cases} c+d\max(x,y)&\text{ if }d\geq 0,\\ c+d\min(x,y)&\text{ if }d\leq 0,\\ \end{cases} \end{multline*}$

For the exponent $\begin{multline*} \exp(x)\leq \exp(y)+\exp(y)(x-y)+\frac12 (x-y)^2\sup_{0\leq\lambda\leq 1}\exp(y+\lambda(x-y))=\\ =\exp(y)+\exp(y)(x-y)+\frac12 (x-y)^2\exp(\max(x,y)) \end{multline*}$

For the folium with $f(x)=x_1^3+x_2^3-3x_1^{\ }x_2^{\ }$ we have $\mathcal{D}^2f(x)=\begin{bmatrix}6x_1&-3\\-3&6x_2\end{bmatrix}.$ Thus a simple majorizer is given by (incorrect 03/03/15) $g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\max(x_1,x_2)(x-y)'V(x-y),$ with $V=\begin{bmatrix}6&-3\\-3&6\end{bmatrix}.$

NB: see probit section for $f''(x)$ decreasing. 03/03/15