Monet rajoittamattomat optimointialgoritmit voidaan sovittaa rajoitettuun tapaukseen, usein rangaistusmenetelmän avulla. Rajoittamattoman menetelmän ottamia hakuvaiheita ei kuitenkaan välttämättä voida hyväksyä rajoitetun ongelman kannalta, mikä johtaa konvergenssin puuttumiseen. Tätä kutsutaan Maratos-ilmiöksi.
YhtäläisyysrajoituksetEdit
SubstituutiomenetelmäEdit
Hyvin yksinkertaisissa ongelmissa, esimerkiksi kahden muuttujan funktiossa, johon kohdistuu vain yksi yhtäläisyysrajoitus, on käytännöllisintä soveltaa substituutiomenetelmää. Ideana on korvata rajoitus kohdefunktioon, jotta saadaan aikaan yhdistetty funktio, joka sisältää rajoituksen vaikutuksen. Oletetaan esimerkiksi, että tavoitteena on maksimoida f ( x , y ) = x ⋅ y {\displaystyle f(x,y)=x\cdot y}
ehdolla x + y = 10 {\displaystyle x+y=10}
. Rajoituksesta seuraa, että y = 10 – x {\displaystyle y=10-x}
, joka voidaan korvata tavoitefunktioon, jolloin saadaan p ( x ) = x ( 10 – x ) = 10 x – x 2 {\displaystyle p(x)=x(10-x)=10x-x^{2}}}
. Ensimmäisen kertaluvun välttämätön ehto antaa ∂ p ∂ x = 10 – 2 x = 0 {\displaystyle {\frac {\partial p}{\partial x}}=10-2x=0}
, joka voidaan ratkaista tapauksessa x = 5 {\displaystyle x=5}
ja näin ollen y = 10 – 5 = 5 {\displaystyle y=10-5=5}
.
Lagrangen kerroinEdit
Jos rajoitetussa ongelmassa on vain tasa-arvorajoituksia, voidaan Lagrangen kerroinmenetelmällä muuntaa se rajoittamattomaksi ongelmaksi, jonka muuttujien määrä on alkuperäinen muuttujien määrä lisättynä alkuperäisellä tasa-arvorajoitusten määrällä. Vaihtoehtoisesti, jos kaikki rajoitteet ovat tasa-arvorajoitteita ja kaikki ovat lineaarisia, ne voidaan ratkaista joidenkin muuttujien osalta muiden muuttujien suhteen, ja edelliset voidaan korvata pois kohdefunktiosta, jolloin jäljelle jää rajoittamaton ongelma pienemmällä muuttujien lukumäärällä.
EpäyhtäläisyysrajoituksetEdit
Epäyhtäläisyysrajoitusten avulla ongelmaa voidaan luonnehtia geometristen optimaalisuusehtojen, Fritz-John-ehtojen ja Karush-Kuhn-Tucker-ehtojen avulla, joiden vallitessa yksinkertaiset ongelmat voivat olla ratkaistavissa.
Lineaarinen ohjelmointiEdit
Jos tavoitefunktio ja kaikki kovat rajoitteet ovat lineaarisia ja jotkut kovat rajoitteet ovat epäyhtälöitä, ongelma on lineaarinen ohjelmointiongelma. Se voidaan ratkaista simpleksimenetelmällä, joka yleensä toimii polynomiajassa ongelman koon suhteen, mutta ei taatusti, tai sisäpistemenetelmillä, jotka taatusti toimivat polynomiajassa.
Epälineaarinen ohjelmointiEdit
Jos tavoitefunktio tai osa rajoitteista on epälineaarisia ja osa rajoitteista on epätasa-arvoja, ongelma on epälineaarisen ohjelmoinnin ongelma.
Kvadraattinen ohjelmointiEdit
Jos kaikki kovat rajoitukset ovat lineaarisia ja osa epätasa-arvoja, mutta tavoitefunktio on kvadraattinen, ongelma on kvadraattinen ohjelmointiongelma. Se on yksi epälineaarisen ohjelmoinnin tyyppi. Se voidaan silti ratkaista polynomisessa ajassa ellipsoidimenetelmällä, jos kohdefunktio on kovera; muuten ongelma voi olla NP-vaikea.
KKT-ehdotMuutos
Sallimalla epätasa-arvorajoitukset, KKT-lähestymistapa epälineaariseen ohjelmointiin yleistää Lagrangen kertojien menetelmää. Sitä voidaan soveltaa differentioituvuuden ja koveruuden vallitessa.
Haarautuminen ja rajaaminenMuokkaa
Kontrastioptimointi voidaan ratkaista haarautumisalgoritmeilla. Nämä ovat backtracking-algoritmeja, jotka tallentavat suorituksen aikana löydetyn parhaan ratkaisun kustannukset ja käyttävät niitä välttääkseen osan hausta. Tarkemmin sanottuna, aina kun algoritmi kohtaa osaratkaisun, jota ei voida laajentaa niin, että muodostuisi ratkaisu, jonka kustannukset ovat paremmat kuin tallennetun parhaan kustannuksen, algoritmi peruuttaa sen sijaan, että se yrittäisi laajentaa tätä ratkaisua.
Edellyttäen, että kustannukset halutaan minimoida, näiden algoritmien tehokkuus riippuu siitä, miten osaratkaisun laajentamisesta saatavat kustannukset arvioidaan. Jos algoritmi voi nimittäin palata osittaisesta ratkaisusta, osa etsinnästä jätetään väliin. Mitä alhaisempi arvioitu kustannus on, sitä parempi algoritmi on, sillä alhaisempi arvioitu kustannus on todennäköisemmin alhaisempi kuin tähän mennessä löydetyn ratkaisun paras kustannus.
Toisaalta tämä arvioitu kustannus ei voi olla alhaisempi kuin todellinen kustannus, joka voidaan saada ratkaisua laajentamalla, sillä muutoin algoritmi voisi perääntyä, vaikka tähän mennessä löydettyä parasta ratkaisua parempi ratkaisu on olemassa. Tämän seurauksena algoritmi vaatii ylärajan kustannukselle, joka voidaan saada osaratkaisua laajentamalla, ja tämän ylärajan tulisi olla mahdollisimman pieni.
Tämän lähestymistavan muunnelma, jota kutsutaan Hansenin menetelmäksi, käyttää intervallimenetelmiä. Se toteuttaa luonnostaan suorakulmaiset rajoitteet.
Ensimmäisen valinnan rajausfunktiotEdit
Yksi tapa arvioida tätä osaratkaisun ylärajaa on tarkastella jokaista pehmeää rajoitetta erikseen. Kullekin pehmeälle rajoitteelle oletetaan suurin mahdollinen arvo mille tahansa määritykselle määrittelemättömille muuttujille. Näiden arvojen summa on yläraja, koska pehmeät rajoitukset eivät voi olettaa suurempaa arvoa. Se on tarkka, koska pehmeiden rajoitusten maksimiarvot voivat johtua eri arvioinneista: pehmeä rajoitus voi olla maksimissaan tapauksessa x = a {\displaystyle x=a}
kun taas toinen rajoitus on maksimaalinen tapauksessa x = b {\displaystyle x=b}
.
Russian doll searchEdit
Tämä menetelmä ajaa branch-and-bound-algoritmin n {\displaystyle n}
ongelmia, joissa n {\displaystyle n}
on muuttujien lukumäärä. Jokainen tällainen ongelma on osaongelma, joka saadaan jättämällä pois muuttujien x 1 , … , x i {\displaystyle x_{1},\ldots ,x_{i}} sekvenssi.
alkuperäisestä ongelmasta yhdessä niitä sisältävien rajoitusten kanssa. Muuttujia x i + 1 , … , x n koskevan ongelman jälkeen {\displaystyle x_{i+1},\ldots ,x_{n}}
on ratkaistu, sen optimaalisia kustannuksia voidaan käyttää ylärajana ratkaistessa muita ongelmia,
Erityisesti sellaisen ratkaisun kustannusarvio, jolla on x i + 1 , … , x n {\displaystyle x_{i+1}},\ldots ,x_{n}}}
määrittelemättöminä muuttujina, lisätään kustannuksiin, jotka johtuvat arvioiduista muuttujista. Käytännössä tämä vastaa arvioitujen muuttujien huomiotta jättämistä ja ongelman ratkaisemista kohdistamattomilla muuttujilla, paitsi että jälkimmäinen ongelma on jo ratkaistu. Tarkemmin sanottuna sekä osoitettuja että osoittamattomia muuttujia sisältävien pehmeiden rajoitusten kustannukset estimoidaan kuten edellä (tai käyttämällä mitä tahansa muuta menetelmää); ainoastaan osoittamattomia muuttujia sisältävien pehmeiden rajoitusten kustannukset estimoidaan sen sijaan käyttämällä vastaavan ongelman optimaalista ratkaisua, joka on tässä vaiheessa jo tiedossa.
Venäläisen nuken hakumenetelmän ja dynaamisen ohjelmoinnin välillä on samankaltaisuutta. Dynaamisen ohjelmoinnin tavoin Russian Doll Search -menetelmässä ratkaistaan osaongelmia koko ongelman ratkaisemiseksi. Mutta siinä missä dynaaminen ohjelmointiyhdistää osaongelmista saadut tulokset suoraan koko ongelman tuloksen saamiseksi, Russian Doll Search käyttää niitä vain rajoina haun aikana.
Kauhan eliminointi Muokkaa
Kauhan eliminointialgoritmi voidaan sovittaa rajoitusten optimointiin. Tietyn muuttujan voi todellakin poistaa ongelmasta korvaamalla kaikki sitä sisältävät pehmeät rajoitteet uudella pehmeällä rajoitteella. Tämän uuden rajoituksen kustannukset lasketaan olettaen maksimiarvo jokaiselle poistetun muuttujan arvolle. Muodollisesti, jos x {\displaystyle x}
on poistettava muuttuja, C 1 , … , C n {\displaystyle C_{1},\ldots ,C_{n}}}
ovat sen sisältäviä pehmeitä rajoituksia, ja y 1 , … , y m {\displaystyle y_{1},\ldots ,y_{m}}}
ovat niiden muuttujia paitsi x {\displaystyle x}
, uusi pehmeä rajoitus määritellään seuraavasti: C ( y 1 = a 1 , … , y n = a n ) = max a ∑ i C i ( x = a , y 1 = a 1 , … , y n = a n ) . {\displaystyle C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).}.
Bucket elimination toimii muuttujien (mielivaltaisen) järjestyksen kanssa. Jokaiseen muuttujaan liittyy ämpäri rajoituksia; muuttujan ämpäri sisältää kaikki rajoitukset, joilla muuttuja on järjestyksessä korkeimmalla. Kauhan eliminointi etenee viimeisestä muuttujasta ensimmäiseen. Kunkin muuttujan kohdalla kaikki kyseisen muuttujan rajoitukset korvataan edellä esitetyllä tavalla muuttujan poistamiseksi. Tuloksena oleva rajoitus sijoitetaan sitten asianmukaiseen ämpäriin.