Un algoritmo para describir puntos en conjuntos semialgebraicos

GABRIELA JERONIMO; DANIEL PERRUCCI; JUAN SABIA

Bahía Blanca, Argentina

Congreso; LVI Reunión Anual de Comunicaciones Científicas de la Unión Matemática Argentina; 2006

Unión Matemática Argentina

Dado un sistema de ecuaciones e inecuaciones dadas por polinomios en n variables con coeficientes reales, una de las preguntas básicas que pueden plantearse es si este sistema tiene o no una solución en R^n. En caso de que el conjunto de las soluciones sea no vacío, la siguiente pregunta natural es cómo exhibir, de alguna manera, (algunas de) estas soluciones. Una de las subrutinas más utilizadas en los algoritmos que resuelven este problema consiste en hallar un conjunto finito que contenga al menos un punto en cada componente conexa del conjunto de las soluciones. En el caso de sistemas de ecuaciones (sin desigualdades), la práctica más usual involucra localizar los puntos críticos sobre el conjunto en cuestión de una función polinomial (típicamente, una proyección o una distancia). En esta charla exhibiremos un algoritmo para la resolución del problema planteado, que utiliza las condiciones de Karush-Kuhn-Tucker (que generalizan el teorema de los multiplicadores de Lagrange al admitir condiciones de desigualdades) para caracterizar puntos críticos. Bajo ciertas hipótesis, estas condiciones permiten reducir el problema a hallar las soluciones aisladas de un sistema de ecuaciones ampliado. Para resolver este nuevo sistema desarrollamos un método específico, basado en técnicas de deformación, que explota fuertemente su estructura. Como resultado obtenemos un nuevo algoritmo para resolver el problema original con complejidades que mejoran las de los algoritmos anteriores que lo resuelven.