Generalizations of the quadratic bound optimization principle

The quadratic bound (QB) principle proposed by Böhning and Lindsay in 1988 is an important special case of the majorization-minimization or minorization-maximization optimization principle. The quadratic upper-bound (QUB) principle is pertinent to minimization; the analogous quadratic lower-bound principle is pertinent to maximization. Unfortunately, in minimizing a loss [Formula: see text], the QUB principle is limited by the difficulty of finding a constant positive definite matrix [Formula: see text] such that [Formula: see text] is positive semidefinite for all [Formula: see text]. This paper proposes a generalization of the QB principle that avoids this limitation. In particular, we construct QUB algorithms by replacing the matrix [Formula: see text] by a continuous matrix-valued function [Formula: see text] that dominates the Hessian [Formula: see text] and depends on the both the current iterate [Formula: see text] and the next potential iterate [Formula: see text]. In practice, we require [Formula: see text] to be diagonal with its diagonal entries separated in [Formula: see text]. In other words, the [Formula: see text]th diagonal entry of [Formula: see text] depends on [Formula: see text] only through its [Formula: see text]th entry [Formula: see text]. Theoretical analysis confirms that this class of generalized QB algorithms enjoys global convergence in favorable circumstances. For the scalar case, the tangency condition that the second derivative equals the bound function at the current point promotes superlinear convergence. Several numerical experiments implemented in Julia illustrate the power of the generalized QB principle.