Introduction

As we said, it is desirable that the subproblems in which we minimize the majorization function are simple. One way to guarantee this is to try to find a convex quadratic majorizer. We mostly limit ourselves to convex quadratic majorizers because on $\mathbb{R}^n$ concave ones have no minima and are of little use for algorithmic purposes. Of course on compact sets minimizers of concave quadratics do exist, and may be useful in some circumstances.

A quadratic $g$ majorizes $f$ at $y$ on $\mathbb{R}^n$ if $g(y)=f(y)$ and $g(x)\geq f(x)$ for all $x$. If we write it in the form $$g(x)=f(y)+(x-y)'b+\frac12 (x-y)'A(x-y)$$ then $g(y)=f(y)$. For differentiable $f$ we have in addition $b=\mathcal{D}f(y)$ and for twice-differentiable $f$ we have $A\gtrsim\mathcal{D}f^2(y).$ If we limit ourselves to convex quadratic majorizers, we must also have $A\gtrsim 0$.

We mention some simple properties of quadratic majorizers on $\mathbb{R}^n$.

1. If a quadratic $g$ majorizes a twice-differentiable convex function $f$ at $y$, then $g$ is a convex quadratic. This follows from $g''(y)\geq f''(y)\geq 0$.

2. If a concave quadratic $g$ majorizes a twice-differentiable function $f$ at $y$, then $f$ is concave at $y$. This follows from $0\geq g''(y)\geq f''(y)$.

3. Quadratic majorizers are not necessarily convex. In fact, they can even be concave. Take $f(x)=-x^2$ and $g(x)=-x^2+\frac12(x-y)^2$.}

4. For some functions quadratic majorizers may not exist. Suppose, for example, that $f$ is a cubic. If $g$ is quadratic and majorizes $f$, then we must have $d=g-f\geq 0$. But $d=g-f$ is a cubic, and thus $d<0$ for at least one value of $x$.

5. Quadratic majorizers may exist almost everywhere, but not everywhere. Suppose, for example, that $f(x)=|x|$. Then $f$ has a quadratic majorizer at each $y$ except for $y=0$. If $y\not= 0$ we can use, following Heiser [1986], the arithmetic mean-geometric mean inequality in the form $$\sqrt{x^{2}y^{2}}\leq\frac{1}{2}(x^{2}+y^{2}),$$ and find $$|x|\leq\frac{1}{2|y|}x^{2}+\frac{1}{2}|y|.$$ If $g$ majorizes $|x|$ at 0, then we must have $ax^{2}+bx\geq |x|$ for all $x\not= 0$, and thus $a|x|+b\mathbf{sign}(x)\geq 1$ for all $x\not= 0$. But for $|x|<\frac{1+|b|}{a}$ and $\mathbf{sign}(x) = -\mathbf{sign}(b)$, we have $a|x|+b\,\mathbf{sign}(x)<1$.