Un algoritmo para describir puntos en conjuntos semialgebraicos

GABRIELA JERONIMO; DANIEL PERRUCCI; JUAN SABIA

Bahía Blanca, Pcia. de Buenos Aires

Congreso; LVI Reunión de Comunicaciones Científicas de la UMA; 2006

UMA

Dado un sistema de ecuaciones e inecuaciones polinomiales f_1(x) =... = f_m(x) = 0, g_1(x) >= 0, ..., g_p(x) >= 0, con f_i,g_j en R[X1, ..., Xn], i = 1, ..., m; j = 1, ..., p, unade las preguntas básicas que pueden plantearse es si este sistematiene o no una solución en R^n. En caso de que el conjunto delas soluciones sea no vacío, la siguiente pregunta natural escómo exhibir, de alguna manera, (algunas de) estas soluciones.Una de las subrutinas más utilizadas en los algoritmos queresuelven este problema consiste en hallar un conjunto finito quecontenga al menos un punto en cada componente conexa del conjunto delas soluciones. En el caso de sistemas de ecuaciones (sindesigualdades), la práctica más usual involucra localizar lospuntos críticos sobre el conjunto en cuestión de una funciónpolinomial (típicamente, una proyección o una distancia).En esta charla exhibiremos un algoritmo para la resolución delproblema planteado, que utiliza las condiciones deKarush-Kuhn-Tucker (que generalizan el teorema de losmultiplicadores de Lagrange al admitir condiciones de desigualdades)para caracterizar puntos críticos. Bajo ciertas hipótesis,estas condiciones permiten reducir el problema a hallar lassoluciones aisladas de un sistema de ecuaciones ampliado. Pararesolver este nuevo sistema desarrollamos un método específico, basado en técnicas de deformación, que explota fuertementesu estructura. Como resultado obtenemos un nuevo algoritmo pararesolver el problema original con complejidades que mejoran las delos algoritmos anteriores que lo resuelven.