Optimisació (matemàtica)

En matemàticas, estadística, economia, ciències empíriques i ciència de la computació, la optimisació (també, optimisació matemàtica o programació matemàtica) és la selecció del millor element (sobre algun criteri) d'un conjunt d'elements disponibles. l'investigació operativa és un dels camps de la matemàtica en les bases de la qual funciona l'optimisació.

En el cas més simple, un problema d'optimisació consistix en maximizar o minimisar una funció real elegint sistemàticament valors d'entrada (presos d'un conjunt permés) i computant el valor de la funció. La generalisació de la teoria de l'optimisació i tècniques per a atres #formulació comprén un àrea gran de les matemàtiques aplicades. De forma general, l'optimisació inclou el descobriment dels "millors valors" d'alguna funció objectiu dau un domini definit, incloent una varietat de diferents tipos de funcions objectiu i diferents tipos de dominis.

Optimisació fa referència a l'acció i efecte d'optimisar. En térmens generals, es referix a la capacitat de fer o resoldre alguna cosa de la manera més eficient possible i, en el millor dels casos, utilisant la menor cantitat de recursos.

En les últimes décades, el terme optimisació s'ha vinculat al món de l'informàtica. No obstant, és un concepte que també s'utilisa en les matemàtiques, en la gestió de processos i l'economia.

Problemes d'optimisació

Un problema d'optimisació pot ser representat de la següent forma:

Donada: una funció f : A $\to$ R.

Buscar: un element x₀ en A tal que f(x₀) ≤ f(x) para tot x en A («minimisació») o tal que f(x₀) ≥ f(x) para tot x en A («maximización»).

Tal formulació és cridada un problema d'optimisació o un problema de programació matemàtica (un terme no directament relacionat en la programació de computadores pero encara en us, per eixemple en la programació llineal - vejau la secció Història). Molts problemes teòrics i del món real poden ser modelats per mig d'este esquema general. Problemes formulats usant esta tècnica en els camps de física i visió per computadora es referixen a la tècnica com a minimisació de l'energia, parlant del valor de la funció f representant l'energia del sistema que està sent modelació.

Típicament, A és algun subconjunt del espai euclídeo Rⁿ, en freqüència delimitat per un conjunt de restriccions, igualtats o desigualtats que els elements de A tenen que satisfer. El domini A de f és cridat el espai de busca o el conjunt d'elecció, mentres que els elements de A sò cridats soluciones candidates o solucions factibles.

La funció f és cridada, diversamente, funció objectiu, funció de cost (minimisació), funció d'utilitat (maximización), funció d'utilitat indirecta (minimisació), o, en certs camps, funció d'energia, o energia funcional. Una solució factible que minimise (o maximizar, si este és el propòsit) la funció objectiu, és cridada una solució òptima.

Per conveni, el format estàndar d'un problema d'optimisació està declarat en térmens de minimisació. Generalment, a menos que abdós, la funció objectiu i la regió factible siguen convexas en un problema de minimisació, pot haver varis mínims locals, a on un mínim local x^* es definix com un punt per al qual existix algun δ > 0, a on para tot x tal que

$\Vert 𝐱-{𝐱}^{\star }\Vert \le \delta$

l'expressió

$f({𝐱}^{\star })\le f(𝐱)$

és verdadera; és dir, en alguna regió al voltant de x^*, tots els valors de la funció són majors que o iguals al valor en eixe punt. El màxim local es definix de modo similar.

Un gran número d'algoritmes proposts per a resoldre problemes no-convexos – incloent a la majoria dels solucionadores disponibles comercialment – no són capaços de fer una distinció entre solucions òptimes locals i solucions òptimes rigoroses, i tracten a les primeres com a solucions actuals del problema original. La branca de les matemàtiques aplicades i l'anàlisis numèric que es responsabilisa en el desenroll d'algoritmes determinista que són capaços de garantisar convergència en temps finito a la solució òptima real d'un problema no convexo es diu optimisació global.

Notació

Els problemes d'optimisació s'expressen a sovint en una notació especial. A continuació es mostren alguns eixemples.

Mínim i Màxim valor d'una funció

Considere la següent notació:

$\underset{x\in ℝ}{\min }(x^2+1)$

Esta denota el valor mínim de la funció objectiu $x^2+1$, quan x se selecciona del conjunt de número real $ℝ$. El valor mínim en este cas és $1$ i ocorre per a $x=0$.

De modo similar, la notació

$\underset{x\in ℝ}{\max }2x$

expressa el valor màxim de la funció objectiu 2x, sent x qualsevol número real. En este cas, no existix tal màxim, després no hi ha un valor òptim acotat.

Arguments de l'entrada òptima

Considere's la següent expressió:

o de manera equivalent

Esta representa el valor (o valors) del argument de x en l'interval $(-\mathrm{\infty },-1]$ que minimisen (o maximizar) la funció objectiu x² + 1 (i no el valor mínim que alcança la funció objectiu para dits valors). En este cas, la resposta és x = -1, ya que x = 0 no és factible, és dir no pertany al domini del problema.

De modo similar,

$\underset{x\in [-5,5],y\in ℝ}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}x\cos (y),$

