“MM algorithm”的意思、由来-开放百科全书

The MM algorithm is an iterative optimization method which exploits the convexity of a function in order to find their maxima or minima. The MM stands for “Majorize-Minimization” or “Minorize-Maximization”, depending on whether the desired optimization is a maximization or a minimization. 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.^[1]^[2]

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.

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

Algorithm

The MM algorithm works by finding a surrogate function that minorizes or majorizes the objective function. Optimizing the surrogate function will drive the objective function upward or downward until a local optimum is reached.

Taking the minorize-maximization version, let

be the objective concave function to be maximized. At the {{mvar|m}} step of the algorithm,

, the constructed function

will be called the minorized version of the objective function (the surrogate function) at

The above iterative method will guarantee that

will converge to a local optimum or a saddle point as {{mvar|m}} goes to infinity.^[5] By the above construction

The marching of

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

1. ^{{cite web|last=Lange|first=Kenneth|title=The MM Algorithm|url=http://www.stat.berkeley.edu/~aldous/Colloq/lange-talk.pdf}}
2. ^Kenneth Lange: "MM Optimization Algorithms", SIAM, {{ISBN|978-1-611974-39-3}} (2016).
3. ^{{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://books.google.com/books?id=GA1P9UNnrmMC&pg=PA253|isbn=9780898719468 }}
4. ^{{cite journal |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 }}
5. ^{{cite journal |last=Wu |first=C. F. Jeff |year=1983 |title=On the Convergence Properties of the EM Algorithm |journal=Annals of Statistics |volume=11 |issue=1 |pages=95–103 |doi= 10.1214/aos/1176346060|jstor=2240463 }}