Optimización matemática: Diferenzas entre revisións

[[Ficheiro:MaximumParaboloid.png|miniatura| Gráfico dun [[paraboloide]] dado por f(x,ey) = -(x²+ey²)+4. O [[Extremos dunha función|máximo]] global en (0,  0,  4) está indicado por un punto vermello.]]

No caso máis simple, un [[problema de optimización]] consiste en [[Extremos dunha función|maximizar ou minimizar]] unha [[función]] real escollendo sistematicamente [[Magnitude matemática|valores]] de entrada (tomados dun conxunto permitido) e computando o valor da función. A xeneralización da teoría da optimización e das técnicas para outras formulacións comprende unha grande área dasda [[Matemáticamatemática aplicada|matemáticas aplicadas.]]. De forma xeral, a optimización inclúe o descubrimento dos "mellores valores" dalgunha función obxectivo dado un dominio definido, incluíndo unha variedade de diferentes tipos de funcións obxectivo e diferentes tipos de [[Dominio de definición|dominios]].

Tipicamente, ''A'' é algún [[Subconjunto|subconxunto]] do [[espazo euclidiano]] Rn, con frecuencia delimitado por un conxunto de restricións, igualdades ou desigualdades que os elementos de ''A'' teñen que satisfacer. O [[Dominio de definición|dominio]] ''A'' de ''f'' chámase ''espazo de procura'' ou o ''conxunto de elección'', mentres que os elementos de ''A'' se chaman ''solucións factibles''.

