Epälineaarinen ohjelmointi - Nonlinear programming

On matematiikka , epälineaarinen ohjelmointi ( NLP ) on prosessi, jossa selvittämistä varten optimoinnin ongelma , jossa joitakin rajoituksia tai kohdefunktion ovat epälineaarisia . Optimointi ongelma on yksi laskettaessa ääriarvon (maksimi, minimit tai paikallaan olevia), joka objektiivinen funktio yli joukon tuntematon todelliset muuttujat ja ehdollinen tyydyttävällä tavalla järjestelmä on yhtälöt ja epätasa , joita kutsutaan yhteisesti rajoitteet . Matemaattisen optimoinnin osa-alue käsittelee ongelmia, jotka eivät ole lineaarisia.

Soveltuvuus

Tyypillinen ei- kupera ongelma on kuljetuskustannusten optimointi valitsemalla joukko kuljetusmenetelmiä, joista yhdellä tai useammalla on mittakaavaetuja erilaisilla yhteyksillä ja kapasiteettirajoituksilla. Esimerkkinä voidaan mainita öljytuotteiden kuljetus, jos se on valittu tai yhdistetty putkistoon, rautateiden säiliöalukseen, säiliöalukseen, jokialukseen tai rannikkotankkiin. Taloudellisen erän koon vuoksi kustannustoiminnoissa voi olla keskeytyksiä sujuvien muutosten lisäksi.

Kokeellisessa tieteessä joitakin yksinkertaisia ​​tietoanalyysejä (kuten spektrin sovittaminen yhteen tunnetun sijainnin ja muodon huippujen summan kanssa, jonka suuruus on tuntematon) voidaan tehdä lineaarisilla menetelmillä, mutta yleensä nämä ongelmat ovat myös epälineaarisia. Tyypillisesti on olemassa teoreettinen malli tutkittavasta järjestelmästä, jossa on muuttuvat parametrit, ja malli kokeesta tai kokeista, joilla voi olla myös tuntemattomia parametreja. Yritetään löytää numeerisesti paras sovitus. Tässä tapauksessa halutaan usein mitata tuloksen tarkkuus ja paras sovitus itse.

Määritelmä

Olkoon n , m ja p positiivisia kokonaislukuja. Olkoon X on osajoukko R ⁿ , anna f , g _i , ja h _j on reaaliarvoinen toimintoja on X kullekin i in { 1 , ..., m } ja kukin j on { 1 , ..., p }, jossa on ainakin yksi f , g _i ja h _j on epälineaarinen.

Epälineaarinen minimointitehtävä on lomakkeen optimointitehtävä

${\ displaystyle {\ begin {aligned} {\ text {minimalize}} & f (x) \\ {\ text {subject to}} & g_ {i} (x) \ leq 0 {\ text {for each}} i \ \ {1, \ piste, m \} \\ & h_ {j} (x) = 0 {\ teksti {jokaiselle}} j \ in \ {1, \ piste, p \} \\ & x \ X: ssä. \ end {aligned}}}$

Epälineaarinen maksimointitehtävä määritellään samalla tavalla.

Mahdolliset rajoitussarjat

Rajoitusjoukon luonteelle on useita mahdollisuuksia, joka tunnetaan myös nimellä toteutettavissa oleva joukko tai toteutettavissa oleva alue .

Mahdotonta ongelma on sellainen, johon ei arvomaailman valintaan muuttujat täyttää kaikki rajoitteet. Toisin sanoen rajoitukset ovat keskenään ristiriitaisia, eikä ratkaisua ole olemassa; mahdollinen joukko on tyhjä sarja .

Mahdollista ongelma on yksi, joka on olemassa ainakin yhdet arvojen valinta muuttujien täyttää kaikki rajoitteet.

Rajaton ongelma on toteutettavissa ongelma, johon kohdefunktion voidaan tehdä parempi tahansa äärellinen arvo. Optimaalista ratkaisua ei siis ole, koska aina on olemassa mahdollinen ratkaisu, joka antaa paremman objektiivisen funktion arvon kuin mikään ehdotettu ratkaisu.

Menetelmät ongelman ratkaisemiseksi

Jos tavoitefunktio on kovera (maksimointitehtävä) tai kupera (minimointitehtävä) ja rajoitusjoukko on kupera , ohjelmaa kutsutaan kuperaksi ja useimmissa tapauksissa voidaan käyttää yleisiä menetelmiä kuperasta optimoinnista .

Jos kohdefunktio on toisen asteen ja rajoitukset ovat lineaarisia, käytetään toisen asteen ohjelmointitekniikoita .

Jos tavoitefunktio on koveran ja kupera funktion suhde (maksimointitapauksessa) ja rajoitukset ovat kuperat, ongelma voidaan muuntaa kuperaksi optimointitehtäväksi murto -ohjelmointitekniikoilla .

Ei -kuperien ongelmien ratkaisemiseksi on saatavilla useita menetelmiä. Yksi lähestymistapa on käyttää lineaaristen ohjelmointitehtävien erityisiä muotoiluja. Toinen menetelmä sisältää haarautumis- ja sidottujen tekniikoiden käytön, jossa ohjelma on jaettu alaluokkiin, jotka on ratkaistava kuperalla (minimointitehtävä) tai lineaarisella arvioinnilla, jotka muodostavat alarajan kokonaiskustannuksille. Myöhemmillä jakamisilla saadaan jossain vaiheessa todellinen ratkaisu, jonka kustannukset ovat yhtä suuret kuin mikä tahansa likimääräinen ratkaisu. Tämä ratkaisu on optimaalinen, vaikkakaan ei ehkä ainutlaatuinen. Algoritmi voidaan myös pysäyttää aikaisin varmistaen, että paras mahdollinen ratkaisu on toleranssin sisällä parhaasta löydetystä kohdasta; tällaisia ​​pisteitä kutsutaan ε-optimaalisiksi. Päättäminen ε-optimaalisiin pisteisiin on tyypillisesti välttämätöntä, jotta voidaan varmistaa rajallinen päättyminen. Tämä on erityisen hyödyllistä suurissa, vaikeissa ongelmissa ja epävarmoihin kustannuksiin tai arvoihin liittyvissä ongelmissa, joissa epävarmuus voidaan arvioida asianmukaisella luotettavuusarvioinnilla.

Alle differentiability ja rajoitus pätevyys , Karush-Kuhn-Tucker (KKT) olosuhteet tarjoavat tarvittavat edellytykset ratkaisu olisi optimaalista. Kupeudessa nämä olosuhteet ovat myös riittävät. Jos jotkut toiminnot eivät ole derivoituva, subdifferential versioita Karush-Kuhn-Tucker (KKT) olosuhteet ovat käytettävissä.

Esimerkkejä

2-ulotteinen esimerkki

Sininen alue on toteutettavissa oleva alue . Tangency linjan kanssa toteutettavissa alue edustaa ratkaisu. Viiva on paras saavutettavissa oleva ääriviiva (lokus, jolla on kohdefunktion arvo).

Yksinkertainen ongelma (esitetty kaaviossa) voidaan määritellä rajoituksilla

x ₁ ≥ 0

x ₂ ≥ 0

x ₁ ² + x ₂ ² ≥ 1

x ₁ ² + x ₂ ² ≤ 2

joiden tavoitefunktio on maksimoitava

f ( x ) = x ₁ + x ₂

missä x = ( x ₁ , x ₂ ).

3-ulotteinen esimerkki

Ratkaisu on yläpinnan tangentti ja rajallinen tila keskellä.

Toinen yksinkertainen ongelma (katso kaavio) voidaan määritellä rajoituksilla

x ₁ ² - x ₂ ² + x ₃ ² ≤ 2

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

joiden tavoitefunktio on maksimoitava

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

missä x = ( x ₁ , x ₂ , x ₃ ).

Katso myös

• Käyrän sovitus
• Pienimmän neliön minimointi
• Lineaarinen ohjelmointi
• nl (muoto)
• Epälineaariset pienimmät neliöt
• Luettelo optimointiohjelmistoista
• Neliöllisesti rajoitettu toisen asteen ohjelmointi
• Werner Fenchel , joka loi perustan epälineaariselle ohjelmoinnille

Viitteet

Lue lisää

• Avriel, Mordecai (2003). Epälineaarinen ohjelmointi: analyysi ja menetelmät. Dover Publishing. ISBN  0-486-43227-0 .
• Bazaraa, Mokhtar S. ja Shetty, CM (1979). Epälineaarinen ohjelmointi. Teoria ja algoritmit. John Wiley & Sons. ISBN  0-471-78610-1 .
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Numeerinen optimointi: Teoreettiset ja käytännön näkökohdat . Universitext (Toinen tarkistettu painos käännöksestä 1997 ranskalainen toim.). Berliini: Springer-Verlag. s. xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-X. MR  2265882 .
• Luenberger, David G .; Niin, Yinyu (2008). Lineaarinen ja epälineaarinen ohjelmointi . Kansainvälinen operaatiotutkimuksen ja johtamistieteen sarja. 116 (kolmas painos). New York: Springer. s. xiv+546. ISBN 978-0-387-74502-2. MR  2423726 .
• Nocedal, Jorge ja Wright, Stephen J. (1999). Numeerinen optimointi. Springer. ISBN  0-387-98793-2 .
• Jan Brinkhuis ja Vladimir Tikhomirov, Optimization: Insights and Applications , 2005, Princeton University Press

Ulkoiset linkit

• Matemaattisen ohjelmoinnin sanasto