MM algorithm

Quality 0.50 · 1 view · Updated 2 months ago

Iterative optimization method

title: "MM algorithm" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["optimization-algorithms-and-methods"] description: "Iterative optimization method" topic_path: "technology/algorithms" source: "https://en.wikipedia.org/wiki/MM_algorithm" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Iterative optimization method ::

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. Despite the name, MM itself is not an algorithm, but a description of how to construct an optimization algorithm.

The expectation–maximization algorithm can be treated as a special case of the MM algorithm.{{cite book |last1=Lange |first1=Kenneth |title=MM Optimization Algorithms |publisher=SIAM |year=2016 |doi=10.1137/1.9781611974409 |isbn=978-1-61197-439-3 However, in the EM algorithm conditional expectations are usually involved, while in the MM algorithm convexity and inequalities are the main focus, and it is easier to understand and apply in most cases.{{cite journal |last1=Lange|first1=K. |last2=Zhou|first2=H. |title=A legacy of EM algorithms |journal=International Statistical Review |year=2022 |volume=90 |issue=Suppl 1 |pages=S52–S66 |doi=10.1111/insr.12526 |pmid=37204987 |pmc=10191373

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 |last1=Ortega |first1=J.M. |last2=Rheinboldt|first2=W.C. |title=Iterative Solutions of Nonlinear Equations in Several Variables |location=New York |publisher=Academic |year=1970 |pages=253–255 |url=https://archive.org/details/iterativesolutio0000orte |url-access=registration |isbn=9780898719468 |last1=Hunter|first1=D.R. |last2=Lange|first2=K. |title=Quantile Regression via an MM Algorithm |journal=Journal of Computational and Graphical Statistics |year=2000 |volume=9 |issue=1 |pages=60–77 |doi=10.2307/1390613 |jstor=1390613 |citeseerx=10.1.1.206.1351

Algorithm

::figure[src="https://upload.wikimedia.org/wikipedia/commons/c/cc/Mmalgorithm.jpg" caption="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 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

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

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

optimization-algorithms-and-methods