II.1.1: Introduction

The next step (history again) was to find systematic ways to do augmentation (which is an art, remember). We start with examples.

An early occurrence of majorization, in the specific context of finding a suitable step size for descent methods, is in Ortega and Rheinboldt [1970, p 253-255]. They call this approach the Majorization Principle, which exists alongside other step size principles such as the Curry-Altman Principle, the Goldstein Principle, and the Minimization Principle.

Suppose we have a current solution $x^{(k)}$ and a descent direction $p^{(k)}$. Consider the function $$g(\alpha):=f(x^{(k)}-\alpha p^{(k)}).$$ Suppose we can find a function $h$ such that $g(\alpha)\leq h(\alpha)$ for all $0<\alpha<\overline{\alpha}$ and such that $g(0)=h(0)$. Now set $$\alpha^{(k)}:=\mathop{\mathbf{argmin}}_{0\leq\alpha\leq\overline{\alpha}}h(\alpha).$$ Then the sandwich inequality says $$g(\alpha^{(k)})\leq h(\alpha^{(k)})\leq h(0)=g(0),$$ and thus $f(x^{(k)}-\alpha^{(k)}p^{(k)})\leq f(x^{(k)}).$

Ortega and Rheinboldt point out that if the derivative of $f$ is Hölder continuous, i.e. if for some $0<\lambda\leq 1$ $$\|\mathcal{D}f(x)-\mathcal{D}f(y)\|\leq\gamma\|x-y\|^\lambda,$$ then we can choose $$h(\alpha)=h(0)-\alpha\langle p^{(k)},\mathcal{D}f(x^{(k)})\rangle+\frac{\gamma}{1+\lambda}(\alpha\|p^{(k)}\|)^{1+\lambda},$$ which implies $$\alpha^{(k)}=\frac{1}{\|p^{(k)}\|}\left[\frac{\langle p^{(k)},\mathcal{D}f(x^{(k)})\rangle}{\gamma\|p^{(k)}\|}\right]^{\frac{1}{\lambda}}.$$