MM algorithm

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.[4] The same concept continued to reappear in different areas in different forms. In 2000, Hunter and Lange put forth "MM" as a general framework.[5] Recent studies have applied the method in a wide range of subject areas, such as mathematics, statistics, machine learning and engineering.

MM 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 ${\displaystyle f(\theta )}$ be the objective concave function to be maximized. At the m step of the algorithm, ${\displaystyle m=0,1...}$, the constructed function ${\displaystyle g(\theta |\theta _{m})}$ will be called the minorized version of the objective function (the surrogate function) at ${\displaystyle \theta _{m}}$ if

${\displaystyle g(\theta |\theta _{m})\leq f(\theta ){\text{ for all }}\theta }$

${\displaystyle g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

Then, maximize ${\displaystyle g(\theta |\theta _{m})}$ instead of ${\displaystyle f(\theta )}$, and let

${\displaystyle \theta _{m+1}=\arg \max _{\theta }g(\theta |\theta _{m})}$

The above iterative method will guarantee that ${\displaystyle f(\theta _{m})}$ will converge to a local optimum or a saddle point as m goes to infinity.[6] By the above construction

${\displaystyle f(\theta _{m+1})\geq g(\theta _{m+1}|\theta _{m})\geq g(\theta _{m}|\theta _{m})=f(\theta _{m})}$

The marching of ${\displaystyle \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.

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.