Algoritmo MM

El algoritmo MM es un método de optimización iterativo que aprovecha la convexidad de una función para encontrar sus máximos o mínimos. MM significa “Mayorizar-Minimizar” o “Minorizar-Maximizar”, dependiendo de si la optimización deseada es una minimización o una maximización. A pesar del nombre, MM en sí no es un algoritmo, sino una descripción de cómo construir un algoritmo de optimización .

El algoritmo de expectativa-maximización puede considerarse un caso especial del algoritmo MM. ^{[1] [2]} Sin embargo, en el algoritmo EM suelen estar involucradas expectativas condicionales , mientras que en el algoritmo MM la convexidad y las desigualdades son el foco principal, y es más fácil de entender y aplicar en la mayoría de los casos. ^[3]

Historia

La base histórica del algoritmo MM se remonta al menos a 1970, cuando Ortega y Rheinboldt estaban realizando estudios relacionados con los métodos de búsqueda lineal . ^[4] El mismo concepto siguió reapareciendo en diferentes áreas en diferentes formas. En 2000, Hunter y Lange propusieron "MM" como marco general. ^[5] Estudios recientes ^{[ ¿quién? ]} han aplicado el método en una amplia gama de áreas temáticas, como matemáticas , estadística , aprendizaje automático e ingeniería . ^{[ cita requerida ]}

Algoritmo

Algoritmo MM

El algoritmo MM funciona encontrando una función sustituta que minorice o aumente la función objetivo. La optimización de la función sustituta mejorará el valor de la función objetivo o lo dejará sin cambios.

Tomando la versión de maximización-minorización, sea la función cóncava objetivo que se maximizará. En el paso m del algoritmo, , la función construida se llamará la versión minorizada de la función objetivo (la función sustituta) en si ${\displaystyle f(\theta )}$ ${\displaystyle m=0,1...}$ ${\displaystyle g(\theta |\theta _{m})}$ ${\displaystyle \theta _{m}}$

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

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

Luego, maximiza en lugar de , y deja ${\displaystyle g(\theta |\theta _{m})}$ ${\displaystyle f(\theta )}$

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

El método iterativo anterior garantizará que convergerá a un óptimo local o un punto de silla cuando m tiende al infinito. ^[6] Por la construcción anterior ${\displaystyle f(\theta _{m})}$

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

En la figura se muestra la marcha de las funciones sustitutas en relación con la función objetivo. ${\displaystyle \theta _{m}}$

Mayorizar-Minimizar es el mismo procedimiento pero con un objetivo convexo a minimizar.

Construyendo la función sustituta

Se puede utilizar cualquier desigualdad para construir la versión mayorizada/minorizada deseada de la función objetivo. Las opciones típicas incluyen

• Desigualdad de Jensen
• Desigualdad de convexidad
• Desigualdad de Cauchy-Schwarz
• Desigualdad de medias aritméticas y geométricas
• Mayorización/mininorización cuadrática mediante la expansión de Taylor de segundo orden de funciones dos veces diferenciables con curvatura acotada.

Referencias

1. Lange, Kenneth. "El algoritmo MM" (PDF) .
2. Lange, Kenneth (2016). Algoritmos de optimización MM . SIAM. doi :10.1137/1.9781611974409. ISBN. 978-1-61197-439-3.
3. Lange, K.; Zhou, H. (2022). "Un legado de algoritmos EM". Revista estadística internacional . 90 : S52–S66. doi :10.1111/insr.12526. PMC 10191373 . 
4. Ortega, JM; Rheinboldt, WC (1970). Soluciones iterativas de ecuaciones no lineales en varias variables . Nueva York: Academic. pp. 253–255. ISBN. 9780898719468.
5. Hunter, DR; Lange, K. (2000). "Regresión cuantil mediante un algoritmo MM". Revista de estadística computacional y gráfica . 9 (1): 60–77. CiteSeerX 10.1.1.206.1351 . doi :10.2307/1390613. JSTOR  1390613. 
6. Wu, CF Jeff (1983). "Sobre las propiedades de convergencia del algoritmo EM". Anales de estadística . 11 (1): 95–103. doi : 10.1214/aos/1176346060 . JSTOR  2240463.