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 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