Un algoritmo para describir puntos en conjuntos semialgebraicos

PERRUCCI, DANIEL; JERONIMO, GABRIELA; SABIA, JUAN

Vaquerías, Córdoba

Congreso; III Encuentro Nacional de Algebra; 2006

Universidad Nacional de Córdoba

Dado un sistema de ecuaciones e inecuaciones polinomiales  f1(x) = . . . = fm(x) = 0, g1(x) ¸ 0, . . . , gp(x) ¸ 0, con fi, gj en R[X1, . . . ,Xn], i = 1, . . . ,m; j = 1, . . . , p, una de las preguntas basicas que pueden plantearse es si este sistema tiene o no una solucion en Rn. En caso de que el conjunto de las soluciones sea no vacio, la siguiente pregunta natural es como exhibir, de alguna manera, (algunas de) estas soluciones. Una de las subrutinas mas 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 practica mas usual involucra localizar los puntos criticos sobre el conjunto en cuestion de una funcion polinomial (tipicamente, una proyeccion o una distancia). En esta charla exhibiremos un algoritmo para la resolucion 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 criticos. Bajo ciertas hipotesis, estas condiciones permiten reducir el problema a hallar las soluciones aisladas de un sistema de ecuaciones ampliado. Para resolver este nuevo sistema desarrollamos un metodo especifico, basado en tecnicas de deformacion, 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.