A función ''f'' chámase '''función obxectivo''', '''función de custo''' (minimización), función de utilidade (maximización), '''función de utilidade''' indirecta (minimización), ou, en certos campos, '''función de enerxía''', ou '''enerxía''' '''funcional.'''<ref>W. Erwin Diewert (2008). "costCost functions," ''The New Palgrave Dictionary of Economics'', 2nd Edition [http://www.dictionaryofeconomics.com/article?id=pde2008_C000390&edition=current&q= Contents].</ref><ref>[//es.wikipedia.org/wiki/Peter_Kenneth_Newmand Peter Newman] (2008). "indirect utility function," ''The New Palgrave Dictionary of Economics'', 2nd Edition. </ref> Unha solución factible que minimice (ou maximice) a función obxectivo, chámase ''solución óptima''.

Por convenio, o formato estándar dun problema de optimización realízase en termos de minimización. Xeralmente, a menos que ambas, a función obxectivo e a rexión factible sexan convexas nun problema de minimización, pode haber varios mínimos locais, onde un mínimo local x* se defínesedefine como un punto para o que existe algún δ &#x3E; 0, onde para todo x tal que

Un gran número de algoritmos propostos para resolver problemas non convexos, incluíndo a maioría dos solucionadores dispoñibles comercialmente, non son capaces de facer unha distinción entre solucións óptimas locais e solucións óptimas rigorosas, e tratan as primeiras como solucións actuais do problema orixinal. A rama das [[Matemáticamatemática aplicada|matemáticas aplicadas]] e a [[análise numérica]] que trata do desenvolvemento de algoritmos deterministas que son capaces de garantir converxencia en tempo finito á solución óptima real dun problema non convexo chámase optimización global.

que minimiza (ou minimizan) a función obxectivo x2''x''² + 1 (e non o valor mínimo que alcanza a función obxectivo para devanditos valores). Neste caso, a resposta é ''x'' = -1, posto que ''x'' = 0 non é factible, é dicir non pertence ao dominio do problema.

(novamente, o valor máximo da función non importa).<math /> Neste caso, as solucións son os pares da forma (5, 2''k''π) e (−5,(2k2''k''+1)π), onde ''k'' percorre todos os [[Número enteiro|enteiros]].

[[Pierre de Fermat]] e [[Joseph Louis Lagrange]] atoparon fórmulas baseadas no cálculo para identificar valores óptimos, mentres que [[Isaac Newton]] e [[Carl Friedrich Gauss]] propuxeron métodos iterativos para aproximar o óptimo. Historicamente, o termo [[programación linear]] para referirse a certos problemas de optimización débese a [[George B. Dantzig]], aínda que gran parte da teoría fora introducida por [[Leonid Kantorovich]] en 1939. Dantzig publicou o [[Algoritmo símplex|algoritmo do símplex]] en 1947 e [[John von Neumann]] desenvolveu a teoría da [[Dualidad (matemáticas)|dualidade]] no mesmo ano.

* ''Satisfacción de restrición'': estuda o caso no cal a función obxectivo f é constante (esta se emprega en [[intelixencia artificial]], particularmente en [[Razonamiento automatizado|razoamento automatizado]]).

* ''[[Cálculo de variaciones|Cálculo de variacións]]'': busca optimizar un obxectivo definido sobre moitos puntos co tempo, considerando como a función obxectivo cambia se o cambio é pequeno no camiño de escolla. A teoría do [[control óptimo]] é unha xeneralización deste.

Un dos teoremas de Fermat asegura que os óptimos dos problemas sen restricións se atopan nos [[puntos estacionarios]], onde a primeira [[derivada]] da función obxectivo é cero (ou o seu [[gradiente]] nulo). De forma máis xeral, tamén poden atoparse nos puntos críticos onde a primeira derivada ou o gradiente da función obxectivo non está definido, ou na [[FronteraFronteira (topologíatopoloxía)|fronteira]] do conxunto de escolla. Unha ecuación (ou conxunto de ecuacións) indicando que a(s) primeira(s) derivada(s) é(son) igual(iguais) a cero nun óptimo interior chámase unha condición de primeira orde ou un conxunto de condicións de primeira orde.

Os óptimos dos problemas con restricións de desigualdade atópanse en cambio mediante o método dos [[Multiplicadores de Lagrange|multiplicadores de Lagrange.]]. Este método computa un sistema de desigualdades chamado condicións de Karush–Kuhn–Tucker ou condicións de folguras complementarias, que se empregan para calcular o óptimo.

Mentres a proba da primeira derivada identifica os puntos que poden ser extremos, esta proba non distingue se un punto é mínimo, máximo ou ningún dos dous. Cando a función obxectivo é dúas veces diferenciable, estes casos poden distinguirse estudando a segunda derivada ou a matriz das segundas derivadas (chamada [[matriz hessiana]]), en problemas sen restricións, ou a matriz das segundas derivadas da función obxectivo e das restricións chamada a matriz hessiana orlada, en problemas con restricións.

As condicións que distinguen os máximos ou mínimos doutros puntos estacionarios chámanse condicións de segunda orde'''.''' Se un candidato a solución satisfai as condicións de primeira orde e as condicións de segunda orde tamén, é suficiente para establecer, polo menos, optimalidade local.

Ademais, os puntos críticos poden ser clasificados usando a definitude da [[Matriz Hessiana|matriz hessiana]]: se é ''[[Matriz definida positiva|definida positiva]]'' nun punto crítico, entón o punto é un mínimo local; se é ''definida negativa'', entón o punto é un máximo local; finalmente, se é ''indefinida'', entón o punto é algún tipo de [[Punto de ensilladura|punto de sela]].

Para resolver problemas, os investigadores poden usar [[Algoritmo|algoritmosalgoritmo]]s que terminen nun número finito de pasos, ou [[métodos iterativos]] que converxen a unha solución (nalgunha clase específica de problemas), ou heurísticas que poden prover solucións aproximadas a algúns problemas (aínda que as súas iteracións non converxen necesariamente).

Os [[métodos iterativos]] usados para resolver problemas de [[programación non linear]] difiren segundo o que avalíen: hessianas, gradientes, ou soamente valores de función. Mentres que avaliando hessianas (H) e gradientes (G) mellórase a velocidade de converxencia, tales avaliacións aumentan a [[Complejidad computacional|complexidade computacional]] (ou custo computacional) de cada iteración. Nalgúns casos, a complexidade computacional pode ser excesivamente alta.

Ademais dos [[Algoritmo|algoritmosalgoritmo]]s (terminación finita) e os métodos iterativos (converxentes), existen métodos heurísticos que poden prover solucións aproximadas a algúns problemas de optimización:

* [[Optimización por enjambre de partículas|Optimización por enxame de partículas]].

== LigazónsVéxase externastamén ==