Sorprendentes límites descubiertos en la búsqueda de soluciones óptimas

By: Max G. Levy

uestras vidas son una sucesión de problemas de optimización. Ocurren cuando buscamos la ruta más rápida a casa desde el trabajo o intentamos equilibrar el costo y la calidad en un viaje a la tienda, o incluso cuando decidimos cómo pasar el tiempo libre limitado antes de acostarnos.

Estos escenarios y muchos otros pueden representarse como un problema de optimización matemática. Tomar las mejores decisiones es cuestión de encontrar sus soluciones óptimas. Y para un mundo inmerso en la optimización, dos resultados recientes brindan buenas y malas noticias.

En un artículo publicado en agosto de 2020 , Amir Ali Ahmadi de la Universidad de Princeton y su antiguo alumno, Jeffrey Zhang , que ahora se encuentra en la Universidad Carnegie Mellon, establecieron que para algunos problemas de optimización cuadrática, en los que los pares de variables pueden interactuar, es computacionalmente inviable. encuentre incluso soluciones óptimas a nivel local de una manera eficiente en el tiempo.

Pero luego, dos días después, Zhang y Ahmadi publicaron un segundo documento con una conclusión positiva. Demostraron que siempre es posible identificar rápidamente si un polinomio cúbico, que puede presentar interacciones de tres vías entre variables, tiene un mínimo local y encontrarlo si lo tiene.

Los límites no son los que esperaban sus descubridores.

“No hubiera pensado que algo mágico sucede con los cubos que hacen que sus mínimos locales sean fáciles de encontrar”, dijo Ahmadi.

En conjunto, los resultados establecen dos marcadores importantes en el estudio de la complejidad computacional, demostrando que ciertos tipos de problemas son fáciles de resolver mientras que otros son necesariamente difíciles.

También proporcionan nuevas barreras para los investigadores interesados ​​en la optimización en una variedad de campos, desde las finanzas hasta los sistemas autónomos.

Vida en matemáticas

Suponga que está a cargo de una fábrica de automóviles que solo fabrica dos modelos, el Cheapo y el Deluxe. El Deluxe se vende por más que el Cheapo, cuesta más fabricarlo y ocupa más tiempo en la línea de producción. ¿Cuántos de cada uno debería construir la fábrica?

Este dilema se traduce en un problema de optimización polinomial.

Para realizar esta traducción, divida el problema en tres elementos distintos. Están todas las variables cuantificables esperando ser optimizadas, como la cantidad de automóviles que debe producir, restricciones, como presupuestos y capacidad de producción, y luego algo llamado función objetivo, que es la suma de cómo cada variable lo orienta hacia su meta o lejos de ella.

“La función objetivo toma las variables de decisión como entrada y escupe un número”, dijo Ahmadi. “Esto es algo que siempre queremos minimizar o maximizar”.

Nuestro ejemplo de factor de automóvil es un problema de optimización simple. Como lo hemos descrito, asumimos que ninguna de las variables interactúa entre sí, lo que significa que se pueden empaquetar en una función lineal. Pero la mayoría de los problemas del mundo real son más complicados. Las matemáticas que los describen también lo son.

Por ejemplo, imagine que está tratando de identificar el centro óptimo para una aerolínea. Cada aeropuerto tiene su propio valor inherente (contribuciones lineales) del tráfico o el costo del aeropuerto. Pero luego, los términos cuadráticos capturan el efecto de elegir pares de aeropuertos que interactúan entre sí de maneras particulares: si tiene mucho tráfico fuera de Los Ángeles, se beneficiará más al vincularlo con un centro de San Francisco.

Y, por supuesto, los problemas pueden ser incluso más complicados que eso. Las interacciones de tres vías entre variables requieren funciones cúbicas más complejas.

Cada paso en la complejidad de las funciones le permite modelar una gama más amplia de problemas. Pero esa complejidad tiene un costo: no hay garantía de que aún pueda calcular las soluciones óptimas.

Problema óptimo

