Un problema matemático clásico es conducido al mundo moderno
Hace un siglo, el gran matemático David Hilbert planteó una pregunta inquisitiva sobre las matemáticas puras. Un avance reciente en la teoría de la optimización está llevando el trabajo de Hilbert a un mundo de vehículo autonómo.
Mucho antes de que los robots pudieran funcionar o los autos podían conducir, los matemáticos contemplaban una simple pregunta matemática. Lo descubrieron, luego lo dejaron descansar, sin forma de saber que el objeto de su curiosidad matemática aparecería en las máquinas del futuro lejano.
El futuro ahora está aquí. Como resultado del nuevo trabajo de Amir Ali Ahmadi y Anirudha Majumdar de la Universidad de Princeton, un problema clásico de las matemáticas puras está a punto de proporcionar una prueba de que los aviones no tripulados y los vehículo autónomos no chocarán contra los árboles ni se desviarán hacia el tráfico que se aproxima.
"Obtiene una garantía completa del 100 por ciento comprobable de que su sistema" evitará colisiones ", dijo Georgina Hall, estudiante graduada de último año en Princeton que ha colaborado con Ahmadi en el trabajo.
La garantía proviene de un lugar improbable, un problema matemático conocido como "suma de cuadrados". El problema fue planteado en 1900 por el gran matemático David Hilbert. Preguntó si ciertos tipos de ecuaciones siempre podrían expresarse como una suma de dos términos separados, cada uno elevado a la potencia de 2.
Los matemáticos resolvieron la cuestión de Hilbert en unas pocas décadas. Luego, casi 90 años después, los científicos e ingenieros informáticos descubrieron que esta propiedad matemática, ya sea que una ecuación se pueda expresar como una suma de cuadrados, ayuda a responder a muchos problemas del mundo real que les gustaría resolver.
"Lo que hago usa mucha matemática clásica del siglo XIX combinada con matemática computacional muy nueva", dijo Ahmadi.
Sin embargo, incluso cuando los investigadores se dieron cuenta de que la suma de cuadrados podría ayudar a responder muchos tipos de preguntas, enfrentaron desafíos para implementar el enfoque. El nuevo trabajo de Ahmadi y Majumdar borra uno de los mayores desafíos: traer una vieja pregunta matemática directamente sobre algunas de las cuestiones tecnológicas más importantes del día.
Amir Ali Ahmadi, profesor de la Universidad de Princeton, ha mostrado cómo se puede aplicar un algoritmo de suma de cuadrados a los problemas modernos de optimización.
Positividad garantizada
¿Qué significa que algo sea una suma de cuadrados? Tome el número 13. Es la suma de dos cuadrados: 22 y 32. El número 34 es la suma de 32 más 52.
En lugar de números, la pregunta de Hilbert -el 17 de 23 que planteó a comienzos del siglo XX- tiene que ver con expresiones polinómicas como 5x2 + 16x + 13. Este tipo de polinomios a veces se pueden expresar también como sumas de cuadrados. Por ejemplo, 5x2 + 16x + 13 pueden reescribirse como (x + 2) 2 + (2x + 3) 2.
Cuando una expresión es una suma de cuadrados, sabes que siempre es no negativa. (Debido a que todo al cuadrado es positivo o cero, y la suma de números positivos es un número positivo.) Hilbert quería saber si funciona al revés: si todos los polinomios no negativos se pueden expresar como una suma de cuadrados de funciones racionales. En 1927, el matemático Emil Artin demostró que la conjetura de Hilbert es cierta.
Esta relación resulta bastante útil. Si te entregan un complicado polinomio, uno con docenas de variables elevadas a altas potencias, no es fácil determinar de inmediato si siempre es no negativo. "Algunos polinomios son obviamente no negativos, otros no. Es difícil probar si siempre son no negativos ", dijo Ahmadi.
Pero una vez que demuestras que el mismo polinomio se puede expresar como una suma de cuadrados, entonces sabes que la no negativa sigue como consecuencia. "Suma de cuadrados te da un buen certificado de positividad", dijo Pablo Parrilo, un científico informático e ingeniero en el Instituto de Tecnología de Massachusetts que fue influyente en llevar la cuestión de la suma de cuadrados al ámbito aplicado.
Saber si un polinomio es siempre no negativo puede parecer una trivialidad matemática. Pero un siglo después de que Hilbert hiciera su pregunta, la no negatividad polinómica ha resultado para responder a problemas aplicados que nos afectan a todos.
La mejor manera
Amir Ali Ahmadi, profesor de la Universidad de Princeton, ha mostrado cómo se puede aplicar un algoritmo de suma de cuadrados a los problemas modernos de optimización.
La suma de cuadrados se encuentra con el mundo real en el campo de la optimización. La teoría de la optimización se refiere a encontrar la mejor manera de hacer algo en medio de restricciones, como encontrar la mejor ruta para el trabajo dadas las condiciones actuales del tráfico y una parada que debe hacer en el camino. Escenarios como estos a menudo se pueden destilar en ecuaciones polinomiales. En tales casos, resuelve u "optimiza" el escenario, al encontrar el valor mínimo tomado por el polinomio.
Encontrar el valor mínimo de un polinomio con muchas variables es difícil: no existe un algoritmo sencillo de estilo de escuela secundaria para calcular el valor mínimo de polinomios complicados, y estos mismos polinomios no son fáciles de graficar.
Debido a que el valor mínimo de un polinomio es difícil de calcular directamente, los investigadores lo infieren por otros medios. Y aquí es donde aparece la no negatividad y la cuestión de si un polinomio es una suma de cuadrados. "Certificar la no negatividad es realmente el corazón de todos los problemas de optimización", dijo Rekha Thomas, matemática de la Universidad de Washington.
Una forma de encontrar el valor mínimo es preguntarse: ¿qué más puedo restar de un polinomio no negativo antes de que se vuelva negativo en alguna parte? Al responder a esta pregunta, puede probar valores diferentes: ¿puedo restar 3 del polinomio de modo que todavía no sea negativo? ¿Qué hay de 4? O 5? Al repetir este procedimiento, le interesa saber en cada paso si el polinomio aún no es negativo. Y la forma de comprobarlo es comprobando si el polinomio aún puede expresarse como una suma de cuadrados.
"Lo que quieres preguntar es, '¿el polinomio no es negativo?' El problema es que responder a la no negatividad es difícil con más variables", dijo Ahmadi. "Es por eso que utilizamos la suma de cuadrados como un sustituto de la no negatividad".
Una vez que los investigadores conocen el mínimo (que es, recuerde, el valor óptimo del polinomio), pueden usar otros métodos para identificar las entradas que conducen a ese valor. Sin embargo, para que la no negatividad ayude a resolver los problemas de optimización, necesita una forma de calcular rápidamente si un polinomio es igual a la suma de cuadrados. Y pasaron 100 años después de la pregunta de Hilbert para que los investigadores lo descubrieran.
Rompiendo el problema
Anirudha Majumdar dirige el Intelligent Robot Motion Lab en la Universidad de Princeton.
La decimoséptima pregunta de Hilbert cruzó de las matemáticas puras a la aplicación en el mundo real alrededor del año 2000. Fue entonces cuando varios investigadores diferentes descubrieron un método algorítmico para verificar si un polinomio es una suma de cuadrados. Lo lograron al traducir la pregunta de suma de cuadrados en un "programa semidefinido", que es un tipo de problema que las computadoras saben cómo manejar. Esto, a su vez, hizo posible que los investigadores en campos como la informática y la ingeniería utilizaran el poder de la no negatividad para orientar su búsqueda de formas óptimas de resolver problemas.
Pero la programación semidefinida tiene una gran limitación: es lenta en problemas grandes y no puede manejar muchos de los polinomios más complicados que a los investigadores realmente les importan. La programación semidefinida puede usarse para encontrar una suma de cuadrados descompuestos para polinomios con un puñado de alrededor de una docena de variables elevadas a potencias no superiores a aproximadamente 6. Los polinomios que caracterizan problemas de ingeniería complejos, como cómo asegurar que un robot humanoide se mantenga en pie - puede involucrar 50 o más variables. Un programa semidefinido podría masticar ese tipo de polinomio hasta el final de los tiempos y aún así no devolver una respuesta de suma de cuadrados.
En un documento publicado en línea el pasado junio, Ahmadi y Majumdar explican una forma de evitar la lentitud de la programación semidefinida. En lugar de tratar de encontrar una suma de cuadrados de descomposición mediante la resolución de un único programa semidefinido lento, muestran cómo hacerlo usando una secuencia de problemas más simples que son mucho más rápidos de calcular.
Este tipo de problemas se denominan "programas lineales" y se desarrollaron en la década de 1940 para responder a los problemas de optimización relacionados con el esfuerzo de guerra. Los programas lineales ahora son bien entendidos y rápidos de resolver. En su nuevo trabajo, Ahmadi y Majumdar muestran que puede resolver muchos programas lineales vinculados (o, en algunos casos, otro tipo de problema conocido como programa de cono de segundo orden) y combinar los resultados para obtener una respuesta que es casi tan buena como la respuesta que podrías obtener con un programa semidefinido. El resultado es que los ingenieros tienen una herramienta nueva y práctica que pueden usar para probar la no negatividad y encontrar la suma de las descomposiciones de cuadrados rápidamente.
"Analizamos una serie de problemas de la robótica y la teoría de control y demostramos que la calidad de la solución que recibíamos seguía siendo útil en la práctica y mucho más rápida de calcular", dijo Majumdar.
Ahora, no es bueno si este muro está a medio camino entre el automóvil y la cabina. Desea diseñar su polinomio para que la pared abrace el obstáculo lo más cerca posible. Esta cerca de la cabina de guardia mientras le da al automóvil suficiente espacio para moverse.
En la práctica, quiere minimizar un valor, la distancia entre la pared y la cabina, y así cambia el gráfico del polinomio para ver qué tan lejos puede empujarlo antes de que deje de ser negativo. Y está probando esa línea probando si el polinomio desplazado sigue siendo una suma de cuadrados.
Un estacionamiento casi vacío es una cosa. Pero en escenarios de conducción realistas, los sensores de un automóvil identifican continuamente obstáculos nuevos y cambiantes: automóviles, bicicletas, niños. Cada vez que aparece un nuevo obstáculo, o uno existente se mueve, el automóvil tiene que idear nuevos polinomios elaborados para cerrarlos. Es una gran cantidad de controles de cuadrados para hacer sobre la marcha.
Hace siete años, un par diferente de investigadores imaginaba que podría ser posible utilizar tales técnicas polinómicas para segregar autos autónomos de lugares a los que no deberían ir. Pero en ese momento, la velocidad computacional hizo de la idea un sueño imposible.
El nuevo enfoque de Ahmadi y Majumdar proporciona una forma de llevar a cabo cálculos tan rápidos. Entonces, si y cuando los autos que conducen de forma autónoma puedan navegar por el mundo de forma segura, tendremos que agradecer a Google y a Tesla, y también a David Hilbert.
Posted from my blog with SteemPress : https://matematicapositiva.com.ve/un-problema-matematico-clasico-es-conducido-al-mundo-moderno/