Using Convexity

There are two major ways in which we use convexity in majorization.

First, we can use the definition of convex functions directly. Thus we rely on the inequality $$f(\sum_{i=1}^n w_ix_i)\geq\sum_{i=1}^n w_if(x_i),$$ where the $w_i$ are non-negative weights adding up to one. This inequality separates the variables, in the sense that it allows us to substitute a sum of univariate functions for a multivariate one.

Second, we can use the results on the derivatives of convex functions. If $f$ is convex, then $$f(x)\geq f(y)+z'(x-y),$$ with $z\in\partial f(y),$ the subgradient of $f$ at $y.$ Thus convex functions have a linear minorizer. In the same way concave functions have a linear majorizer.