epäkonveksi

Epäkonveksi (non-convexity) on käsite matematiikassa ja sen sovelluksissa, joka kuvaa olosuhdetta, jossa jokin joukko, funktio tai ongelma ei ole konveksi. Joukko S on konveksi, jos jokainen lineaarikombinaatio tx + (1−t) y kuuluu S kaikille x,y ∈ S ja kaikille t ∈ [0,1]. Epäkonveksi joukko on siis sellainen, että löytyy x,y ∈ S ja t ∈ [0,1], joiden tx + (1−t) y ei ole S:ssä.

Geometriassa epäkonveksia alueita ovat esimerkiksi rengas (annulus) tai U-kirjaimen muotoinen alue sekä kahdesta erillisestä osasta koostuvat joukot. Myös ympyrän kehän (käytännössä piirin pistejoukko) ei ole konveksi. Konveksin ja epäkonveksin eron havainnollistaa se, että konveksin alueen sisällä olevat suorat campat kulkevat läpi kokonaisuudessaan, kun taas epäkonveksissa alueissa voi olla “reikiä” tai erillisiä osia, joiden välillä suora viiva ei mahtuisi alueen sisälle.

Funktion tasolla f on konveksi, jos sen epigrafi on konveksi; vastakohtana epäkonveksi f ei täytä tätä ominaisuutta. Esimerkkejä epäkonveksista funktioista ovat monet polynomit, joiden toinen derivaatta muuttuu signaaliin, sekä monikohdistuneet funktiot, joissa on useita local minimumja. Epäkonveksiyden vuoksi joidenkin optimointiongelmien globaali ratkaisu voi olla vaikea löytää ja ratkaisuja voi olla useita.

Sovelluksissa epäkonveksi aiheuttaa haasteita esimerkiksi optimointialgoritmeissa ja taloustieteessä, jossa epäkonveksit mieltymykset tai tuotantokustannukset voivat johtaa useisiin tasapainokohtiin tai parhaiten löydettävien ratkaisujen epävarmuuteen. Epäkonveksin käsittelyyn käytetään usein konveksin hullun (convex hull) ja relaxaatiometodeja parhaan mahdollisen ratkaisun etsimiseksi.