Sharp Quadratic Majorization

A quadratic function $$g(x)=c+b(x-y)+\frac12 a (x-y)^2$$ majorizes $f$ in $y$ if and only if $c=f(y)$, $b=f'(y)$, and $$a\geq A(y)\mathop{=}\limits^{\Delta}\sup_{x\not= y}\delta(x|y),$$ where $$\delta(x|y)\mathop{=}\limits^{\Delta}\frac{f(x)-f(y)-f'(y)(x-y)}{\frac12 (x-y)^2}.$$ We find the best quadratic majorization of $f$ in $y$ by choosing $a=A(y)$.

To study the relation between $f$ and its quadratic majorizers more in depth, we define $\phi:\mathbb{R}^3\Rightarrow\mathbb{R}$ and $\delta:\mathbb{R}^3\Rightarrow\mathbb{R}$ by $$\phi(x,y,a)\mathop{=}\limits^{\Delta}f(y)+f'(y)(x-y)+\frac12 a(x-y)^2$$ and $\delta(x,y,a)\mathop{=}\limits^{\Delta}f(x)-\phi(x,y,a)$. We also define slices of these functions, using bullets. Thus, for example, $\phi(\bullet,y,a)$ is a function of a single variable, with $y$ and $a$ fixed at unique values.

Now $\phi(\bullet,y,a)\gtrsim f(x)$ if and only if $\delta(x,y,a)\leq 0$ for all $x,$ which is true if and only if $\delta^\star(y,a)=0,$ where $$\delta^\star(y,a)\mathop{=}\limits^{\Delta}\sup_x\delta(x,y,a).$$ Note that $\delta(y,y,a)=0$, and thus generally $\delta^\star(y,a)\geq 0$.

Because $\delta(x,y,\bullet)$ is linear in $a$, we see that $\delta^\star(y,\bullet)$ is convex. In other words, $$\mathcal{A}(y)\mathop{=}\limits^{\Delta}\{a\mid\delta^\star(y,a)\leq 0\}$$ is an interval, which may be empty. Now $\phi(\bullet,y,a)\gtrsim_y f(x)$ if and only if $a\in\mathcal{A}(y)$. If $\mathcal{A}(y)=\emptyset$ then no quadratic majorization exists.

Since $a\in\mathcal{A}(y)$ implies $b\in\mathcal{A}(y)$ for all $b\geq a$, we see that $\mathcal{A}(y)$ is either empty, or an interval of the form $[a_\star(y),+\infty)$ or $(a_\star(y),+\infty)$, with $$a_\star(y)\mathop{=}\limits^{\Delta}\inf_a\mathcal{A}(y).$$ If $\mathcal{A}(y)=\emptyset$ we set $a_\star(y)=+\infty$. The majorization function $\phi(\bullet,y,a_\star(y))$ is called the sharpest quadratic majorization of $f$ at $y$ [De Leeuw and Lange, 2009].

Now $$\delta'(x)=f'(x)-f'(y)-a(x-y),$$ and $$\delta''(x)=f''(x)-a.$$ We see that $\delta$ is concave if $a\geq\sup_x f''(x)$. Moreover $\delta$ is increasing if $\delta'\geq 0$, i.e. if $$\frac{f'(x)-f'(y)}{x-y}\begin{cases}\geq a&{ \text{if}\ }x>y\\\leq a&{ \text{if}\ }x<y\end{cases}$$ for all $x$.

Thus if $\delta$ has a maximum at $\hat x$ we must have $$a=\frac{f'(\hat x)-f'(y)}{\hat x - y},$$ as well as $$a\geq f''(\hat x).$$ At the maximum $$\delta(\hat x)=f(\hat x)-f(y)-\frac12(f'(\hat x)+f'(y)).$$