Orlando Sarmiento
Programa de Ingeniería de Sistemas y Computación – COPPE, Universidad Federal de Rio de Janeiro, 68511 CEP: 21941-972, Rio de Janeiro, Brasil.
En este artículo, estamos interesados en resolver un problema de optimización global con polinomios, esto es, encontrar un mínimo global de una función objetivo polinomial sujeto a un conjunto de restricciones definidas por funciones polinomiales, todas definidas en términos de alguna variable de decisión. Estos problemas generalizan diversos problemas de optimización, como por ejemplo, problemas de programación lineal entera 0-1, programación lineal, programación cuadrática, entre otros. Considerando funciones polinomiales no convexas, el problema se torna difícil de resolver, por ello, en recientes décadas muchos investigadores intentan desenvolver nuevas técnicas abordando estos problemas, una de ellas es la técnica de Reformulación-Linealización (RLT). Esa técnica se realiza a través de un proceso de reformulación automática el cual genera desigualdades válidas con el propósito de fortalecer la relajación y, en consecuencia, mejorar el rendimiento de los algoritmos globales branch-and-bound. En este trabajo presentaremos algunas relajaciones RLT que han sido estudiados exhaustivamente con óptimos resultados en programación cuadrática, y últimamente extendidos, por Sherali & Tuncbilek [10,11], para programación con polinomios de mayor grado. Mostraremos los principales resultados obtenidos en tales investigaciones, y aplicaremos estas metodologías para resolver el problema de optimización esférica cúbica.
Descriptores: Programación global con polinomios, relajaciones de un problema, técnica reformulación-linealización (RLT), algoritmo branch-and-bound, problema de optimización esférica cúbica.