Optimització matemàtica

En matemàtiques, estadística, ciències empíriques, ciències de la computació o economia, l'optimització matemàtica (també dita optimització o programació matemàtica) és la selecció del millor element (respecte d'un criteri determinat) entre un conjunt d'elements disponibles.

L'optimització intenta donar solució a una sèrie de problemes que es caracteritzen per buscar quin és el màxim i/o el mínim d'una funció, suposant que n'hi hagi. S'entén per un màxim el valor més gran que pot atènyer la funció, ja sigui en un domini limitat (es parla de màxim relatiu) o bé en la totalitat del seu domini (es parla de màxim global). De la mateixa manera es té el mínim,

que és el valor més petit que pot prendre la funció, mínim global si es tracta del valor més petit de tot el seu domini o mínim relatiu si el domini d'aquesta funció ve delimitat .

Per tant, la programació matemàtica intenta donar resposta als problemes que segueixen l'esquema següent:

${\begin{matrix}\max(\min )f(x)\\x\in \Omega \subseteq \mathbb {R} ^{n}\end{matrix}}$

on la x representa un vector. L'expressió f(x) és la funció objectiu, la que s'ha d'optimitzar, que mesura la qualitat de les decisions. A més a més la x ha de complir les restriccions que té el problema o bé ha de pertànyer al conjunt de decisions factibles, $\Omega$.

Problemes d'optimització

Per resoldre un problema d'optimització de funcions, un dels procediments a seguir és: d'entrada, plantejar la funció que es vol maximitzar o bé minimitzar. S'ha de plantejar una equació que relacioni les diverses variables del problema (suposant que hi hagi més d'una variable). Continuant amb la suposició, es pot aïllar una variable d'una equació i així substituir-la en l'altra funció, de manera que queda una sola variable. Ara, ja es pot derivar la funció i igualar-la a zero per trobar els punts estacionaris o extrems locals. Aquests punts tendeixen a ser màxims, mínims o bé punts de sella. Tot i això, la funció pot tenir més màxims i mínims que s'acostumen a trobar als extrems del domini i als punts on la funció no es pot derivar. No obstant això, a vegades, per solucionar aquest tipus de problemes amb restriccions es pot trobar amb un sistema d'igualtats o desigualtats que s'ha de resoldre per poder arribar a la solució del problema d'optimització.

${\begin{matrix}g(x_{1},...,x_{n})&\leq &0\\h(x_{1},...,x_{n})&=&0\end{matrix}}$

Per tant, aquests tipus de problemes tracten de prendre una decisió òptima per tal de maximitzar o minimitzar un criteri determina. És per aquest motiu, que s'utilitza sovint en l'àmbit de les ciències socials i concretament l'econòmic. Els economistes, l'utilitzen per trobar els màxims beneficis davant d'una producció, com poder augmentar la velocitat i l'eficiència, així com reduir costos, temps, riscs... A més a més, utilitzen restriccions, ja que les empreses no acostumen a tenir una llibertat total a l'hora d'actuar, estan regides per un pressupost, per unes capacitats financeres, un espai físic... Per tant, qualsevol decisió no és possible. Les restriccions ajuden a predir els comportaments que duran a terme els empresaris. Un dels exemples més senzills, per començar amb l'optimització i les restriccions és la programació lineal.

Història

Pierre de Fermat i Joseph Louis Lagrange van trobar fórmules basades en el càlcul per identificar valors òptims, mentre que Isaac Newton i Carl Friedrich Gauss van proposar mètodes iteratius per aproximar l'optimització. Històricament, el terme programació lineal per referir-se a certs problemes d'optimització es deu a George B. Dantzig, encara que gran part de la teoria havia estat introduïda per Leonid Kantorovich el 1939. Dantzig va publicar l'algoritme símplex en 1947 i John von Neumann va desenvolupar la teoria de la dualitat en el mateix any.

El terme programació en aquest context no es refereix a la programació d'ordinadors. Més aviat, el terme ve de l'ús de programa per l'exèrcit de Estats Units en referir-se a la proposta d'entrenament i planificació logística, el qual va ser el problema estudiat per Dantzig en aquell temps.

Altres investigadors importants en el camp de l'optimització matemàtica van ser els següents:

Richard Bellman Ronald A. Howard Narendra Karmarkar William Karush Leonid Khachiyan Bernard Koopman Harold W. Kuhn Joseph Louis Lagrange László Lovász

