Generalizations of the quadratic bound optimization principle

Abstract

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 f ( θ ) , the QUB principle is limited by the difficulty of finding a constant positive definite matrix B such that B − d 2 f ( θ ) is positive semidefinite for all θ . This paper proposes a generalization of the QB principle that avoids this limitation. In particular, we construct QUB algorithms by replacing the matrix B by a continuous matrix-valued function B n ( θ ) that dominates the Hessian d 2 f ( θ ) and depends on the both the current iterate θ n and the next potential iterate θ . In practice, we require B n ( θ ) to be diagonal with its diagonal entries separated in θ . In other words, the i th diagonal entry of B n ( θ ) depends on θ only through its i th entry θ i . 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.