La teoría de la optimización moderna se desarrolló durante la Segunda Guerra Mundial cuando un científico llamado George Dantzig ideó un procedimiento para encontrar soluciones a los problemas de optimización lineal. Su trabajo pionero ayudó al Departamento de Defensa de EE. UU. A tomar decisiones informadas sobre todo, desde la adquisición de aviones hasta el transporte de suministros al extranjero.

Durante las siguientes décadas, los investigadores siguieron su ejemplo y desarrollaron algoritmos más rápidos para encontrar soluciones óptimas a problemas cada vez más complicados.

Pero en la década de 1980 estos avances chocaron con una barrera inamovible. Los investigadores demostraron que no es posible que exista un algoritmo rápido para resolver problemas de optimización. Establecieron que estas preguntas son fundamentalmente demasiado complejas para permitirlo. 

Entonces, ¿a dónde ir si las soluciones óptimas están fuera de su alcance? Puede buscar soluciones aproximadas o soluciones óptimas “localmente”, como se las conoce.

Es posible que las soluciones localmente óptimas no representen el mejor resultado posible, pero son mejores que cualquier solución similar. Son formas “suficientemente buenas” de tomar decisiones, como cuántos de cada automóvil fabricar, que no se pueden mejorar con pequeños ajustes en algunas de las variables. Solo una gran reorganización podría conducir al mejor resultado absoluto, pero para problemas grandes, dicha reorganización es demasiado intensiva desde el punto de vista informático.

Dado todo esto, desde principios de la década de 1990, los investigadores han tratado de determinar si existe un método rápido para encontrar soluciones óptimas a nivel local. En dos casos importantes, Ahmadi y Zhang finalmente descubrieron la respuesta.

Malas noticias para las cuadráticas

Cuando los investigadores quieren determinar si un problema es computacionalmente difícil de resolver, por lo general lo comparan con alguna otra pregunta cuya complejidad ya conocen. Si sabe que el problema A es intratable y puede demostrar que resolver el problema B proporcionaría una forma de resolver A, ahí está su prueba.

“Eso debe significar que el problema que tuvo BI no es fácil”, dijo Zhang.

En su primer artículo, Ahmadi y Zhang igualaron el desafío de la optimización cuadrática, en la que los pares de variables interactúan, con algo llamado el problema del conjunto estable máximo, un problema famoso (y demostrablemente) difícil de resolver.

Un “conjunto estable” es cualquier lista de nodos en un gráfico en el que no hay dos nodos directamente vinculados. El problema del conjunto estable máximo pide encontrar el conjunto más grande de un gráfico. Incluso si todo lo que desea saber es si existe un conjunto estable de un tamaño determinado, es computacionalmente complejo determinar la respuesta.

En junio pasado, Ahmadi y Zhang reformularon el problema del conjunto estable máximo como un caso especial de búsqueda de soluciones óptimas a nivel local. Se les ocurrió un método para representar la pregunta del conjunto estable como un problema de optimización cuadrática. Encontrar un conjunto estable de cierto tamaño se convirtió en una cuestión de encontrar soluciones óptimas a nivel local para este problema de optimización.

Y dado que ya sabían que no hay una forma rápida de encontrar estos conjuntos estables, sabían que no hay una forma rápida de resolver este problema. Esto significa que las soluciones óptimas a nivel local son tan difíciles de encontrar para este tipo de problemas como las verdaderamente óptimas, una correspondencia sorprendente.

“Intuitivamente, debería ser más fácil. Lo sorprendente es que demuestran que es difícil ”, dijo Monique Laurent de CWI, el instituto nacional de investigación en matemáticas e informática de los Países Bajos.

Buenas noticias sobre Cubics

Ahmadi y Zhang descartaron la existencia de un algoritmo eficiente que siempre encuentra soluciones óptimas a nivel local para algunos problemas de optimización cuadrática. Al mismo tiempo, querían saber: ¿Podrían hacerlo para problemas de optimización cúbica que conllevan la condición simplificadora de que no incorporan restricciones?

Los polinomios cúbicos son importantes de muchas formas prácticas. Proporcionan un marco matemático para pensar en interacciones de tercer orden entre variables. El aumento de la claridad puede mejorar enormemente las herramientas, como las que se utilizan para la minería de texto, donde desea que los algoritmos extraigan el significado de los grandes conjuntos de datos.

