  Block majorization-minimization (BMM) is a simple iterative algorithm for
nonconvex constrained optimization that sequentially minimizes majorizing
surrogates of the objective function in each block coordinate while the other
coordinates are held fixed. BMM entails a large class of optimization
algorithms such as block coordinate descent and its proximal-point variant,
expectation-minimization, and block projected gradient descent. We establish
that for general constrained nonconvex optimization, BMM with strongly convex
surrogates can produce an $\epsilon$-stationary point within
$O(\epsilon^{-2}(\log \epsilon^{-1})^{2})$ iterations and asymptotically
converges to the set of stationary points. Furthermore, we propose a
trust-region variant of BMM that can handle surrogates that are only convex and
still obtain the same iteration complexity and asymptotic stationarity. These
results hold robustly even when the convex sub-problems are inexactly solved as
long as the optimality gaps are summable. As an application, we show that a
regularized version of the celebrated multiplicative update algorithm for
nonnegative matrix factorization by Lee and Seung has iteration complexity of
$O(\epsilon^{-2}(\log \epsilon^{-1})^{2})$. The same result holds for a wide
class of regularized nonnegative tensor decomposition algorithms as well as the
classical block projected gradient descent algorithm. These theoretical results
are validated through various numerical experiments.