que equivalent a

$\underset{x,y}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}x\cos (y),\text{sujeto a:}x\in [-5,5],y\in ℝ,$

representa al parell (o parells) (x,i) que minimisen (o maximizar) el valor de la funció objectiu xcos(i), en la restricció afegida de que x es troba en l'interval [-5,5] (novament, el valor mínim de la funció no importa). En este cas, les solucions són els parells de la forma (5, 2kπ) i (−5,(2k+1)π), a on k recorre tots els sancers.

Arg min i arg max a voltes apareixen escrits com argmin i argmax, i volen dir argument del mínim i argument del màxim.

Història

Pierre de Fermat i Joseph Louis Lagrange varen trobar fòrmules basades en el càlcul per a identificar valors òptims, mentres que Isaac Newton i Carl Friedrich Gauss varen propondre métodos iterativos per a aproximar l'òptim. Històricament, el terme programació llineal per a referir-se a certs problemes d'optimisació es deu a George B. Dantzig, encara que gran part de la teoria havia segut introduïda per Leonid Kantorovich en 1939. Dantzig va publicar l'Algoritme símplex en 1947 i John von Neumann va desenrollar la teoria de la dualitat en el mateix any.

El terme programació en este context no es referix a la programació de computadores. Més be, el terme ve de l'us de programa per l'eixèrcit d'Estats Units en referir-se a la proposta d'entrenament i planificació llogística, el qual va anar el problema estudiat per Dantzig en aquell llavors.

Atres investigadors importants en el camp de l'optimisació matemàtica varen ser els següents:^{cita requerida}

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 Cunyes

Subcampos principals

• Programació convexa estudia el cas en que la funció objectiu és convexa (minimisació) o cóncava (maximización) i el conjunt de restriccions és convexo. Est pot ser vist com un cas particular de la programació no llineal o com la generalisació de la programació llineal o de la convexa quadràtica.
  • Programació llineal (PL): és un tipo de programació convexa, en el que la funció objectiu f és llineal i el conjunt de restriccions s'especifica usant solament equacions i inecuaciones llineals. Dit conjunt és cridat poliedre o politopo si està acotat.
  • Programació cònica: és una forma general de la programació convexa. PL, PCSO i PSD poden tots ser vists com a programes cònics en el tipo de con apropiat.
  • Programació de con de segon orde (PCSO): és un tipo de programació convexa i inclou certs tipos de problemes de programació quadràtica.
  • Programació semidefinida (PSD): és un subcampo de l'optimisació convexa a on les variables fonamentals són matrius semidefinidas. És una generalisació de la programació llineal i la programació quadràtica convexa.
  • Programació geomètrica: és una tècnica per mig de la qual l'objectiu i les restriccions de desigualtat expressats com polinomis i les restriccions d'igualtat com monomis, poden ser transformats en un programa convexo.
  • Programació en sancers o Programació sancera: estudia programes llineals en els quals algunes o totes les variables estan obligades a prendre valors sancers. Esta no és convexa i en general és molt més complexa que la programació llineal regular.
