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]

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

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.

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.