Desde su creación hace más de dos décadas por Daniel Spielman (arriba) y Shang-hua Teng, el análisis suavizado se ha utilizado para analizar el rendimiento de algoritmos distintos del método símplex, incluidos los métodos de punto interior para la programación lineal.
Crédito: Allie Barton
En 1947, el científico matemático George Dantzig inventó el método simplex, un medio poderoso y práctico para encontrar soluciones a la programación lineal para problemas de optimización. Los científicos no perdieron tiempo en utilizar el método simplex en una variedad de aplicaciones en el gobierno, la industria, la ciencia y la ingeniería.
Medio siglo después, cuando Daniel A. Spielman era un Ph.D. estudiante del Instituto Tecnológico de Massachusetts, el método símplex estaba en la cima del panteón de algoritmos importantes. Sin embargo, la investigación había demostrado que el método símplex tenía escollos probados; no debería funcionar tan bien como lo hizo. ¿Que esta pasando?
Spielman resolvió el misterio en 2001, en un trabajo conjunto con Shang-hua Teng, ahora profesor universitario y profesor Seeley G. Mudd de Ciencias de la Computación y Matemáticas en la Escuela de Ingeniería Viterbi de la Universidad del Sur de California. Al ser pioneros en una técnica llamada análisis suavizado, su trabajo brindó una explicación original y convincente del poder del método simplex y sugirió un nuevo paradigma para medir la efectividad de los algoritmos.
Este trabajo fue reconocido en 2008 por el Premio Gödel, patrocinado conjuntamente por el Grupo de Interés Especial en Algoritmos y Teoría de la Computación (SIGACT) de la ACM y la Asociación Europea de Ciencias de la Computación Teórica. Ahora Spielman, profesor de Ciencias de la Computación de Sterling y profesor de Estadística y Ciencia de Datos y de Matemáticas en la Universidad de Yale, ha sido galardonado con el Premio Breakthrough en Matemáticas 2023, en parte por este trabajo de optimización.
Spielman tiene una gran capacidad «para generar nuevos enfoques», dijo Lance Fortnow, decano de la Facultad de Computación del Instituto de Tecnología de Illinois. «No fue como si alguien más hubiera inventado el análisis suavizado y Spielman dijera: ‘Probémoslo en programación lineal’. Esto fue: ‘Quiero entender la programación lineal. ¿Cuál es la forma correcta de hacerlo?'».
Competencia Simplex Bests Polynomial-time
Dantzig formuló el concepto de programación lineal como una forma de modelar problemas de optimización. El modelo produce un poliedro, posiblemente de muy alta dimensión, donde las esquinas representan soluciones. El método simplex proporciona una forma muy eficiente de moverse a lo largo de las aristas del poliedro hacia una esquina óptima. El algoritmo se hizo a la medida de las máquinas informáticas que recién comenzaban a aparecer cuando Dantzig hizo este trabajo.
En la década de 1970, el auge de la teoría de la complejidad aportó nueva precisión al estudio de la eficiencia de los algoritmos. En general, un algoritmo se considera eficiente si se ejecuta en tiempo polinomial, lo que significa que incluso para las entradas del algoritmo en el peor de los casos, el tiempo de ejecución siempre está limitado por una función polinomial del tamaño de entrada. Esto contrasta con los algoritmos cuyo tiempo de ejecución puede aumentar exponencialmente con el tamaño de entrada.
Pronto surgió un hecho curioso: a pesar de su excelente desempeño en la práctica, el método símplex no se ejecuta en tiempo polinomial. Se encontraron ejemplos en los que símplex se ejecutaba en tiempo exponencial. Eventualmente, se encontraron algoritmos de tiempo polinomial para programación lineal, pero el método símplex continuó usándose y, en muchas situaciones, superó a sus competidores de tiempo polinomial.
¿Por qué simplex funciona tan bien?
Esta pregunta estaba en el aire cuando Fortnow era un Ph.D. estudiante en el Instituto de Tecnología de Massachusetts (MIT) en la década de 1980, varios años antes de que Spielman se graduara allí. Sin embargo, recuerda Fortnow, pocos intentaban resolverlo. «El método simplex ya existía desde hace 40 años», dijo Fortnow. La actitud general fue: «Bueno, funciona bien en la práctica».
Cuando Spielman y Teng presentaron un análisis suavizado, fue una gran sorpresa. «Es una forma completamente diferente de ver la complejidad del peor de los casos», dijo Fortnow, «y podrían aplicarla a la programación lineal. Ambas piezas fueron muy emocionantes».
Peor caso versus aleatorio
Spielman era un estudiante de posgrado cuando él y Teng comenzaron a trabajar juntos; Teng era entonces instructor en el MIT.
El objetivo inicial de la pareja era mejorar el método símplex encontrando una nueva forma de proceder alrededor del poliedro, con la esperanza de que el algoritmo mejorado se ejecutara en tiempo polinomial. «Fracasamos en ese esfuerzo», dijo Spielman, «pero cuando estábamos trabajando en ello, aprendimos algo».
El estándar de tiempo polinomial se centra en cómo se comporta un algoritmo en los peores casos, independientemente de si tales casos son típicos. Los casos en los que el método símplex requiere un tiempo exponencial, como el famoso ejemplo encontrado por Victor Klee y George Minty en 1972, «se sabía que eran artificiales», dijo Spielman. «No tendían a ocurrir en la práctica».
Una forma alternativa de ver el rendimiento algorítmico es examinar cómo funciona un algoritmo con entradas aleatorias. Alrededor de 1980, el informático alemán Karl-Heinz Borgwardt demostró que cuando se alimentan entradas aleatorias, el método símplex siempre se ejecuta en tiempo polinomial. Este resultado trajo nuevos conocimientos, pero no contó toda la historia.
Las entradas aleatorias, lejos de ser típicas, son de hecho «muy especiales», dijo Spielman. «Cada parte de la entrada es aleatoria en realidad es una condición muy fuerte. Eso no suele suceder». En la práctica, las entradas al método símplex provienen de sistemas del mundo real, que no son puramente aleatorios sino que contienen estructura.
Lo que Spielman y Teng encontraron es que si tomaban una entrada del peor de los casos para el método símplex e introducían una pequeña perturbación aleatoria, la entrada perturbada se ejecutaría repentinamente en tiempo polinomial. «Aprendimos que [the worst cases] eran realmente muy frágiles», dijo Spielman. «La forma en que Shang-hua lo expresó es que, si usas guantes de boxeo, no podrías construir uno de ellos. Necesitabas mucha precisión para construir un ejemplo que sería malo para el método símplex».
Esta observación llevó a Spielman y Teng a desarrollar un análisis suavizado, que combina el peor de los casos y los puntos de vista aleatorios, lo que brinda una explicación convincente de por qué el método símplex funciona tan bien. La «complejidad suavizada» de un algoritmo es el máximo del tiempo de ejecución esperado del algoritmo sobre las entradas que contienen ligeras perturbaciones. Para un algoritmo de baja complejidad suavizada, cada entrada tiene una vecindad que contiene entradas en las que el algoritmo funcionará bien.
Desde su nacimiento hace más de dos décadas, el análisis suavizado se ha utilizado para analizar el rendimiento de algoritmos distintos del método símplex, incluidos los métodos de punto interior para la programación lineal. También ha guiado el diseño de nuevos algoritmos.
Recientemente, el análisis suavizado se ha utilizado en el aprendizaje automático, donde a menudo se busca la agrupación en clústeres de datos. «Los datos generalmente provienen del mundo real o de algo natural, por lo que espera que haya ruido en ellos», comentó Spielman. «Entonces, en la agrupación en clústeres u otras tareas de aprendizaje automático, el análisis suavizado debería ser mejor que el análisis del peor de los casos».
Las preguntas correctas
A veces, cuando un recién llegado hace un gran trabajo temprano, la presión de sobresalir en ese nivel puede volverse agobiante. Sin embargo, «fue todo lo contrario con Dan», dijo Fortnow. «Simplemente lo ayudó a comenzar. Continuó haciendo cosas más grandes y mejores». La mención del premio Breakthrough de Spielman menciona sus contribuciones en la teoría de gráficos espectrales, el problema de Kadison-Singer, el álgebra lineal numérica y la teoría de la codificación.
Spielman ha aportado a toda su obra un punto de vista muy original que puede orientar nuevas direcciones de investigación. «Hay personas que pueden encontrar la pregunta correcta para hacer, y hay personas que pueden responder las preguntas», dijo Fortnow. «Es raro ser ambos. Y Dan es ambos».
allyn jackson es un periodista radicado en Alemania que se especializa en ciencias y matemáticas.
entradas no encontradas