• Programació quadràtica: permet a la funció objectiu tindre térmens quadràtics, mentres que el conjunt factible pot ser especificat en equacions i inecuaciones llineals. Per a formes específiques del terme quadràtic, esta és un tipo de programació convexa.
• Programació fraccionaria: estudia l'optimisació de raons de dos funcions no llineals. La classe especial de programes fraccionarios cóncaus pot ser transformada a un problema d'optimisació convexa.
• Programació no llineal: estudia el cas general en el que la funció objectiu, o les restriccions, o abdós, contenen parts no llineals. Est pot o no, ser un programa convexo. En general, si el programa és convexo afecta la dificultat de resolució.
• Programació estocàstica o Optimisació estocàstica: estudia el cas en el que alguna de les restriccions o paràmetros depén de variables aleatòries.
• Programació robusta: com la programació estocàstica, és un intent per capturar l'incertitut en les senyes fonamentals del problema d'optimisació. Açò es fa per mig de l'us de variables aleatòries, pero en canvi, el problema és resolt tenint en conte imprecisions en les senyes d'entrada.
• Optimisació combinatòria: es preocupa dels problemes a on el conjunt de solucions factibles és discret o pot ser reduït a un.
• Optimisació dimensional-infinita: estudia el cas a on el conjunt de solucions factibles és un subconjunt d'un espai de dimensió infinita, per eixemple un espai de funcions.
• Heurístiques i Metaheurísticas: fan suposicions sobre el problema que està sent optimisat. Usualment, les heurístiques no garantisen que qualsevol solució òptima siga trobada. Després, les heurístiques són usades per a trobar solucions aproximades per a molts problemes d'optimisació complicats.
• Satisfacció de restricció: estudia el cas en el qual la funció objectiu f és constant (esta és usada en inteligència artificial, particularment en raonament automatizado).
• Programació disyuntiva: s'usa quan a lo manco una restricció pot ser satisfeta pero no totes. Esta és d'us particular en la programació en un número de subcampos. Les tècniques són dissenyades principalment per a l'optimisació en contexts dinàmics (és dir, presa de decisions en el transcurs del temps).

• Càlcul de variacions: busca optimisar un objectiu definit sobre molts punts en el temps, considerant com la funció objectiu canvia si el canvi és menut en el camí d'elecció. La tècnica del control òptim és una generalisació d'est.
• Programació dinàmica estudia el cas en el que l'estratègia d'optimisació es basa en la divisió del problema en subproblemas més menuts. L'equació que descriu la relació entre estos subproblemas es diu equació de Bellman.
• Programació matemàtica en restriccions d'equilibri és a on les restriccions inclouen desigualtats variables o complementàries.

Classificació de punts crítics i extrems

Factibilidad del problema

La solubilidad del problema, també cridada factibilidad del problema, és la qüestió de si existix alguna solució factible, al marge del seu valor objectiu. Est pot ser considerat com el cas especial de l'optimisació matemàtica a on el valor objectiu és el mateix per a tota solució, i aixina qualsevol solució és òptima.

Molts algoritmes d'optimisació necessiten començar a partir d'un punt factible. Una via per a obtindre tal punt és relaixar les condicions de factibilidad usant una variable de chala; en suficient chala, qualsevol punt de partida és factible. Llavors, es minimisa eixa variable de chala fins que la chala siga nula o negativa.

Existència

El teorema de Weierstrass afirma que una funció real i contínua en un conjunt compacte alcança el seu valor màxim i mínim. De forma més general, una funció semi-contínua inferior en un conjunt compacte alcança el seu mínim; una funció semi-contínua superior en un conjunt compacte alcança el seu màxim.

Condicions necessàries de optimalidad

Un de les teoremes de Fermat assegura que els òptims dels problemes irrestrictos són trobats en els punts estacionarios, a on la primera derivada de la funció objectiu és zero (o el seu gradient nul). De forma més general, també poden ser trobats en els punts crítics a on la primera derivada o el gradient de la funció objectiu no està definit, o en la frontera del conjunt d'elecció. Una equació (o conjunt d'equacions) indicant que la(s) primera(s) derivada(s) és(són) igual(és) a zero en un òptim interior es diu una condició de primer orde o un conjunt de condicions de primer orde.