Cuando entré en el problema de los mínimos locales cúbicos, en realidad esperaba que fuera intratable.

Jeffrey Zhang, Universidad Carnegie Mellon

Por ejemplo, imagina que introduces un bloque de texto en una computadora y le pides que determine de qué trata el texto. La computadora observa que la palabra “manzana” aparece con frecuencia. Pero sin más información, el tema sigue siendo ambiguo.

“Podría ser la fruta. Podría ser la empresa ”, dijo Anima Anandkumar del Instituto de Tecnología de California.

Saber que aparecen tanto la “manzana” como la “naranja” le daría más confianza, pero aún podría estar equivocado (Orange también es una empresa). Un tercer término como “melón” introduce una relación cúbica y podría permitirle concluir con seguridad que el texto está hablando de productos.

Pero la claridad adicional aporta complejidad adicional, y es por eso que Zhang inicialmente no se hizo ilusiones.

“Cuando entré en el problema de los mínimos locales cúbicos, en realidad esperaba que fuera intratable”, dijo.

A principios de 2019, exploró diferentes formas de abordar el problema. Estuvo atascado hasta que Ahmadi sugirió que probara una técnica llamada suma de cuadrados que Ahmadi había utilizado anteriormente para resolver otros problemas de optimización.

Un futuro más brillante

“Suma de cuadrados” se refiere a la idea de que algunos polinomios se pueden representar como la suma del cuadrado de otros polinomios. Por ejemplo, 2 x ² + 16 x + 34 = ( x + 5) ² + ( x + 3) ² .

La perspectiva de suma de cuadrados revela inmediatamente las propiedades del polinomio con el que comenzaste. Los cuadrados de los números reales no pueden ser negativos, por lo que si puede expresar un polinomio como una suma de cuadrados, y hay una manera rápida de verificar si puede, habrá demostrado que siempre genera un valor no negativo. Sin embargo, este enfoque no funciona en problemas de optimización cuadrática con restricciones, razón por la cual Ahmadi y Zhang no pudieron aprovecharlo en su trabajo cuadrático.

Pero para problemas de optimización cúbica sin restricciones, la suma de cuadrados se convierte en una prueba útil para encontrar soluciones mínimas óptimas localmente. Imagine la gráfica de una función polinomial como una curva que flota sobre el eje horizontal. Su punto bajo corresponde a una disposición particular de variables.

Un algoritmo rápido puede recorrer una serie de entradas, probando repetidamente que el polinomio es una suma de cuadrados. Mientras hace esto, el algoritmo arrastra la curva hacia abajo para que toque el eje y sea apenas positiva. En ese punto, otro algoritmo rápido puede indicarle las coordenadas del punto bajo de manera eficiente.

El gran avance de Zhang y Ahmadi se produjo cuando descubrieron que la búsqueda de soluciones localmente óptimas de funciones cúbicas se puede realizar encontrando puntos bajos de ciertos polinomios con la prueba de suma de cuadrados.

En la gráfica de un polinomio cúbico como x ³ + 1, un extremo siempre va hacia el infinito negativo. Entonces, los cúbicos nunca pueden ser no negativos en todas partes o una suma de cuadrados. Pero Ahmadi y Zhang encontraron una forma de enfocarse exclusivamente en la parte del gráfico que se curva hacia arriba. Y ahí es donde aplicaron su prueba de suma de cuadrados.

“Para los cúbicos, siempre podemos arrastrar nuestra función hasta donde queramos”, dijo Zhang.

El resultado resuelve una importante cuestión teórica sobre la dificultad de encontrar soluciones localmente óptimas de funciones cúbicas. Ahmadi y Zhang ahora están tratando de mejorar su valor práctico actualizando un algoritmo ampliamente utilizado para que pueda funcionar con relaciones cúbicas en lugar de solo cuadráticas. Esto haría que el programa fuera menos errático y podría conducir a un mejor rendimiento para una variedad de tareas de aprendizaje automático.

“Si tienen éxito en hacer que esto funcione”, dijo Laurent, “esto podría ser muy útil”.