UABDivulga - Barcelona recerca i innovació

D'una forma general els problemes de programació matemàtica es poden definir com els del càlcul del màxim o mínim d'una funció d'una o vàries variables, quan aquestes estan sotmeses a un conjunt de restriccions de diferent tipus. Un programa matemàtic s'indica en la forma següent,

on, en el cas més general per nosaltres, podem pensar que S és un conjunt compacte i F(x) una funció continua sobre S. L'objectiu de la programació matemàtica és localitzar entre els elements del conjunt S, anomenats solucions factibles del programa, aquells on la funció F(x), anomenada funció objectiu, prengui el menor valor. Aquestes solucions, si existeixen, se les anomena solucions òptimes del programa. A la pràctica aquest concepte s'ha de precisar distingint entre solucions òptimes locals i globals. El concepte d'òptim local es defineix per comparació entre els valors de la funció objectiu en un subconjunt de les solucions factibles limitat a un entorn arbitrari de la solució. Si la comparació s'amplia a tots els elements del conjunt factible S aleshores tenim el concepte d'òptim global.

Evidentment tot òptim global és local.
Si un problema és convex, i.e., F(x) és convexa i a més S és convex, se sap que cada òptim local és global. En els problemes on la convexitat de la funció objectiu o de les restriccions no poden ser comprovades, és raonable pensar que el problema pot tenir múltiples óptims locals. L'optimització global tracta de la caracterització i càlcul dels òptims globals dels problemes amb multiplicitat d'extrems. Suposem que, utilitzant les técniques standard d'optimització local de la programació no lineal, haguem obtingut un punt estacionari del programa. En aquest punt tenim que aturar el programa ja que cap procediment local pot informar-nos si la solució obtinguda és global o no, i en aquest últim cas com continuar per obtenir un punt factible millor. Qualsevol procediment d'optimització global no pot defugir la qüestió de com transcendir un punt factible, si n'hi ha cap, o en cas contrari com evidenciar que el punt trobat és un òptim global del problema. Els mètodes d'optimització global són substancialment diferents dels mètodes locals i, entre d'altres, utilitzen eines combinatòries tals com cutting-plane, branch and bound i branch and cut. Totes aquestes técniques són costoses en temps d'ordinador.

Quan volem aplicar tècniques d’optimització global per resoldre problemes de programació matemàtica amb múltiples extrems sempre ens trobem en que la convexitat està present d’una forma o altra. Aquest és el cas si la funció objectiu es pot representar com a diferència de funcions convexes, F(x) = f(x) - g(x), on f(x) i g(x) són convexes (funció DC), i, a més, supossem que el conjunt factible, S, és convex. Aleshores, el programa matemàtic

es pot transformar, mitjantçant la introducció d'una nova variable t, en un programa equivalent convex i amb una restricció "reverse convex" (és a dir, una inequació definida per una funció convexa però amb la desigualtat en sentit contrari al que hauria de tenir per que el seu conjunt solució fos convex):

"Equivalent", en aquest cas, significa que a partir d'un mínim global de (2) es pot trobar un mínim global de (3) i viceversa. Hi ha algorismes eficients, dins el camp de l'optimització global, per resoldre aquests tipus de problemes. Ara bé, una funció DC admet infinites representacions com a diferencia de funcions convexes. Només cal fixar-se en F(x) = f(x) + f(x) - (g(x) + f(x)); on f(x) és una funció convexa qualsevol. Les preguntes que sorgeixen en aquest punt són:

1) és possible, donada una representació DC, trobar-ne un altre que millori l'eficiència computacional de l'algorisme que resol (3)?,
2) hi ha una representació DC que sigui la millor de totes?

A l'article introduïm els conceptes necessaris per respondre les anteriors preguntes en el cas els polinomis de varies variables i donem un procediment per calcular la millor representació DC d'una funció polinòmica, anomenada mínima representació DC. També es descriuen uns quants experiments numèrics, els quals mostren la importància de la mínima representació DC des d'un punt de vista de l'eficiència computacional. Un dels exemples presentats amb detall consisteix en una aplicació a un problema de generació hidroelèctrica.