UABDivulga - Barcelona recerca i innovació

De una forma general los problemas de programación matemática se pueden definir como los del cálculo de láximo o mínimo de una función de una o varias variables, cuando éstas están sometidas a un conjunto de restricciones de diferentes tipos. Un programa matemático se indica como sigue,

donde, en el caso más general para nosotros, podemos pensar que S es un conjunto compacto y F(x) una función contínua sovre S. El objetivo de la programación matemática es localizar entre los elementos del conjunto S, llamadas soluciones factibles del programa, aquellos donde la función F(x), llamada función objetivo, tome el menor valor. Estas soluciones, si existen, se les llama soluciones óptimas del programa. En la práctica este concepto se ha de precisar distinguiendo entre soluciones óptimas locales y globales. El concepto de óptimo local se define por comparación entre los valores de la función objetivo en un subconjunto de las soluciones factibles limitado a un entorno arbitrario de la solución. Si la comparación se amplía a todos los elementos del conjunto factible S entonces tenemos el concepto de óptimo global.

Evidentemente todo óptimo global es local.

Si un problema es convexo, i.e., F(x) es convexa y además S es convexo, se sabe que cada óptimo local es global. En los problemas donde la convexidad de la función objetivo o de las restricciones no pueden ser comprobadas, es razonable pensar que el problema puede tener múltiples óptimos locales. La optimización global trata de la caracterización y cálculo de los óptimos globales de los problemas con multiplicidad de extremos. Suponemos que, utilizando las técnicas standard de optimización local de la programación no lineal, hayamos obtenido un punto estacionario del programa. En este punto tenemos que parar el programa ya que ningún procedimiento local puede informarnos si la solución obtenida es globlal o no, y en este último caso cómo continuar para obtener un punto factible mejor. Cualquier procedimiento de optimización global no puede rehuir la cuestión de cómo trascender un punto factible, si hay alguno, o en caso contrario cómo evidenciar que el punto encontrado es un óptimo global del problema. los métodos de optimización global son substancialmente diferentes de los métodos locales y, entre otro, utilizan herramientas son costosas en tiempo de ordenador.

Cuando queremos aplicar técnicas de optimización global para resolver problemas de programación matemática con múltiples extremos siempre nos encontramos con que la convexidad está preesnte de una forma o de otra. Éste es el caso si la función objetivo se puede representar como una diferencia de funciones convexas, F(x) = f(x) - g(x), donde f(x) u g(x) son convexas (función DC), y, además, suponemos que el conjunto factible, S, es convexo. Entonces, el programa matemàtico

se puede transformar, mediante la introducción de una nueva variable t, en un programa equivalente convexo y con una restricción "reverse convex" (es decir, una inecuación definida por una función convexa pero con la desigualdad en sentido contrario al que habría de tener para que su conjunto solución fuera convexo):

"Equivalente", en este caso, significa que a partir de un mínimo global (2) se puede encontrar un mínimo global de (3) y viceversa. Hay algoritmos eficientes, dentro del campo de la optimización global, para resolver este tipo de problemas. Sólo hay que fijarse en F(x) = f(x) + f(x) - (g(x) + f(x)); donde f(x) es una función convexa cualquiera. Las preguntas que surgen en este punto son:

1) ¿es posible, dada un representación DC, encontrar otra que mejore la eficiencia computacional del algoritmo que resuleve (3)?,
2) ¿hay una representación DC que sea la mejor de todas?

En el artículo intriducimos los conceptos necesarios para responder las anteriores preguntas en el caso de los polinomios de varias variables y damos un procedimiento para calcular la mejor representación DC de una función polinómica, llamada mínimo representación DC. També se describen unos cuantos experimentos numéricos, los cuales muestran la importancia de la mínima representación DC desde un punto de vista de la eficiencia computacional. uno de los ejemplos presentados con detalle consiste en una aplicación a un problema de generación hidroeléctrica.