Programació no llineal

En matemàtiques, la programació no llineal (PNL) és el procés de resolució d'un problema d'optimisació definit per un sistema d'igualtats i desigualtats subjectes a un conjunt de restriccions sobre un conjunt de variables reals desconegudes, en una funció objectiu a maximizar (o minimisar), quan alguna de les restriccions o la funció objectiu no són llineals. És un subcampo de l'optimisació matemàtica que s'ocupa de problemes que no són llineals.

Aplicabilidad

Un problema típic no convexo és el d'optimisar els costs de transport per mig de la selecció d'un conjunt de métodos de transport, un o més dels quals presenten economies d'escala, en diverses conectivitats i restriccions de capacitat. Un eixemple seria el transport de productes petrolífers donada una selecció o combinació de mijos de transport com a oleoducte, camió cisterna, camió cisterna, barcaça fluvial o buc cisterna coster. Pel tamany del lot econòmic, els costs poden presentar tant discontinuïtats com a canvis suaus.

En la ciència experimental, alguns anàlisis de senyes senzills (com l'ajust d'un espectre en una suma de picos d'ubicació i forma conegudes pero de magnitut desconeguda) poden realisar-se en métodos llineals, pero en general estos problemes també són no llineals. Normalment, s'utilisa un model teòric del sistema estudiat en paràmetros variables i també un model de l'experiment o experiments, que també poden tindre paràmetros desconeguts. S'intenta trobar numèricament el millor ajust. En este cas, a sovint es desija obtindre una mida de la precisió del resultat, aixina com el millor ajust en sí.

Formulació matemàtica del problema

Un problema de programació no llineal pot enunciar-se d'una forma molt simple:

Siguen n, m i p sancers positius. Siga X un subconjunt de Rⁿ (generalment en restriccions de caixa), siguen f, g_i, i h_j funcions reals en X per a cada i en {1, ..., m} i cada j en {1, ..., p}, en a lo manco una de f, g_i, i h_j no llineal.

Un problema de programació no llineal és un problema d'optimisació de la forma:

$\underset{x\in X}{\max }f(x)$ maximizar una funció objectiu

o

$\underset{x\in X}{\min }f(x)$ minimisar una funció objectiu (de cost)

a on

$f:R^n\to R$

$X\subseteq R^n.$

Possibles tipos de conjunt de restriccions

Existixen vàries possibilitats per a la naturalea del conjunt de restriccions, també conegut com a conjunt factible o regió factible.

Un problema inviable és aquell en el que cap conjunt de valors de les variables d'elecció satisfà totes les restriccions. És dir, les restriccions són mútuament contradictòries i no existix solució; el conjunt factible és el conjunt buit.

Un problema factible és aquell per al que existix a lo manco un conjunt de valors per a les variables d'elecció que satisfan totes les restriccions.

Un problema illimitat és un problema factible per al qual la funció objectiu pot ser millor que qualsevol valor finito dau. Per tant, no existix una solució òptima, ya que sempre hi ha una solució factible que proporciona un valor de la funció objectiu millor que qualsevol solució proposta.

Alguns casos especials de programació no llineal tenen métodos de solució especialisats:

• Si la funció objectiu és cóncava (problema d'maximización) o convexa (problema de minimisació) i el conjunt de restriccions és convexo, el programa es denomina convexo i, en la majoria dels casos, es poden utilisar métodos generals d'optimisació convexa.

• Si la funció objectiu és quadràtica i les restriccions són llineals, s'utilisen tècniques de programació quadràtica.

• Si la funció objectiu és el cocient d'una funció cóncava i una convexa (en el cas d'maximización) i les restriccions són convexas, el problema pot transformar-se en un problema d'optimisació convexa per mig de tècniques de programació fraccionaria. La programació fraccionaria és una generalisació de la programació llineal-fraccionaria. La funció objectiu en un programa fraccionario és el cocient de dos funcions que, en general, són no llineals. El cocient a optimisar sol descriure algun tipo d'eficiència d'un sistema. A la seua volta, la programació llineal-fraccionaria (PLF) és una generalisació de la programació llineal (PL). Mentres que la funció objectiu en un programa llineal és una funció llineal, la funció objectiu en un programa llineal-fraccionaria és el cocient de dos funcions llineals. Un programa llineal pot considerar-se un cas especial d'un programa llineal-fraccionaria en el que el denominador és la funció constant 1.

Procediment

El problema es remonta a l'optimisació d'una funció auxiliar sense restriccions secundàries (NB) utilisant els métodos que es descriuen a continuació. Per a poder fer us dels métodos basats en #gradient, l'àrea a buscar es dividix en aquelles en les que la funció objectiu és diferenciable. Si és possible, els subdominis deuen ser convexos i també la funció objectiu en ells. Després es pot calcular els extrems globals en les subárea en els métodos enumerats en Optimisació matemàtica i Optimisació convexa i seleccionar l'òptim.

La construcció de la funció auxiliar s'explica en un eixemple: dos boles en un canal intenten alcançar el punt més baix possible, pero no deuen penetrar entre sí. La funció objectiu és per lo tant l'energia potencial de les boles i assumix un mínim en equilibri. La restricció $g(x,y)\le 0$ designaria la intersecció de les esferes $x$ i $y$, a on en negatiu s'entén per penetració una distància positiva.

1. Multiplicadors de Lagrange: Les NB es multipliquen per factors reals, els multiplicadors de Lagrange, i s'incorporen a la funció objectiu de manera que si els multiplicadors de Lagrange són positius, es penalisa la violació de la NB. La funció auxiliar aixina obtinguda es denomina funció de Lagrange. Els multiplicadors de Lagrange s'introduïxen en el problema com a incògnites i també deuen determinar-se. En el cas de les esferes, els multiplicadors de Lagrange no són més que les forces de contacte que les esferes eixercixen entre sí quan es toquen, per a que no es penetren.
2. Funcions de barrera: Les NB es representen en funcions barrera que prenen valors positius a mida que s'aproxima a la frontera del domini de definició i creixen fins a l'infinit en la frontera. Les funciones barrera es multipliquen pels paràmetros barrera $r$ i s'incorporen a la funció objectiu de manera que es penalisa l'aproximació al llímit i s'evita aixina la violació de les NB. En l'image esfèrica, les esferes tindrien un mant més o menys gros, que es torna més i més rígit quant més es comprimix en entrar en contacte. D'esta manera, s'evita la violació de la NB a costa de penalisar inclús l'aproximació al llímit d'alcanç. El método s'utilisa en Procediment de punts interiors.
3. Funcions de penalisació: Les funcions de penalisació s'utilisen de la mateixa manera que les funcions de barrera. Les NB es representen en funcions de penalisació que desapareixen en el ranc admissible i són positives quan es viola el NL. Les funcions de penalisació es multipliquen per paràmetros de penalisació $r$ i s'incorporen a la funció objectiu de manera que es penalisa la violació del NL, d'ahí el seu nom. Ací poden violar-se NB actives i deu comprovar-se la admisibilidad de la solució. En l'image de l'esfera, la funció de penalisació correspon a la penetració "real" (que desapareix quan les esferes estan positivament espayades) i el paràmetro de penalisació correspon a la rigidea d'un moll. El moll intenta tirar dels punts de penetració cap a la superfície. Quant més rígit siga el moll, menor serà la penetració.

1. Método de Lagrange aumentat: És una combinació dels multiplicadors de Lagrange i el método de penalisació. El multiplicador de Lagrange es determina iterativamente en funció de la violació de la NB.
2. Trivial (i per lo tant a sovint no cobert en les fonts), pero aixina i tot val la pena mencionar i en l'us pràctic, és que les NL actives es poden utilisar per a eliminar variables. Les variables es fixen en valors que fan impossible la violació de la NL. En l'image de l'esfera, s'acoplarien els punts de contacte de les esferes (s'igualarien les seues coordenades), de modo que ya no podria produir-se una penetració (allí).

Métodos de resolució del problema

Si la funció objectiu f és llineal i l'espai restringit és un politopo, el problema és de programació llineal i pot resoldre's utilisant algun dels ben coneguts algoritmes de programació llineal.

Si la funció objectiu és cóncava (problema d'maximización), o convexa (problema de minimisació) i el conjunt de restriccions és convexo, llavors es pot utilisar el método general d'optimisació convexa.

Existix una varietat de métodos per a resoldre problemes no convexos. Un d'ells consistix en utilisar #formulació especials de problemes de programació llineal. Un atre método implica l'us de tècniques de Ramificació i poda, quan el problema es dividix en subdivisions a resoldre per mig d'aproximacions que formen un llímit inferior del cost total en cada subdivisió. Per mig de subdivisions successives, s'obtindrà una solució el cost de la qual és igual o inferior que el millor llímit inferior obtingut per alguna de les solucions aproximades. Esta solució és òptima, encara que possiblement no siga única. L'algoritme pot ser parat abans, en la garantia de que la millor solució serà millor que la solució trobada en un percentage acotat. Això s'utilisa en concret en problemes importants i especialment difícils i quan el problema conta en costs incerts o valors a on l'incertitut pot ser estimada en un grau de fiabilitat apropiat.

Les condicions de Karush-Kuhn-Tucker proporcionen les condicions necessàries per a que una solució siga òptima.

S'utilisen algoritmes de solució tals com:

• El método de Newton,
• El método cuasi-Newton,
• El método del gradient conjugat,
• La busca llineal,
• Les regions de confiança,
• El método Nelder-Pixeu,

entre uns atres

Eixemples

Eixemple en dos dimensions

Un problema senzill pot definir-se per les restriccions:

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

en una funció objectiu a ser maximizar

f(x) = x₁ + x₂

a on x = (x₁, x₂)

Eixemple en tres dimensions

Un atre problema simple es definix per la restriccions:x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

en una funció objectiu a ser maximizar

f(x) = x₁x₂ + x₂x₃

a on x = (x₁, x₂, x₃)

Usos

La programació no llineal (PNL) és una ferramenta matemàtica poderosa utilisada per a resoldre problemes d'optimisació en els que la funció objectiu o algunes de les restriccions són no llineals. Estos problemes sorgixen en diversos escenaris de la vida real en diferents indústries, com per eixemple:

Gestió de la cadena de suministrament: en l'optimisació d'una cadena de suministrament, les empresas deuen determinar la millor forma d'assignar recursos, programar la producció i distribuir productes en vàries ubicacions. A sovint, les funcions de cost relacionades en el transport, inventaris i processos de producció són no llineals per factors com els rendiments decreixents en la producció o els costs d'enviament variables en funció de la distància. La PNL s'utilisa per a minimisar els costs totals mentres es complixen les demandes i restriccions de producció.

Optimisació de carteres: els inversionistes busquen maximizar els rendiments mentres minimisen el risc en la seua cartera d'inversions. La relació entre el risc de la cartera (a sovint medit com a varianza) i la seua tornada esperada és no llineal. La PNL ajuda a determinar la combinació òptima d'actius que complixca en restriccions com el presupost i la tolerància al risc, mentres busca el rendiment més alt possible.

Optimisació de sistemes energètics: en la generació d'energia, especialment la renovable, optimisar la combinació de generació és un problema no llineal. Per eixemple, la producció d'energia solar i eòlica depén de condicions ambientals, i l'almagasenament d'energia té costs no llineals associats en l'eficiència i la capacitat. La PNL pot utilisar-se per a determinar la mescla d'energia més rendable, satisfent la demanda i minimisant l'impacte ambiental.

Disseny de processos químics: en l'indústria química, la PNL s'utilisa per a l'optimisació de processos. La relació entre temperatura, pressió i les taxes de reacció química sol ser no llineal. Els models de NLP ajuden a dissenyar reactors, optimisar processos de separació i reduir el desperdici, minimisant el consum d'energia o maximizar la producció.

Aprenentage automàtic i rets neuronals: l'entrenament de rets neuronals és inherentemente un problema d'optimisació no llineal. L'objectiu és minimisar l'error entre les eixides predites i les reals. Els algoritmes de programació no llineal s'utilisen per a ajustar els pesos en una ret de manera eficient i conseguir el millor rendiment.

Vore també

• Optimisació
• Ajust de curves
• Método de mínims quadrats
• Programació llineal
• Werner Fenchel
• Teorema de Brunn-Minkowski
• Conjugada convexa
• Ramificació i poda (Ramificació i acotación)

Bibliografia

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. and Shetty, C. M. (1979). Nonlinear programming. Theory and algorithms. John Wiley & Sons. ISBN 0-471-78610-1.
• Nocedal, Jorge and Wright, Stephen J. (1999). Numerical Optimization. Springer. ISBN 0-387-98793-2.
• Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. ISBN 1-886529-00-0.

Enllaços externs

• Programació no llineal. Eixercicis resolts [1] archivat en Wayback Machine.Plantilla:Pdf

• Programació no llineal en restriccions en desigualtat [2] archivat en Wayback Machine.Plantilla:Pdf
• Programació No Llineal
• Preguntes freqüents de programació no llineal (en anglés)
• Glossari de programació matemàtica (en anglés)
• Nonlinear Programming Survey OR/MS Today

Software

• AIMMS Optimization Modeling AIMMS — Inclou programació no llineal en solucions sectorials (prova debades, llicència de prova disponible);
• AMPL solver software - Debades per a estudiants
• Artelys Knitro optimizador especialisat en programació no llineal (versió de prova disponible)
• GAMS – Versió debades disponible per a estudiants