Arkadi Nemirovski Yurii Nesterov Boris Polyak Lev Pontryagin James Renegar R. Tyrrell Rockafellar Cornelis Roos Naum Z. Shor Michael J. Todd Albert Tucker Michael Omar Cuñas

Subcamps principals

• Programació convexa estudia el cas en què la funció objectiu és convexa (minimització) o còncava (maximització) i el conjunt de restriccions és convex. Aquest pot ser vist com un cas particular de la programació no lineal o com la generalització de la programació lineal o de la convexa quadràtica.
  • Programació lineal (PL): és un tipus de programació convexa, en què la funció objectiu f és lineal i el conjunt de restriccions s'especifica usant només equacions i inequacions lineals. Aquest conjunt és anomenat poliedre o polítop si està fitat.
  • Programació cònica: és una forma general de la programació convexa. PL, PCSO i PSD poden tots són vists com a programes cònics amb el tipus de con apropiat.
  • Programació de con de segon ordre (PCSO): és un tipus de programació convexa i inclou certs tipus de problemes de programació quadràtica.
  • Programació semidefinida (PSD): és un subcamp de l'optimització convexa on les variables fonamentals són matrius semidefinides. És una generalització de la programació lineal i la programació quadràtica convexa.
  • Programació geomètrica: és una tècnica per mitjà de la qual l'objectiu i les restriccions de desigualtat expressats com a polinomis i les restriccions d'igualtat com a monomis, poden ser transformats en un programa convex.
  • Programació amb enters o Programació entera: estudia programes lineals en els quals algunes o totes les variables estan obligades a prendre valors enters. Aquesta no és convexa i, en general, és molt més complexa que la programació lineal regular.
• Programació quadràtica: permet a la funció objectiu tenir termes quadràtics, mentre que el conjunt factible pot ser especificat amb equacions i inequacions lineals. Per a formes específiques del terme quadràtic, aquesta és un tipus de programació convexa.
• Programació fraccionària: estudia l'optimització de raons de dues funcions no lineals. La classe especial de programes fraccionaris còncaus es pot transformar a un problema d'optimització convexa.
• Programació no lineal: estudia el cas general en què la funció objectiu, o les restriccions, o tots dos, contenen parts no lineals. Aquest pot ser un programa convex o no. En general, si el programa és convex, afecta la dificultat de resolució.
• Programació estocàstica o Optimització estocàstica: estudia el cas en què alguna de les restriccions o paràmetres depèn de variables aleatòries.
• Programació robusta: com la programació estocàstica, és un intent per capturar la incertesa en les dades fonamentals del problema d'optimització. Això es fa mitjançant l'ús de variables aleatòries, però en canvi, el problema es resol tenint en compte imprecisions a les dades d'entrada.
• Optimització combinatòria: es preocupa dels problemes on el conjunt de solucions factibles és discret o pot ser reduït a un.
• Optimització dimensional-infinita: estudia el cas on el conjunt de solucions factibles és un subconjunt d'un espai de dimensió infinita, per exemple un espai de funcions.
• Heurístiques i Metaheurístiques: fan suposicions sobre el problema que està sent optimitzat. Usualment, les heurístiques no garanteixen que qualsevol solució òptima sigui trobada. Després, les heurístiques són usades per trobar solucions aproximades per a molts problemes d'optimització complicats.
• Satisfacció de restricció: estudia el cas en què la funció objectiu f és constant (aquesta és usada en intel·ligència artificial, particularment en raonament automatitzat).
• Programació disjuntiva: s'usa quan almenys una restricció pot ser satisfeta però no totes. Aquesta és d'ús particular en la programació en un nombre de subcamps. Les tècniques són dissenyades principalment per a l'optimització en contextos dinàmics (és a dir, presa de decisions amb el transcurs del temps).
• Càlcul de variacions: cerca optimitzar un objectiu definit sobre molts punts amb el temps, considerant com la funció objectiu canvia si el canvi és petit en el camí d'elecció. La tècnica del control òptim és una generalització d'aquest.
• Programació dinàmica estudia el cas en què l'estratègia d'optimització es basa en la divisió del problema en subproblemes més petits. L'equació que descriu la relació entre aquests subproblemes s'anomena equació de Bellman.
• Programació matemàtica amb restriccions d'equilibri és on les restriccions inclouen desigualtats variables o complementàries.

