MM algorithm

History

The historical basis for the MM algorithm can be dated back to at least 1970, when Ortega and Rheinboldt were performing studies related to line search methods.{{cite book |url-access=registration |isbn=9780898719468

Algorithm

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

Taking the minorize-maximization version, let f(\theta) be the objective concave function to be maximized. At the m step of the algorithm, m=0,1... , the constructed function g(\theta|\theta_m) will be called the minorized version of the objective function (the surrogate function) at \theta_m if

: g(\theta|\theta_m) \le f(\theta) \text{ for all } \theta : g(\theta_m|\theta_m)=f(\theta_m)

Then, maximize g(\theta|\theta_m) instead of f(\theta) , and let

: \theta_{m+1}=\arg\max_{\theta}g(\theta|\theta_m)

The above iterative method will guarantee that f(\theta_m) will converge to a local optimum or a saddle point as m goes to infinity. By the above construction : f(\theta_{m+1}) \ge g(\theta_{m+1}|\theta_m) \ge g(\theta_m|\theta_m)= f(\theta_m)

The marching of \theta_m and the surrogate functions relative to the objective function is shown in the figure.

Majorize-Minimization is the same procedure but with a convex objective to be minimised.

Constructing the surrogate function

One can use any inequality to construct the desired majorized/minorized version of the objective function. Typical choices include

• Jensen's inequality
• Convexity inequality
• Cauchy–Schwarz inequality
• Inequality of arithmetic and geometric means
• Quadratic majorization/mininorization via second order Taylor expansion of twice-differentiable functions with bounded curvature.

References

References

1. Lange, Kenneth. "The MM Algorithm".
2. Wu, C. F. Jeff. (1983). "On the Convergence Properties of the EM Algorithm". [[Annals of Statistics]].