Sub-level Majorization

Stability of the majorization algorithm is guaranteed by the sandwich inequality, which says that $$f(x^{(k+1)})\leq g(x^{(k+1)},x^{(k)})\leq g(x^{(k)},x^{(k)})=f(x^{(k)}).$$ The first inequality in the chain comes from the majorization condition $f(x)\leq g(x,y)$ for all $x,y\in X$. There is, however, a weaker condition which still implies the same inequality.

Suppose that we merely require that the majorization function $g$ satisfies $$g(x,y)\leq g(y,y)\Rightarrow f(x)\leq g(x,y).$$ Then we still have $g(x^{(k+1)},x^{(k)})\leq g(x^{(k)},x^{(k)})=f(x^{(k)})$, and as a consequence also $f(x^{(k+1)})\leq g(x^{(k+1)},x^{(k)})$. The sandwich inequality still applies.

The weaker localized majorization condition, which we will call sublevel majorization (or simply S-majorization) from now on, says that $g$ majorizes $f$ on the sublevel set $$\mathcal{L}(y)\mathop{=}\limits^{\Delta}\{x\in X\mid g(x,y)\leq g(y,y)=f(y)\},$$ while for $x\not\in\mathcal{L}(y)$ we can have $f(x)>g(x,y)$. In other words, $g(x,y)-f(x)$ must have a global minimum equal to zero on $\mathcal{L}(y)$ at $y$.

S-majorization is easy to visualize for a univariate quadratic majorizer $$g(x,y)=f(y)+f'(y)(x-y)+\frac12 a(x-y)^2,$$ which has $g(x,y)\leq f(y)$ if $x$ is in the interval with end-points $y$ and $y-\frac{2f'(y)}{a}$. For quadratic S-majorization of a cubic $f$, for example, we must have $$a\geq f''(y)+\frac13 f'''(y)(x-y)$$ at both end-points of the interval $I(y)$, which means we must have both $a\geq f''(y)$ and $$a^2-af''(y)+\frac23 f'''(y)f'(y)\geq 0.\tag{1}$$ If the quadratic $\text{(1)}$ has no real roots, or two equal real roots, then it is always non-negative, and we have sub-level majorization of the cubic at $y$ if $a\geq f''(y)$. Now suppose the quadratic $\text{(1)}$ has two different real roots, say $p(y)<q(y)$. We have $p(y)+q(y)=f''(y)$. Thus if $p(y)$ and $q(y)$ are non-negative, then $0\leq p(y)\leq q(y)\leq f''(y)$, and we have sub-level majorization for $a\geq f''(y)$. If $p\leq 0$ and $q\geq 0$ then $q=f''(y)-p\geq f''(y)$ and thus $a\geq q(y)$. If both $p(y)\leq 0$ and $q(y)\leq 0$ then $f''(y)\leq p(y)<q(y)\leq 0$, and thus $\overline{a}(y)=0$ and sub-level majorization is linear.

Near a local minimum, where $f''(y)\geq 0$ and $f'(y)$ is close to zero, the two roots of the quadratic are approximately $q=f''(y)-\frac23 f'(y)$ and $p=\frac23 f'(y)$.

note: 030615 Add the example from the paper and the reference

Quadratic sub-level majorization in the multivariate case. We have $$g(x,y)=f(y)+(x-y)'\mathcal{D}f(y)+\frac12(x-y)'A(x-y)$$ for some $A$ which we assume to be positive definite for now. Then $g(x,y)\leq f(y)$ if and only if $$(x-z)'A(x-z)\leq (\mathcal{D}f(y))'A^{-1}\mathcal{D}f(y),$$ with $z=y-A^{-1}\mathcal{D}f(y)$. For given $y$ and $A$ this means $x$ must be in an ellipse centered at $z$, but note that if $A$ changes then shape, radius, and center of the ellipse change.

If $A=aH$ with $H$ fixed, then we have the more manageable inequality $$\frac{1}{a^2}\geq \frac{(x-z)'H(x-z)}{(\mathcal{D}f(y))'H\mathcal{D}f(y)}$$