algoritmo MM

El algoritmo MM es un método de optimización iterativo que explota 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 maximización de expectativas puede tratarse como un caso especial del algoritmo MM. ^{[1] [2]} Sin embargo, en el algoritmo EM generalmente están 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 realizaban estudios relacionados con los métodos de búsqueda de líneas . ^[4] El mismo concepto continuó 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 necesaria ]}

Algoritmo

algoritmo MM

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

Tomando la versión de minorización-maximización, sea la función cóncava objetivo a maximizar. En el paso m del algoritmo, la función construida se llamará 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, maximice en lugar de y deje que ${\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 llegue 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 el funcionamiento de las funciones sustitutas y 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

• La 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 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 de 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: Académico. págs. 253-255. ISBN 9780898719468.
5. Cazador, 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.