Matlabissa on moniulotteisen epälineaarisen optimointiongelman ratkaisemiseen valmis funktio nimeltä fmincon. Tämän käyttämiseksi ongelma formuloidaan ensin standardimuotoon
min f(x)
missä f(x) on minimoitava kohdefunktio ja viisi seuraavaa riviä ovat muuttujavektoriin x kohdistuvia rajoitteita: lineaariset epäyhtälörajoitteet (rivi 1), lineaariset yhtälörajoitteet (rivi 2), epälineaariset epäyhtälörajoitteet (rivi 3) ja epälineaariset yhtälörajoitteet (rivi 4) muodostetaan omiksi matriisiyhtälöryhmikseen. Rivin 5 muotoon taas syötetään muuttujan x alarajat lb sekä ylärajat ub omina vektoreinaan.[15]
Rivien 1 ja 2 mukaiset lineaariset rajoitteet Matlab osaa käsitellä suoraan kerroinmatriisien (A ja Aeq) ja vakiovektoreiden (B ja Beq) avulla, mutta rivien 3 ja 4 mukaisten epälineaaristen
rajoitteiden syöttämiseksi on tehtävä erillinen funktiotiedosto nonlcon, mihin funktiot Cx ja Ceqx
suoraan, mutta helpointa on tehdä siitäkin erillinen funktiotiedosto, sillä tämä mahdollistaa haluttaessa myös kohdefunktion gradientin ja Hessin matriisin syöttämisen (ks. luku 4.3). Kun ongelma on saatu esitettyä tässä muodossa, voidaan seuraavaksi yrittää ratkaista optimaalinen ratkaisuvektori X kutsumalla fmincon-funktiota komennolla
X=fmincon(fun,x0,A,B,Aeq,Beq,lb,ub,nonlcon,options) ,
missä x0 on ratkaisun alkuarvausvektori. Options-kenttään voidaan spesifioida tiettyjä lisäehtoja tai –ohjeita käyttäjän tarpeiden mukaan; perustapauksissa funktion vakioasetukset ovat kuitenkin useimmiten täysin riittävät ratkaisun saavuttamiseksi, eikä niihin tarvitse ainakaan
ensimmäiseksi koskea. Tällaisessa tapauksessa options-kenttä jätetään lopusta pois. Mikäli jotakin edellä mainituista rajoitteista ei käytetä, merkitään kyseis(t)en rajoitte(id)en kohdalle kutsukomentoon tyhjä matriisi []. Jos ongelmassa esimerkiksi ei ole lineaarisia
epäyhtälörajoitteita, X:n arvoille ei ole ylärajaa ja asetuksiin ei kosketa, kutsukomento on tällöin X=fmincon(fun,x0,[],[],Aeq,Beq,lb,[],nonlcon) .
Kun optimiratkaisu X on löytynyt, informoi funktio käyttäjää kertomalla ratkaisun lisäksi myös aktiiviset epäyhtälörajoitteet sekä aktiiviset ala- ja ylärajarajoitteet. Hyödyllisenä lisätietona funktio kertoo myös, mikä aiheutti optimoinnin päättymisen, ts. mikä funktion katkaisuehdoista täyttyi. Tämän perusteella voidaan päätellä, onko saatu vastaus miten suurella
todennäköisyydellä todellakin kohdefunktion globaali minimi vai onko laskennassa tullut esimerkiksi iterointikertojen maksimiraja vastaan.
4.3 Ratkaisualgoritmi
Fmincon minimoi annetun kohdefunktion käyttäjän asettamilla rajoitteilla huomattavan nopeasti, eikä käyttäjän välttämättä tarvitse tietää itse ratkaisuprosessista mitään. On kuitenkin suureksi hyödyksi ymmärtää funktion käyttämän algoritmin toimintaa, sillä tietyistä syistä optimointi ei välttämättä aina konvergoi kohti optimaalista ratkaisua. Lisäksi algoritmin toimintaa voidaan useissa tapauksissa nopeuttaa ja tarkentaa sopivilla lisäasetuksilla.
Perusasetuksena fmincon käyttää ratkaisussa trust region reflective-algoritmia, mikä on ns.
”large-scale”-algoritmi.[16] Tämä ei tarkoita sitä, että ratkaisua haettaisiin jotenkin erityisen laajalta alueelta, vaan sitä, että ratkaisussa ei käytetä tai varastoida dataa täysiin matriiseihin; kun ongelma on purettu lineaarisiksi yhtälöryhmiksi, käsitellään ratkaisuprosessissa vain tiettyä osaa tai osia yhtälöryhmämatriiseista kerrallaan. Tämä nopeuttaa laskentaa huomattavasti.
Valitettavasti kyseistä algoritmia ei voida käyttää, mikäli ongelma sisältää sekä
muuttujarajoituksia lb ja ub että lineaarisia rajoitteita. Lisäksi epälineaarisia rajoitteita algoritmi ei osaa käsitellä ollenkaan. Näistä syistä ratkaisualgoritmia on tämän ongelman tapauksessa vaihdettava ns. ”medium-scale”-algoritmiin nimeltä Active set, mikä osaa käsitellä kaikenlaisia rajoitteita. (Mikäli käyttäjä ei ole tätä vaihdosta tehnyt, osaa Matlab suorittaa algoritmin vaihdon itse.)
Active set-algoritmin toiminta perustuu monien muiden optimointi- ja datasovitusalgoritmien tapaan neliösummien minimoimiseen. Tässä kyseinen algoritmi käyttää apuna minimoitavia Karush-Kuhn-Tuckerin (lyh. KKT) yhtälöitä. Selkeyden vuoksi aloitetaan algoritmin johtaminen helposta perustilanteesta optimoinnin aihepiirin ulkopuolelta:
Tutkitaan monen muuttujan funktion f(x) ääriarvoja tilanteessa, missä ratkaisun pitää täyttää side-ehto (eli toisin sanoen rajoite) g(x) = 0. Lagrangen kertoimien menetelmällä funktion minimi tai maksimi tällä side-ehdolla saadaan gradienttien avulla yhtälöryhmästä
{∇ ( ) ∇ ( )
( ) (50)
missä Lagrangen kerroin λ on nollasta eriävä.[17] Vastaavalla tavalla voidaan määritellä minimoitava kohdefunktio f ja sitä koskevat rajoitteet G muotoon
min f(x)
s.t. { ( )
( ) (51)
missä yhtälöt Gi(x) ovat lineaarisia tai epälineaarisia yhtälörajoitteita, kun i = 1,…,m ja
lineaarisia tai epälineaarisia epäyhtälörajoitteita, kun i = m+1,…,n. Tällöin minimikohta voidaan ratkaista käyttämällä KKT-yhtälöitä:
{
Näistä yhtälöistä nähdään, että ratkaisupisteessä X kohdefunktion ja aktiivisten rajoitefunktioiden gradientit kumoavat toisensa (yhtälö 1). Aktivoitumattomien rajoitefunktioiden
Lagrange-kertoimet saavat tällöin arvon nolla (yhtälöt 2 ja 3).[16] [18] Periaatteeltaan algoritmi vastaa siis täysin normaalia monen muuttujan funktion ääriarvolaskentaa. Rajoitteiden määrä ja
lausekkeiden vaikeus vain aiheuttavat niin suuria hankaluuksia käsin laskentaan, että koneellinen ratkaisu on ainoa järkevä vaihtoehto.
Perusalgoritmi on toimiva ja löytää ratkaisun melko usein, mutta koska algoritmi on ”middle-scale”-tyyppiä ja kuljettaa mukanaan koko ajan kaikkia matriiseja, jättää sen nopeus toivomisen varaa. Tätä voidaan kuitenkin parantaa syöttämällä funktioiden derivaattoja, sillä
normaalitilanteessa fmincon laskee sekä kohdefunktiolle että epälineaarisille rajoitefunktioille jokaisella iteraatioaskeleella likimääräisen gradientin ja Hessin matriisin käyttämällä
iteraatiopisteen ja sen jonkin lähipisteen äärellisiä erotuksia (ns. ”finite difference method”).
Mikäli näille funktioille lasketaan käyttäjän toimesta gradientit ja Hessin matriisit valmiiksi, nopeutuu laskenta huomattavasti näiden derivaatta-approksimaatioiden jäädessä pois. Lisäksi valmiiksi syötetyt lausekkeet antavat tarkkoja arvoja gradientille ja Hessin matriisille, minkä ansiosta laskentatarkkuuskin paranee. Joissain tilanteissa laskenta voi saavuttaa pisteen, jossa ratkaisu on sallittu, mutta äärellisten erotusten antama gradienttiapproksimaatio veisikin
seuraavan ratkaisun ei-sallitulle alueelle. Jos tällöin kohdefunktio on sattumalta sellaista muotoa, että se saa sallitun alueen ulkopuolella kompleksisia arvoja, ratkaisija kaatuu. Jos käyttäjä on
antanut valmiiksi lasketut gradientit sekä kohdefunktiolle että epälineaarisille rajoitefunktioille, myös tältä ongelmalta vältytään.[18]
Funktiolla voidaan ottaa huomioon myös mahdolliset inhimilliset virheet gradienttien
syöttämisessä, mikäli asetetaan päälle ”DerivativeCheck”-lisäasetus. Tämä toiminto tarkastaa, että käyttäjän antama gradientti ja äärellisten erotusten perusteella laskettu gradientti antavat samansuuntaisia arvoja ja antaa tarvittaessa käyttäjälle eroavaisuuksista varoituksen.
Periaatteessa huippuunsa optimoidussa koodissa tätä toimintoa kannattaisi luonnollisesti käyttää vain aluksi ja poistaa se käytöstä, kun gradientit on todettu oikein syötetyiksi, mutta ainakaan tämän ongelman testeissä toiminnolla ei ollut tieteellisesti todettavissa olevaa vaikutusta ratkaisuaikoihin. Sitä vastoin pelkkien kohdefunktion gradienttien syöttäminen nopeutti
laskentaa 60-70 prosenttia, joten sillä on algoritmin toimintaa huomattavasti tehostava vaikutus.
Tämän ongelman laskut on suoritettu Matlabin versiolla R2006b, missä algoritmivaihtoehdot on rajattu edellä mainittuihin kahteen. Viimeisimmissä versioissa (R2010a, R2011a) fmincon-funktioon on tarjolla kaksi muutakin algoritmia, joiden pitäisi olla huomattavasti edellä kuvattua Active set-algoritmia tehokkaampia. Näitä ei päästy kokeilemaan, mutta toisaalta jo nyt käytetty algoritmikin tuotti luotettavan oloisia tuloksia hyvin kohtuullisilla laskenta-ajoilla. Välttämätöntä tarvetta uudemmille versioille ei siis tässä käytössä ole.