Epäkonveksisuus

Epäkonveksisuus tarkoittaa sitä, että jokin joukko tai jokin funktio ei ole konveksi. Joukko S ⊂ R^n on konveksi, jos jokaiselle x,y ∈ S ja jokaiselle λ ∈ [0,1] lineaarinen yhdistelmä z = λx + (1−λ)y kuuluu S. Epäkonveksisuus tarkoittaa, että tämä ehto ei päde: löytyy x,y ∈ S ja λ ∈ (0,1) siten, että z ∉ S.

Geometriassa epäkonveksia ovat esimerkiksi renkaan tai muun koloa sisältävän alueen kaltaiset muotoryhmät. Yleisiä esimerkkejä ovat annulus, useista osista koostuvat joukot tai alueet, joissa kaksi pistettä on erillään mutta niiden yhdistävä suora ei kokonaan kuulu alueeseen. Epäkonveksisuus voi ilmetä sekä yksittäisten alueiden että niiden yhdistelmien muodossa.

Funktion konveksisuus ja epäkonveksisuus liittyvät optimointiin. Funktio f on konveksi, jos kaikille x,y ja λ ∈ [0,1] pätee f(λx+(1−λ)y) ≤ λ f(x) + (1−λ) f(y). Jos tätä ehtoa ei täyty, funktio on epäkonveksi. Samoin, jos tavoite- tai rajoitejoukko on epäkonveksi, optimointitehtävä voi sisältää useita lokaaliminimejä eikä globaalia ratkaisua ole helposti saatavilla.

Merkitys ja sovellukset. Konveksilla optimoinnilla on usein yksiselitteisiä, hyvin käyttäytyviä ratkaisuja, kun taas epäkonveksisuus monimutkaistaa ongelmia ja voi johtaa moniin paikallisiin minimoihin. Epäkonveksisuutta esiintyy mm. koneoppimisessa, suunnittelussa, resurssien jakamisessa sekä monissa teoreettisissa ja käytännön optimointiongelmissa, joihin etsitään globalisointia, konveksivietälyä tai heuristisia ratkaisuja.