Tipus d'optimitzacions

La resolució que es plantegi dependrà del nivell de la generalitat que prengui el problema.

Optimització clàssica o sense restriccions

D'entrada cal derivar la funció que es vol optimitzar. Un cop derivada la funció presentada s'ha d'igualar a zero per tal de trobar un valor per a cada variable que es disposa.

∂f / ∂xi(a) = 0

Com a condició cal indicar que "i" pot ser qualsevol valor que estigui entre [0,∞).

Si la funció objectiu és d'una variable: primer es fa la seva derivada i després s'iguala a 0 per trobar allà on hi ha un punt estacionari. Per resoldre l'equació, cal aïllar la variable (es pot usar factor comú o haver de resoldre equacions de segon, tercer… grau). El punt que s'obtingui serà un possible punt estacionari.

Si la funció objectiu és de dues variables: d'entrada cal realitzar les derivades parcials respecte a cada una de les variables i s'ha d'igualar les dues parcials que surtin a 0. Aquest cop, usant el mètode de substitució es troba el punt o bé que s'hagi de resoldre un sistema de dues equacions amb dues incògnites. Per tant, et pot recórrer al mètode de reducció o igualació. Un cop igualat a zero i s'hagin trobat els possibles punts estacionaris cal comprovar si realment són òptims, ja que no pot afirmar que tot punt estacionari sigui un òptim (màxim o mínim), sinó que si la funció és derivable llavors es tindrà un punt que pot ser màxim o mínim. Per tant, cal estudiar les condicions que ho determinaran i classificar-los segons el tipus d'òptim que siguin:

• Condició de primer ordre (segons la fórmula inicial): "a" serà un òptim de "f", per tant, serà un punt crític de "f". En el cas d'una funció objectiu amb dues variables es pot usar el que anomenem R². Donada una funció f(x,y) i un punt P=(x₀, y₀) serà :
  • "P" és un màxim local si f(x,y) és més petit o igual que f(x₀, y₀). Suposant que existeix un cercle de centre "P" i radi r>0 per a totes les "x" i "y" del cercle.
  • "P" és un mínim local si f(x,y) és més gran o igual que f(x₀, y₀). Suposant que existeix un cercle de centre "P" i radi r>0 per a totes les "x" i "y" del cercle.
  • "P" és un punt de sella, quan sigui un punt estacionari i no es pugui considerar ni màxim ni mínim.
• Condició de segon ordre, seguint el Teorema 1 (tenint en compte que "a" és un punt crític de "f" i només és vàlid quan tenim una funció de dues variables o més i les seves derivades parcials de 1r i 2n ordre són contínues):
  • "a" serà un mínim local de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és definida positiva (si i només si tots els valors propis de "x" i "y" són positius i diferents de 0,0), si surt semidefinida positiva (si els valors propis de "x" i "y" donen el valor 0,0 o un valor positiu) hem de mirar les definicions.
  • "a" serà un màxim local de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és definida negativa (si i només si tots els valors propis de "x" i "y" són negatius i diferents de 0,0), si surt semidefinida negativa (si els valors propis de "x" i "y" donen el valor 0,0 o un valor negatiu) hem de mirar les definicions.
  • "a" serà un punt de sella de "f" quan, la forma quadràtica que té per matriu associada a H(a)f és indefinida.
• Condició suficient de primer ordre: per determinar la concavitat o convexitat de la funció (partint de la base que a és un punt crític de "f"):
  • La funció (f) serà convexa si "a" és un mínim global de "f".
  • La funció (f) serà còncava si "a" és un màxim global de "f".

Optimització amb restriccions d'igualtat (no clàssica)

Optimitzar f(x)

Subjecte a gi(x) = 0

Com a condició cal dir que "i" pot ser qualsevol valor que estigui entre [0,∞]

En aquest cas es tracta d'una funció objectiu que està subjecta o regida per una altra funció que li determina el domini. Aquest tipus d'optimització es pot resoldre de diverses maneres:

Mètode directe o substitució

La resolució mitjançant el mètode directe o substitució tracta de transformar el problema original a un problema equivalent d'optimització però sense cap restricció.

Optimitzar f(x)

Subjecte x є M

Exemple:

Optimitzar (x-3)² + (y+6)²

Subjecte x + y = 7

