MM Algorithm

Definition

The MM algorithm is an iterative optimization method which exploits the convexity of a function in order to find its maxima or minima. The MM stands for Majorize-Minimization or Minorize-Maximization, depending on whether the desired optimization is a minimization or a maximization.

The MM algorithm works by finding a surrogate function that minorizes or majorizes the objective function. Optimizing the surrogate function will monotonically improve the value of the objective function.

Algorithm

Consider Minorize-Maximization algorithm for a maximization problem of a function $f(\theta )$.

1. Find a surrogate function $g(\theta |{\theta }_m)$ (minorized $f(\theta )$) satisfying:
   • $\forall \theta ,g(\theta |{\theta }_m)\le f(\theta )$
   • $g(\theta |{\theta }_m)=f({\theta }_m)$
2. Find a point maximizes the surrogate function ${\theta }_{m+1}=\underset{\theta }{\mathrm{argmax}}g(\theta |{\theta }_m)$ Then, $f({\theta }_m)=g({\theta }_m|{\theta }_m)\le g({\theta }_{m+1}|{\theta }_m)\le f({\theta }_{m+1})$
3. Use the maximum point ${\theta }_{m+1}$ as the next point.
4. Re-evaluate the surrogate function $g(\theta |{\theta }_{m+1})$ at the new point ${\theta }_{m+1}$ and repeat Iteration until convergence to a (local) maximum.