Els òptims dels problemes en restriccions de desigualtat són en canvi trobats per mig del método dels multiplicadors de Lagrange. Este método computa un sistema de desigualtats anomenat Condicions de Karush–Kuhn–Tucker o condicions de chales complementàries, les quals s'usen llavors per a calcular l'òptim.

Condicions suficients de optimalidad

Mentres la prova de la primera derivada identifica els punts que poden ser extrems, esta prova no distinguix si un punt és mínim, màxim, o cap dels dos. Quan la funció objectiu és dos voltes diferenciable, estos casos poden ser distinguits estudiant la segona derivada o la matriu de les segones derivades (cridada matriu Hessiana),en problemes irrestrictos, o la matriu de les segones derivades de la funció objectiu i les restriccions anomenada la matriu Hessiana orlada, en problemes restrictos.

Les condicions que distinguixen als màxims, o mínims, d'atres punts estacionarios són cridades condicions de segon orde. Si un candidat a solució satisfà les condicions de primer orde i les condicions de segon orde també, és suficient per a establir, a lo manco, optimalidad local.

Sensibilitat i continuïtat de l'òptim

La teorema de la envoltura descriu com el valor d'una solució òptima canvia quan un paràmetro subjacent canvia. El procés que computa este canvi és cridat estàtica comparativa.

La teorema del màxim de Claude Berge (1963) descriu la continuïtat d'una solució òptima com una funció de paràmetros subjacents.

Càlculs d'optimisació

Per als problemes irrestrictos en funcions dos voltes diferenciables, alguns punts crítics poden ser trobats detectant els punts a on el gradient de la funció objectiu és zero (és dir, els punts estacionarios). De forma més general, un subgradiente zero certifica que un mínim local ha segut trobat per als problemes de minimisació en funcions convexas o unes atres funcions de Lipschitz.

Ademés, els punts crítics poden ser classificats usant la definitud de la matriu Hessiana: si és definida positiva en un punt crític, llavors el punt és un mínim local; si és definida negativa, llavors el punt és un màxim local; finalment, si és indefinida, llavors el punt és algun tipo de punt de ensilladura.

Els problemes restrictos poden en freqüència ser transformats en problemes irrestrictos en ajuda dels multiplicadors de Lagrange. La relaixació Lagrangiana pugues també proveir solucions aproximades a difícils problemes restrictos.

Quan la funció objectiu és convexa, llavors qualsevol mínim local serà també un mínim global. Existixen tècniques numèriques eficients per a minimisar funcions convexas, per eixemple els métodos de punt interior.

Tècniques d'optimisació computacional

Per a resoldre problemes, els investigadors poden usar algoritmes que terminen en un número finito de passos, o métodos iterativos que convergixen a una solució (en alguna classe específica de problemes), o heurístiques que poden proveir solucions aproximades a alguns problemes (encara que els seus iteraciones no convergixen necessàriament).

Algoritmes d'optimisació

• Algoritme Simplex de George Dantzig, dissenyat per a la programació llineal.
• Extensions de l'algoritme Simplex, dissenyats per a la programació quadràtica i per a la programació llineal-fraccionaria.
• Variants de l'algoritme Simplex que són especialment apropiades per a l'optimisació de rets.
• Algoritmes combinatoris.

Métodos iterativos

Els métodos iterativos usats per a resoldre problemes de programació no llineal diferixen segons lo que evaluen: Hessianas, #gradient, o solament valors de funció. Mentres que evaluant Hessianas (H) i #gradient (G) millora la velocitat de convergència, tals evaluacions aumenten la complexitat computacional (o cost computacional) de cada iteración. En alguns casos, la complexitat computacional pot ser excessivament alta.