Usant el mètode directe es pot aïllar una de les variables de la restricció (x = 7–y) i substituir a la funció inicial o objectiu [(7-y)-3]² + (y+6)². Ara ja es pot resoldre l'equació d'una variable de segon grau, llavors es pot trobar un valor de "y". Obtingut aquest valor, es substitueix a la restricció i ja es disposa del valor de "x" també "i" per tant, ja s'ha trobat el possible òptim. Ara tan sols, queda classificar-lo segons les condicions de primer o segon ordre, ara bé, sempre serà relatiu l'òptim trobat, ja que està condicionat a un domini de la funció.

Mètode dels multiplicadors de Lagrange

La resolució mitjançant el mètode dels multiplicadors de Lagrange s'acostuma a utilitzar quan no es pot aïllar una de les variables de la restricció. Aquest mètode consisteix en plantejar la funció lagrangiana: "L (x,y) = f(x,y) – λ [g(x,y)-C)" on "λ" és una constant. Un cop feta la funció lagrangiana s'han de fer les derivades parcials respecte a les dues variables que conté la funció ("x" i "y") i igualar-les a 0. Amb aquestes dues equacions i la restricció es pot plantejar un sistema de tres equacions.

f'(x)= λg'(x)

f'(y)= λg'(y)

g(x,y)= C

Llavors queda resoldre el sistema per tal de trobar els valors que prenen "x", "y" i "λ". Un cop es disposi dels valors que poden prendre cada una de les variables, cal classificar-los segons quin tipus d'òptim siguin. Per tant, primer es substituiran els valors a la funció lagrangiana que s'ha creat només començar amb la resolució del problema. Una manera ràpida i senzilla per saber si es parla d'un mínim o un màxim és fixar-se en la funció lagrangiana. Si "f" i "g" són funcions convexes encara que hi hagi alguna funció lineal, la funció resultat serà convexa i per tant l'òptim trobat serà un mínim. No obstant això, si "f" i "g" són funcions còncaves encara que hi hagi alguna funció lineal el resultat serà còncava, i per tant, l'òptim trobat serà un màxim. Si d'aquesta manera no es pot saber el tipus d'òptim caldrà recórrer al menor orlat o ampliat. Si el resultat d'aquest és menor que 0, s'obté que és un mínim, mentre que, si és major que 0, es tracta d'un màxim.

Esquema d'estudi generals d'aquest tipus de problemes:

1. D'entrada, cal formular el problema de manera que amb un costat es tingui la funció que es vol optimitzar, i a sota la restricció a la qual es troba sotmesa la funció.
2. A continuació cal fer les derivades parcials i igualar-les a zero per trobar els punts crítics.
3. Classificar els punts crítics en funció de la seva naturalesa, és a dir, si es tracta d'un mínim o d'un màxim.
4. Comprovar els límits de la funció, és a dir, les fronteres i els vèrtexs on també i s'hi poden trobar possibles punts crítics.

Optimització amb restriccions de desigualtat

En aquest tipus d'optimització existeixen les anomenades condicions de Kuhn-Tucker, les quals, en alguns casos, poden ser utilitzades per intentar trobar punts crítics (màxims o mínims). No obstant això, aquesta és una àrea molt poc desenvolupada de la matemàtica. Les condicions de Khun-Tucker fallen freqüentment o són insuficients per trobar l'existència d'extrems.

Optimització estocàstica

Quan les variables del problema (funció objectiu i/o restriccions) són variables aleatòries, es realitza optimització estocàstica.

Optimització amb informació no perfecta

En aquest cas, la quantitat de variables o la funció objectiu poden ser desconegudes o una variable més. La matemàtica coneguda com a matemàtica borrosa es troba actualment intentant resoldre aquest tipus de problemes, però el desenvolupament d'aquest camp de la matemàtica és encara massa incipient, i fins ara els resultats obtinguts han sigut escassos.

Vegeu també

• Descomposició de Benders
• Programació lineal entera
• Programació no lineal
• Màxims i mínims
• Problema del recobriment

Enllaços externs

• COIN-OR — Computational Infrastructure for Operations Research (anglès)
• Decision Tree for Optimization Software — Enllaços a codis font d'optimització (anglès)
• Global optimization Arxivat 2008-12-28 a Wayback Machine. — Optimització global (anglès)
• Mathematical Programming Glossary Arxivat 2010-03-28 a Wayback Machine. (anglès)