epäkonveksiin

Epäkonveksiin on käsite geometriassa ja optimoinnissa, joka viittaa alueeseen tai joukkoon, joka ei ole konveksi. Konveksinen joukko on sellainen, että jokainen kahden pisteen välinen suoran segmentti pysyy joukossa. Epäkonveksissa joukossa on ainakin kaksi pistettä, joiden välinen suoran osa ei ole kokonaan joukossa, jolloin konveksisuuden ehto ei toteudu.

Esimerkkejä epäkonveksista muodosta ovat esimerkiksi ympyrästä leikattu pala, U-momainen tai rengasmainen alue. Myös polygonissa epäkonveksisuus ilmenee, kun jokin sisäkulma on suurempi kuin 180 astetta, eli joukko sisältää reflexiivisiä kulmia. Nämä muodot voivat olla haastavia sekä geometrisessa suunnittelussa että laskennallisessa käsittelyssä, koska niiden sisäiset polut ja täytettävyyden ehdot eivät seuraa konveksien määritelmien mukaisesti.

Optimoinnissa epäkonveksisuus tuo huomattavia haasteita. Konveksissa ongelmissa on usein yksi globaalinen minimikohta, mutta epäkonveksissa voi esiintyä lukuisia paikallisia minimejä, eivätkä tunnetut konveksisuusmenetelmät välttämättä löydä parasta ratkaisua. Tämän vuoksi käytetään erilaisia lähestymistapoja, kuten heuristiikkoja, satunnaisia hakualgoritmeja (esim. simulated annealing), geneettisiä algoritmeja tai jakamalla ongelman osiin ja yhdistämällä ratkaisuja.

Käyttökohteita ovat esimerkiksi tietojenkäsittely, tietokonegrafiikka, robotiikka, suunnittelujärjestelmät ja tilastolliset mallit, joissa epäkonveksit mallit paremmin kuvaavat todellisia ilmiöitä. Liittyviä käsitteitä ovat konveksisuus, konveksijoukko ja konvekseihin liittyvät rakenteet.