II.1.2.2: Majorization on a Set

We can have different majorizations of $f$ on $\mathcal{X}$ at different points $y_1,\cdots,y_n\in\mathcal{X}$. Now consider the situation in which we have a different majorization for each point $y\in\mathcal{X}$.

• $g(x,y)\geq f(x)$ for all $x,y\in\mathcal{X}$,
• $g(y,y)=f(y)$ for all $y\in\mathcal{X}$.

Majorization is strict if the first condition can be replaced by

• $g(x,y)>f(x)$ for all $x,y\in\mathcal{X}$ with $x\not= y$.

Or, equivalently, if the second condition can be replaced by

• $g(x,y)=f(x)$ if and only if $x=y$.

We call $g$ a majorization scheme for $f$ on $\mathcal{X}$, because $g$ automatically gives a majorization for $f$ for every $y\in\mathcal{X}$. Thus a majorization of $f$ on $\mathcal{X}$ at $y$ is a real-valued function $g$ on $\mathcal{X}$, a majorization scheme for $f$ on $\mathcal{X}$ is a real-valued function on $\mathcal{X}\otimes\mathcal{X}$.

Because $g(x,y)\geq g(x,x)=f(x)$ for all $x,y\in\mathcal{X}$ we see that $$f(x)=\min_{y\in\mathcal{X}}g(x,y)$$ for all $x\in\mathcal{X}$. Thus $g$ majorizes $f$ if and only if $f(x)=\min_{y\in\mathcal{X}} g(x,y)$ and the minimum is attained for $y=x.$ Strict majorization means the minimum is unique. It follows that the majorization relation between functions is a special case of the augmentation relation.

As an example of a majorization scheme for $f:x\rightarrow -\log(1+\exp(-x))$ we use $$g(x,y)=f(y)+f'(y)(x-y)+\frac18(x-y)^2.$$ Also define the function $h$ by $h(x,y)=f(x)$.

Functions $g$ is plotted in Figure 1 in blue, function $h$ is in red.

Figure 1: Majorization Scheme for log(1+exp(x)) </center>

Graphs of the intersection of the graphs of $g$ and $h$ with the vertical planes $y=c$ parallel to the $x$-axes at $y=-5,-2,0,2,5$ are in Figure 2. The red lines are the intersections with $h$, i.e. the function $f$, the blue lines are the quadratics majorizing $f$ at $y=-5,-2,0,2,5$.