Un important criteri per als optimizadores és just el número d'evaluacions de funcions requerit, com este en freqüència és de per sí un gran esforç computacional, usualment molt més esforce que el del optimizador en sí, ya que en la seua majoria té que operar sobre N variables. Les derivades proveïxen informació detallada per als optimizadores, pero són encara més costoses de calcular, per eixemple aproximant el gradient pren a lo manco N+1 evaluacions de funcions. Per a l'aproximació de les segones derivades (agrupades en la matriu Hessiana) el número d'evaluacions de funcions és d'orde N². El método de Newton requerix les derivades de Segon orde, per lo tant per cada iteración el número de cridades a funció és d'orde N², pero per al optimizador d'un gradient pur més simple és d'orde N. No obstant, els optimizadores de gradient necessiten usualment més iteraciones que l'algoritme de Newton. Ser millor sobre el número de cridades a funcions depén del problema en sí.

Métodos que evaluen Hessianas (o aproximen Hessianas, usant diferències finitas):

• • Método de Newton.
    • Programació seqüencial quadràtica: un método de Newton basat en problemes restrictos de menuda-mijana escala. Algunes versions poden manejar problemes de gran dimensió.
• Métodos que evaluen #gradient o aproximen #gradient usant diferències finitas (o inclús subgradientes):
  • Métodos Quasi-Newton: métodos iterativos per a problemes mijans-grans (eixemple N<1000).
  • Métodos de gradient conjugat: métodos iterativos per a problemes grans. (En teoria, estos métodos terminen en un número finito de passos en funcions objectiu quadràtiques, pero esta terminació finita no s'observa en la pràctica en computadores de precisió finita.)

• • Métodos de punt interior: esta és una gran classe de métodos per a l'optimisació restricta. Alguns métodos de punt interior usen solament informació del subgradiente, i uns atres requerixen l'evaluació de les Hessianas.
  • Descens del gradient (alternativament, descens pronunciat o ascens pronunciat): un método llent d'interés teòric i històric, el qual ha segut renovat per a trobar solucions aproximades de problemes enormes.
  • Método del subgradiente: un método iterativo per a grans funcions de Lipschitz localment usant #gradient generalisats.
• Métodos que evaluen solament valors de funcions: si un problema és contínuament diferenciable, llavors els #gradient poden ser aproximats usant diferències finitas, en tal cas pot ser usat un método basat en gradient.
  • Métodos d'interpolació.
  • Métodos de busca de patrons, els quals tenen millors propietats de convergència que la heurística de Nelder-Pixeu.

Convergència global

De modo general, si la funció objectiu no és una funció quadràtica, llavors molts métodos d'optimisació usen atres métodos per a garantisar que alguna subsecuencia de iteraciones convergix a una solució òptima. El primer método popular que garantisa convergència es recolza en busques llineals, el qual optimisa una funció en una dimensió. Un segon i popularisat método per a garantisar convergència usa regions de confiança. Abdós busques llineals i regions de confiança són usats en métodos moderns d'optimisació no diferenciable. Usualment un optimizador global és molt més llent que els optimizadores locals alvançats (per eixemple BFGS), per lo tant en freqüència un optimizador global eficient pot ser construït per l'inici del optimizador local de diferents punts de partida.

Heurístiques

Ademés dels algoritmes (terminació finita) i els métodos iterativos (convergents), existixen heurístiques que poden proveir solucions aproximades a alguns problemes d'optimisació:

• Evolució diferencial.
• Algoritme de busca diferencial.
• Relaixació Dinàmica.
• Algoritmes genètics.
• Ascens de montanyes.
• Nelder-Pixeu: una heurística popular per aproximar la minimisació (sense cridades a #gradient).
• Optimisació per eixam de partícules.
• Optimisació artificial de la colónia d'abelles.

Vore també

• Optimisació multiobjetivo
• Eficiència de Pareto
• Multiplicadors de Lagrange
• Optimisació bayesiana

Enllaços externs

• COIN-OR—Computational Infrastructure for Operations Research
• Decision Tree for Optimization Software Links to optimization source codes
• Global optimization
• Archivat el 28 de decembre de 2008 archivat en Wayback Machine.
• Mathematical Programming Glossary
• Mathematical Programming Society
• NEOS Wikicurrently being replaced by the[1] archivat en Wayback Machine.
• Optimization Online A repository for optimization i-prints
• Optimization Related Links
• Convex Optimization I EE364a: Course from Stanford University
• Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization