Optimointi (matematiikka)

Alalla optimointi on sovelletun matematiikan on kyse löytää optimaaliset parametrit - enimmäkseen monimutkainen - järjestelmä. "Optimaalinen" tarkoittaa, että tavoitefunktio minimoidaan tai maksimoidaan. Optimointiongelmia syntyy liiketoiminnan matematiikassa , tilastoissa , operaatiotutkimuksessa ja yleensä kaikilla tieteenaloilla, jotka toimivat tuntemattomilla parametreilla, kuten fysiikka , kemia ja meteorologia . Usein optimointiongelmien analyyttinen ratkaisu ei ole mahdollista, ja on käytettävä numeerisia menetelmiä .

Esimerkki yksinkertaisesta optimointiongelmasta

Yksinkertaisin optimointi ongelma on löytää vähimmäis- tai korkeintaan differentioituva yksiulotteista toiminto , joka saavutetaan tavallisesti löytää nollat ensimmäisen johdannaisen . ${\ displaystyle f (x)}$

Esimerkkejä optimointiongelmista

Liikematematiikka

Tavoitetoiminto edustaa tässä lähinnä yrityksen voittoa tai liikevaihtoa; Parametrit ovat raaka-aineet, henkilöstön käyttö, koneet, hinnat jne. Tavoitetoiminto tulisi maksimoida. Pohjimmiltaan se on yksinkertaistettu hallinnan perusongelman virallistaminen. Se saa systemaattisen perustan Operations Research -tutkimukseen .

Tilastot , tiedonlouhinta

Tilastomallit sisältävät avoimet parametrit, jotka on arvioitu. Parametrijoukko on optimaalinen, jos siihen liittyvä malliesimerkki edustaa datasuhteita optimaalisesti, ts. H. mallinnetun datan (sopivan laatutoiminnon kannalta) poikkeamat empiirisestä tiedosta ovat mahdollisimman pienet, ts. optimaaliset. Kohdefunktio voidaan valita eri tavoin täällä, esimerkiksi neliöiden summana tai todennäköisyysfunktiona .

Ilmastotutkimus

Ilmastomallit edustavat yksinkertaistettuja numeerisia järjestelmiä todellisista hydrodynaamisista prosesseista ilmakehässä.Ruudukon solujen sisällä vuorovaikutukset on arvioitava likimäärin yhtälöillä. Yhtälöt voivat olla joko johdettavissa perustavanlaatuisista hydrodynaamisista laeista tai käytetään empiirisiä yhtälöitä, ts. Periaatteessa tilastollisia malleja, joiden parametrit on optimoitava siten, että ilmastomallit edustavat todellisia prosesseja mahdollisimman hyvin.

Peliteoria

Saavuttaako pelaajajoukko superpelissä optimaalisen populaation? Tai ainakin Pareto-optimi ? Onko tämä tasapaino vakaa?

fysiikka

Mittauskäyrien arviointi vaihtelemalla teoreettisen funktion parametriarvoja ("optimointi parametriavaruudessa", katso myös kompensointilaskenta ("sovitus")) niin, että teoreettinen funktio vastaa mittauskäyrää mahdollisimman tarkasti. Fyysiset järjestelmät pyrkivät aina energiamiiniin ; monet ongelmat ovat juuri tämän energiaminimin löytäminen.

Rajaus

Alueella on approksimaatio on numeerisesti on sukua optimointi . Vastaavasti voidaan sanoa: Lähentämisongelma on kahden funktion välisen etäisyyden ( metrisen ) minimoinnin ongelma .

Termit: tavoitefunktio, rajoitteet, sallittu joukko, paikallinen ja globaali optimointi

Oletetaan seuraavassa minimointitehtävä. Optimoitavaa, esimerkiksi etäisyyttä, kutsutaan tavoitefunktioksi . Vaihtelevat ovat kohdefunktion parametrit tai muuttujat . Kaksiulotteisen optimointitehtävän (eli kahden itsenäisen parametrin) tapauksessa kohdetoiminto voidaan kuvitella spatiaalisesti parametreilla, jotka kattavat pituus- ja syvyysakselit. Korkeus on sitten tavoitefunktion arvo. Puhtaassa intuitiossa luodaan "vuorijono", jossa on vuoria ja laaksoja (ainakin jatkuvilla toiminnoilla).

Jos optimointitehtävä on tosiasiallisesti lähentämisongelma , niin “vuorijonolle” viitataan joskus myös sopivaksi topologiaksi . Tällöin valtaosassa tapauksia neliösummaa käytetään objektiivisena funktiona , katso yksityiskohdat artikkelista Vähiten neliömetodi .

Koska tavoitefunktio edustaa "vuorijonoa", optimointiongelma on rinnastettava tämän vuorijonon syvimmän laakson (minimointi) tai korkeimman huipun (suurin) löytämiseen. Ponnistelu tehtävän ratkaisemiseksi riippuu ratkaisevasti "vuoren" muodosta. Äärimmäinen esimerkki minimointitehtävästä olisi ehdottomasti tasainen taso, josta yksittäiset neulanmuotoiset pisteet työntyvät esiin satunnaisissa pisteissä. Tässä tapauksessa mikään hakualgoritmi ei auta, voit etsiä vain satunnaisesti ( Monte Carlon menetelmä ) tai skannata järjestelmällisesti koko pinnan. Yksi yksinkertaisimmista tapauksista kaksiulotteisessa optimointitehtävässä on, kun kallion muoto on parabolan muotoinen, joka on symmetrinen korkeusakselin suhteen ja jonka kärki löytyy.

Jos optimointitehtävä koostuu seuraavan suhteellisen (paikallisen) minimin tai maksimin löytämisestä läheisyydessä vuoren tietystä pisteestä, puhutaan paikallisesta optimoinnista . Jos tehtävänä on löytää absoluuttinen minimi tai maksimiarvo koko vuorijonolle, puhutaan globaalista optimoinnista . Näillä kahdella tehtävällä on hyvin erilaiset vaikeusasteet: Paikalliseen optimointiin on olemassa lukuisia menetelmiä, jotka kaikki johtavat tavoitteeseen enemmän tai vähemmän nopeasti kaikissa kovin vaikeissa tapauksissa hyvin varmasti. Globaalilla optimoinnilla tehtävän ratkaistavuus tietyssä tai toteutettavissa olevassa laskentabudjetissa riippuu suuresti kohdefunktion topologiasta.

Usein yksi on kiinnostunut vain parametrien arvot, jotka täyttävät lisäksi rajoitteet (NB). (Jos nämä rajoitukset koskevat vain funktion määritelmäalueen reunaa, niitä kutsutaan myös rajoituksiksi. ) Ne voidaan antaa yhtälöiden tai eriarvoisuuksien muodossa tai kuvata yksiselitteisesti joukkoa (esimerkiksi vain kokonaislukuratkaisuja). Kaikkien parametriarvojen joukko, joka täyttää kaikki NB: n, kutsutaan sallituksi joukoksi . Vuorien kohdalla NL kaventaisi aluetta, jolla etsintää tehdään. Tarkasteltavaa optimointiongelmaa kutsutaan hyväksyttäväksi, jos hyväksyttävä joukko eli etsittävä alue ei ole tyhjä. Aktiivisten ja passiivisten toissijaisten olosuhteiden välillä tehdään ero : Lomakkeen NB on aktiivinen, kun optimi on sallitun alueen reunalla ja on siten yhtä suuri . Jos NB olisi passiivinen, se ei merkitsisi optimaalista rajoitusta, joten optimi on alueella eikä reunalla. Lomakkeen NB on aina aktiivinen. ${\ displaystyle g (x) \ leq 0}$${\ displaystyle g (x) = 0}$${\ displaystyle h (x) = 0}$

luokittelu

Skalaariset optimointiongelmat

Skalaarinen optimointiongelma voidaan ilmaista matemaattisesti muodossa

"Sulje / maksimoida mukaisesti toissijainen ehto "${\ displaystyle f (x)}$ ${\ displaystyle x \ X: ssä}$

edustaa; tässä reaaliarvoinen funktio ja . Usein sallittu määrä annetaan epäsuorasti toiminnolla, joka on yleensä muodoltaan standardoitu ${\ displaystyle f \ kaksoispiste V \ to \ mathbb {R}}$${\ displaystyle X \ subseteq V}$ ${\ displaystyle X}$

${\ displaystyle X = \ {x \ in V: g (x) \ leq 0 \}}$vektoriarvoisella funktiolla (vertailu tarkoittaa: mikään komponentti ei saa olla positiivinen).${\ displaystyle g \ kaksoispiste V \ to \ mathbb {R} ^ {m}}$${\ displaystyle g (x)}$

Skalaarien optimointiongelmat voidaan muodosta riippuen luokitella seuraavasti: ${\ displaystyle V, X, f, g}$

• Vaihteluongelma : on äärettömän ulotteinen, erityisesti funktiotila.${\ displaystyle V}$
• Optimaalinen ohjausongelma : Klassisen vaihtelun ongelma differentiaaliyhtälön rajoituksilla
• Lineaarinen ohjelma (LP): missä on affiini, on lineaarinen.${\ displaystyle V = \ mathbb {R} ^ {n}, g = Axe-b}$${\ displaystyle A \ sisään \ mathbb {R} ^ {m \ kertaa n}}$${\ displaystyle f = c ^ {T} x}$
• Toissijainen ohjelma (QP): kuten yllä, vain on toisen asteen funktio.${\ displaystyle f}$
• Toissijainen ohjelma, jolla on toisen asteen rajoituksia (QCQP)
• Epälineaarinen ohjelma : ovatko kaikki toiminnot (yleensä oletetaan niiden olevan jatkuvasti erotettavissa ; optimin läheisyydessä voidaan usein käyttää neliöllistä lähentämistä, mikä johtaa joihinkin käytännön menetelmiin.)${\ displaystyle f, g}$
• Kokonaislukuohjelma (myös erillinen ohjelma ): Lisäksi sallitut arvot rajoitetaan kokonaislukuun tai yleisemmin erillisiin arvoihin.${\ displaystyle x}$
• Stokastinen ohjelma : Joitakin kuvauksen parametreja ei tunneta (mutta niiden satunnaisjakauma on tiedossa).${\ displaystyle f, g}$
• Kupera ohjelma : on kupera ja kupera (kovera), jos se minimoidaan (maksimoidaan). Kuperat ohjelmat sisältyvät erityistapauksena ${\ displaystyle X}$${\ displaystyle f}$
  • Kartiomainen ohjelma : Yleistettyjä eriarvoisuuksia käytetään, muuten kaikki toiminnot ovat affiinisia. Kartiopohjaisilla ohjelmilla on puolestaan ​​kolme osa-aluetta:
    • Semidefinite-ohjelmat käyttävät positiivisten semidefinite-matriisien kartiota, joten niillä on matriisi muuttujana.
    • SOCPs ( toisen kertaluvun Cone ohjelma ) käyttää toisen asteen kartio, jota kutsutaan myös Lorentz kartio .
    • Lineaariset optimointiongelmat voidaan muotoilla myös kartiomaisina ohjelmina.
  • Tietyissä olosuhteissa neliöohjelmat ja neliöohjelmat, joilla on toissijaisia ​​rajoituksia, kuuluvat myös kuperan optimoinnin piiriin.
  • Geometriset ohjelmat eivät ole sinänsä kuperia, mutta ne voidaan muuntaa kuperaksi ongelmaksi.

Kullakin näistä optimoinnin osa-alueista on erityisesti ongelman rakenteeseen räätälöidyt ratkaisumenetelmät.

Huomautus terminologiasta: "Ohjelma" on ymmärrettävä "optimointiongelman" synonyymiksi (eikä "tietokoneohjelmaksi"). Termin "ohjelma" käyttö perustuu historiallisesti: Ensimmäiset optimointisovellukset olivat sotilaallisia ongelmia, joille voitiin löytää toimintaohjelma.

Vektorien optimointiongelmat

Optimointi ongelma vektori optimointi (kutsutaan myös Pareto optimointi ), toisaalta, on ongelma, jossa arvot useiden funktiot täytyy optimoida samanaikaisesti. Tämä voidaan sitä koskeva optimoimalla vektoriarvoisena kohdefunktion . Ratkaisuja, jotka johtavat kaikki tavoitetoiminnon komponentit samanaikaisesti optimaaliseen, eivät yleensä ole käytettävissä; pikemminkin on olemassa suurempi joukko ratkaisuja, joista esimerkiksi yksi optimaalinen piste voidaan valita skalaarisella (tavoitetoiminnon yksittäisten komponenttien painotus). ${\ displaystyle f \ kaksoispiste V \ to \ mathbb {R} ^ {n}}$

Lineaarinen ja kokonaislukuoptimointi

Tärkeä erikoistapaus on lineaarinen optimointi . Tässä kohdefunktio on lineaarinen, ja rajoitukset voidaan esittää lineaaristen yhtälöiden ja eriarvoisuuksien järjestelmällä. Jokainen paikallinen optimi on automaattisesti myös globaali optimi, koska sallittu alue on kupera. On pivot menetelmiä laskea globaali optimi tarkalleen, periaatteessa, joista tunnetuimpia ovat simplex menetelmiä (ei pidä sekoittaa alamäkeen simplex menetelmä alla). 1990-luvulta lähtien on kuitenkin ollut myös tehokkaita sisäpistemenetelmiä, jotka voivat olla kilpailukykyisiä simplex-menetelmän kanssa tietyntyyppisiin optimointiongelmiin.

Rajoitus kokonaislukumuuttujiin vaikeuttaa ongelmaa huomattavasti, mutta samalla laajentaa mahdollisia sovelluksia. Tätä ns. Integraalia lineaarista optimointia käytetään esimerkiksi tuotannon suunnittelussa , aikataulutuksessa , reittisuunnittelussa tai televiestinnän tai liikenneverkkojen suunnittelussa .

Epälineaarinen optimointi

Paikallisen epälineaarisen optimoinnin menetelmät rajoituksin

Tapauksessa epälineaarinen optimointi, jossa kohdefunktion, rajoitteet (NB) tai molemmat ovat ei- lineaarisia, on vaikeampaa kuin lineaarinen optimointi . Ratkaisu saavutetaan vähentämällä ongelma aputoiminnon optimointiin ilman NB: tä. Alla olevia epälineaarisen optimoinnin menetelmiä ilman NB: tä voidaan sitten soveltaa tähän uuteen ongelmaan. Menettely tulisi selittää kosketusongelmalla: Kaksi kaukalossa olevaa palloa yrittää ottaa alimman mahdollisen pisteen, mutta eivät saa tunkeutua toisiinsa. Kohdefunktion on siis paikkasidonnainen energia pallot ja olettaa vähintään tasapainossa. Toissijaisen ehto tässä olisi tunkeutumista pallot ja , jossa negatiivinen tunkeutuminen tarkoittaa positiivista etäisyys. Aputoiminnon rakentamiseksi on viisi tapaa: ${\ displaystyle g (x, y) \ leq 0}$${\ displaystyle x}$${\ displaystyle y}$

1. Lagrange-kertojat : NB kerrotaan todellisilla tekijöillä, Lagrange-kertojat ja lisätään tavoitefunktioon. Tekijät tuodaan ongelmaan tuntemattomina, ja ne on myös määritettävä ( Karush-Kuhn-Tucker -ehtojen mukaisesti ). Pallojen tapauksessa Lagrangen kertoimet ovat juuri kosketusvoimia, joita pallot kohdistavat toisiinsa kosketuksen aikana, jotta ne eivät tunkeudu toisiinsa.
2. Rangaistustoiminnot: NB on esitetty rangaistustoiminnoilla, jotka katoavat määritelmäalueelta ja ovat negatiivisia, jos NB: ää rikotaan. Rangaistustoiminnot kerrotaan rangaistusparametreilla ja lisätään tavoitefunktioon (kun maksimoidaan, muuten vähennetään), niin että NB: n rikkomuksesta rangaistaan, joten nimi. Aktiivisia NB: itä voidaan rikkoa tässä ja ratkaisun hyväksyttävyys on tarkistettava. Pallokuvassa rangaistustoiminto vastaa todellista tunkeutumista , joka katoaa siis positiivisella etäisyydellä, ja rangaistusparametri vastaa jousen jäykkyyttä. Jousi yrittää vetää läpäisevät kohdat takaisin pintaan. Mitä jäykempi jousi, sitä vähemmän tunkeuma on.${\ displaystyle \ min (0, g (x, y))}$
3. Estetoiminnot: Estetoimintoja käytetään kuten rangaistustoimintoja. Niillä on kuitenkin jo negatiivisia arvoja, kun ne lähestyvät toimialueen rajaa ja kasvavat rajalle äärettömyyteen. Pallokuvassa palloilla olisi enemmän tai vähemmän paksu takki, joka tulee yhä jäykemmäksi, sitä enemmän sitä puristetaan kosketettaessa. NL: n rikkominen estetään hinnalla, joka jopa reunan lähestymisestä rangaistaan.
4. Laajennettu Lagrange-menetelmä: Tämä on yhdistelmä edellisiä menetelmiä. Lagrange-kerroin määritetään iteratiivisesti NB: n rikkomisen perusteella.
5. Triviaali, mutta mainitsemisen arvoinen on, että aktiivista NB: tä voidaan käyttää tavoitetoiminnon parametrien eliminoimiseen. Parametrit asetetaan arvoiksi, jotta NB: n rikkominen on nyt mahdotonta. Pallokuvassa pallojen kosketuspisteet kytketään toisiinsa (tasaavat niiden koordinaatit) siten, että tunkeutumista (sinne) ei voi enää tapahtua.

Paikallisen epälineaarisen optimoinnin menetelmät ilman rajoituksia

Paikallisen optimoinnin tapauksessa menetelmän valinta riippuu tarkasta ongelmasta: Onko kyseessä mielivaltaisesti tarkasti määritetty kohdefunktio? (Näin ei ole usein stokastisten objektiivifunktioiden kohdalla.) Onko objektiivinen toiminto ympäristössä tiukasti yksitoikkoinen, vain yksitoikkoinen vai voisiko edes olla pieniä suhteellisia ääripäitä ”matkalla”? Mitkä ovat kaltevuuden määrittämisen kustannukset?

Esimerkkejä menetelmistä:

Johdannaisvapaat menetelmät

• Bisection-menetelmä , kultaisen leikkauksen menetelmä ja muut menetelmät yksiulotteisten toimintojen optimoimiseksi tai linjahaulle (peräkkäinen haku) moniulotteisissa toiminnoissa.
• Alamäkeen simplex-menetelmä
• Luottamusalueen menettely

Nämä menetelmät maksavat monia iteraatioita, mutta ovat (osittain) suhteellisen vankkoja kohdefunktion ongelmien, esimerkiksi pienen suhteellisen ääripään suhteen, eivätkä ne vaadi gradientin laskemista. Jälkimmäinen voi olla erittäin kallista, jos haetaan vain suhteellisen epätarkkaa tulosta.

Menettelytavat, joihin tarvitaan ensimmäinen johdannainen

• Secant-menetelmä (ensimmäisen johdannaisen nollan määrittämiseksi)
• Gradientimenetelmä ja konjugaattigradienttimenetelmä .
• Lähes Newton-menetelmä

Nämä menetelmät ovat nopeampia kuin johdannaisvapaat menetelmät, kunhan gradientti voidaan laskea nopeasti, ja ne ovat yhtä vankat kuin johdannaisvapaat menetelmät.

Menettelytavat, joihin vaaditaan toinen johdannainen

• Newton-menetelmä tai Newton-Raphson-menetelmä.

Newton-menetelmä tunnetaan yleisesti menetelmänä nollan määrittämiseksi ja vaatii ensimmäisen johdannaisen. Vastaavasti sitä voidaan soveltaa myös tavoitefunktion johtamiseen, koska optimointitehtävä on 1. johdannaisen nollien määrittäminen. Newton-menetelmä on erittäin nopea, mutta ei kovin vankka. Jos et ole varma optimointiongelmasi "hyvänlaatuisuudesta", sinun on myös käytettävä globalisaatiostrategioita, kuten askelkokohaku tai luottamusalueen menettelyt .

Gauss-Newton-menetelmä on käytettävissä käytännössä usein esiintyviin ongelmiin, joissa minimoitavalla tavoitefunktiolla on vektoriarvotun funktion (pienimmän neliösumman, "pienimmän neliön" menetelmä) vakion neliön erityinen muoto. , jota periaatteessa voidaan käyttää, käyttää sitä tosiasiaa, että tämän muotoisissa toiminnoissa tietyissä lisäoletuksissa kalliita 2. johdannaista ( Hessian-matriisi ) voidaan arvioida hyvin ilman sen nimenomaista laskentaa Jacobi-matriisin funktiona . Tällä tavoin lähellä Newtonin menetelmää saavutetaan superlineaarinen konvergenssinopeus lähellä kohdetta . Koska tämä menetelmä on perinyt Newton-menetelmän vakausongelmat, tarvitaan myös ns. Globalisaatio- ja vakauttamisstrategioita, jotta voidaan taata lähentyminen ainakin seuraavaan paikalliseen minimiin. Suosittu muunnos on tässä Levenberg-Marquardt-algoritmi .

Menetelmät globaalille epälineaariselle optimoinnille

Toisin kuin paikallinen optimointi, globaali optimointi on matematiikassa melkein ratkaisematon ongelma: Ei ole käytännössä mitään menetelmiä, jotka useimmissa tapauksissa johtavat pisteeseen, joka varmasti tai jopa hyvin todennäköisesti edustaa absoluuttista ääripäätä.

Kaikilla globaalin optimoinnin menetelmillä on yhteistä, että ne etsivät toistuvasti paikallisia minimit / maksimit tietyn järjestelmän mukaisesti.

Tässä käytetään useimmiten evoluutioalgoritmeja . Nämä antavat hyvän tuloksen varsinkin kun suhteellisten minimien ja maksimien järjestely osoittaa tietyn säännöllisyyden, jonka tuntemus voidaan periä. Erittäin hyvä menetelmä voi olla myös se, että valitaan satunnaisesti lähtökohdat paikallisten minimien / maksimien etsimiselle, jotta sitten voidaan tutkia laillisuuksien hakutuloksia tilastollisin menetelmin.

Käytännössä todellinen hakukriteeri ei kuitenkaan usein heijastu riittävästi. Joten on usein paljon tärkeämpää olla etsimättä globaalia optimaalia, vaan parametrialue, jolla on mahdollisimman monta suhteellista minimiä. Klusterianalyysimenetelmät tai hermoverkot sopivat tähän .

Muita epälineaarisen globaalin optimoinnin menetelmiä:

• Optimointiprosessit ovat analogisia luonnon kanssa
  • Tulva-algoritmi ( suuren vedenpaisumuksen algoritmi )
  • Simuloitu hehkutus ( simuloitu hehkutus )
  • Metropolis-algoritmi
  • Hyväksymiskynnys ( hyväksymiskynnys )
  • Muurahaisalgoritmi ( muurahaiskolonian optimointi )
  • Hiukkasten parven optimointi
• Muut menettelyt
  • Mäkikiipeily ( mäkikiipeily )
  • Stokastinen tunnelointi ( stokastinen tunnelointi )
  • RANSAC-algoritmi mittaustietojen parempaan käsittelyyn poikkeamien kanssa
  • Primal-Dual-Active-sarja-algoritmi ratkaisua toisen asteen Optimointitehtävän yli kupera osajoukko Hilbertin avaruus ylittää asetetun${\ displaystyle S}$ ${\ displaystyle V}$${\ displaystyle \ Omega}$

Suorituskykyä algoritmit on usein analysoidaan perusteella testi ongelmia monimutkainen rakenne minimien tai maksimien, joiden tarkka ratkaisu on tunnettu. Esimerkki tällaisesta testitoiminnosta on rastrigiinifunktio .

Teoreettiset lausunnot

(Erotettavissa olevan) funktion optimoinnissa ilman rajoituksia tiedetään, että minimit / maksimit voivat olla vain pisteissä . Tätä ehtoa käytetään monien ratkaisumenetelmien rakentamisessa. Rajoitetuilla optimoinnilla on analogisia teoreettisia lausuntoja: kaksinaisuus ja Lagrange-kertojat . ${\ displaystyle f (x)}$${\ displaystyle \ nabla f (x) = 0}$

Kupera ongelmia

Kuparien ongelmien tapauksessa etsittävä alue ja kohdefunktio ovat kuperat. Kuparin alueen tapauksessa kaikki sen minkä tahansa kahden pisteen yhdistävän viivan pisteet ovat myös kokonaan alueella. Matemaattisesti:

${\ displaystyle \ lambda \ in [0,1] \ Rightarrow x + \ lambda (yx) \ in X \ quad \ forall x, y \ in X}$

Esimerkkejä kuperista alueista ovat ympyrät, ellipsit, kolmiot ja neliöt.

Kohdefunktio on kupera, jos kaikki alueen kaksi pistettä yhdistävän suoran pisteiden tavoitefunktion arvot ovat tämän suoran alapuolella. Matemaattisesti:

${\ displaystyle \ lambda \ in [0,1] \ Rightarrow f (x + \ lambda (yx)) \ leq f (x) + \ lambda (f (y) -f (x)) \ quad \ forall x, y \ X: ssä}$.

Tämän artikkelin alussa esitetyllä parabolisen optimoinnin ongelmalla on kupera tavoitefunktio.

Kuparien ongelmien tapauksessa jokainen paikallinen minimi on myös globaali minimi. Jos pisteet ovat optimaaliset, niin kaikki näiden pisteiden väliset pisteet ovat optimaalisia. Matemaattisesti: ${\ displaystyle x_ {i} \ ,, \; i = 1, \ dotsc, n}$

${\ displaystyle \ alpha _ {1}, \ alpha _ {2}, \ dotsc, \ alpha _ {n} \ in [0,1] \; \ kiila \; \ summa _ {i = 1} ^ {n } \ alpha _ {i} = 1 \ quad \ Rightarrow \ quad f \ left (\ sum _ {i = 1} ^ {n} \ alpha _ {i} x_ {i} \ right) = f _ {\ text {opt}}}$.

kaksinaisuus

Yksi optimointiongelmiin liittyvä (Lagrange) kaksoisongelma on ${\ displaystyle \ min \; f (x): \; g (x) = 0}$

${\ displaystyle \ max _ {\ lambda} \ min _ {x} {\ mathcal {L}} (x, \ lambda)}$

missä on siihen liittyvä Lagrange-funktio. Kuuma täällä Lagrangen kertoimet , tai kaksi muuttujaa tai varjo hintoihin . Toissijaisten ehtojen rikkominen on selvästi sallittua, mutta siitä määrätään objektiivisessa toiminnassa lisäkustannuksia rikkottua yksikköä kohti. Ratkaisu , jonka rajoituksia ei kannata rikkoa, ratkaisee kaksoisongelman. Kupareissa (erityisesti lineaarisissa) tehtävissä kaksoisongelman arvo on yhtä suuri kuin alkuperäisen ongelman arvo. Lineaarisille ja kuperille neliöllisille ongelmille sisäinen minimointi voidaan ratkaista suljetussa muodossa ja kaksoisongelma on taas lineaarinen tai kupera neliöllinen ongelma. ${\ displaystyle {\ mathcal {L}} (x, \ lambda) = f (x) + \ lambda ^ {T} g (x)}$${\ displaystyle \ lambda}$${\ displaystyle \ lambda}$${\ displaystyle \ lambda}$

Lagrange-kertojat

Lagrangen kertojalauseessa todetaan, että ratkaisuja rajoitettuun optimointiongelmaan voidaan löytää vain paikoista, joissa on ehtoa täyttäviä Lagrange-kertojia${\ displaystyle \ min _ {x} \, f (x): \, g (x) = 0}$${\ displaystyle x}$ ${\ displaystyle \ lambda _ {i}}$

${\ displaystyle \ nabla _ {x} {\ mathcal {L}} (x, \ lambda) = \ nabla f (x) + \ summa _ {i} \ lambda _ {i} \ nabla g_ {i} (x ) = 0}$

täyttää. Tämä ehto on suora yleistys yllä olevalle johdannan ehdolle. Tällä tavoin Lagrangen kertojalause antaa välttämättömän ehdon minimille tai maksimille. Riittävä ehto voidaan saada ottamalla huomioon toisen johdannaiset.

Lagrangen kertojalause soveltuu vain, jos rajoitukset annetaan yhtälöillä. Eriarvoisuuden yleistämisen antaa Karush-Kuhn-Tucker-lause . ${\ displaystyle \ min _ {x} \ {f (x): g (x) \ leq 0 \}}$

Rangaistustoiminnot

Rangaistusparametrien rajalle, joka lähestyy ääretöntä, rangaistustoiminnoilla löydetty ratkaisu muuttuu Lagrange-kertojien kanssa löydetyksi ratkaisuksi.

Laajennettu Lagrange-menetelmä

Äärettömän monien iteraatioiden raja-alueella laajennetulla Lagrange-menetelmällä löydetty ratkaisu pyrkii myös Lagrange-kertojilla löydettyyn ratkaisuun.

Yksittäiset todisteet

1. ↑ Lineaarisen ohjelmoinnin isä ( Memento 11. marraskuuta 2009 Internet-arkistossa ) julkaisussa: informs.org

kirjallisuus

• Walter Alt: Epälineaarinen optimointi - Johdanto teoriaan, menettelyihin ja sovelluksiin . Vieweg, 2002, ISBN 3-528-03193-X .
• Yonathan Bard: Epälineaarinen parametriarviointi . Academic Press, New York 1974, ISBN 0-12-078250-2 .
• Hans Benker: Matemaattinen optimointi tietokonealgebrajärjestelmillä. Springer-Verlag, Berliini / Heidelberg / New York 2003.
• S. Boyd, L. Vandenberghe: Kupera optimointi . Cambridge University Press, 2004. (online)
• W. Domschke, A. Drexl: Johdatus operaatiotutkimukseen. 7. painos. Springer, Berliini 2007, ISBN 978-3-540-70948-0 .
• R. Fletcher: Optimoinnin käytännön menetelmät . Wiley, 1987, ISBN 0-471-91547-5 .
• U. Hoffmann, H. Hofmann: Johdatus optimointiin: esimerkkejä kemian tekniikan olennoista . Verlag Chemie, Weinheim 1971, ISBN 3-527-25340-8 .
• R. Horst, pääministeri Pardalos (toim.): Handbook of Global Optimization . Kluwer, Dordrecht 1995, ISBN 0-7923-3120-6 .
• F. Jarre, J. Stoer: Optimointi . Springer, 2004, ISBN 3-540-43575-1 . rajoitettu esikatselu Google-teoshaulla
• J. Nocedal, SJ Wright: Numeerinen optimointi . Springer, Berliini 1999, ISBN 0-387-98793-2 .
• C. Geiger, C. Kanzow: Rajoitettujen optimointitehtävien teoria ja numerot . Springer, 2002, ISBN 3-540-42790-2 . rajoitettu esikatselu Google-teoshaulla
• C. Grossmann, J. Terno: Optimoinnin numerot . Teubner Study Books, 1997, ISBN 3-519-12090-9 . rajoitettu esikatselu Google-teoshaulla

nettilinkit

• Optimointikirjallisuus Saksan kansalliskirjaston luettelossa
• Yleinen linkkisivun globaali optimointi (englanti)
• Johdanto numeeriseen optimointiin
• NEOS-oppaan optimointi (englanti)
• Optimointiohjelmiston päätöksentekopuu (englanti)
• Globaalit optimointialgoritmit - teoria ja sovellus (englanti; PDF-tiedosto; 13,14 Mt)