konveksiset

Konveksiset joukot ovat geometriassa ja analyysissä keskeinen käsite. Joukko C on konveksi, jos kaikille x ja y ∈ C sekä kaikille t ∈ [0,1] pätee (1−t)x + ty ∈ C. Tämä tarkoittaa, että x ja y:n välinen suora eli line segmentti [x,y] kuuluu kokonaisuudessaan C:n sisälle.

Esimerkkejä konveksista joukosta ovat koko R^n, kaikki intervallit [a,b] ⊂ R sekä kaikki konveksit monikulmiot ja polytopit. Yleisemmin polytopit (monikulmioita ja niiden yleisempiä polytopeja) ovat konveksia, jos niiden muodostavat kärjet ja sivut määrittävät alueen siten, ettei mikään kohtaa jää ulkopuolelle. Ei-konveksit esimerkit ovat kaksinainen muodostelma erillisiä pilkottuja osia, joiden välillä ei ole kaikkien pisteiden kautta kulkevaa suoraa sisällä.

Keskeisiä ominaisuuksia ovat, että joukon leikkaus kahdesta konveksista joukoista on konveksi, sekä Minkowski-summa C+D = {c+d | c∈C, d∈D} on konveksi kun C ja D ovat konveksia. Affiinikuva f(x) = Ax + b säilyttää konveksisuuden, ja myös konveksien joukkojen yhdistelmä ei yleensä ole konveksinen; unionti erillisiä konveksia joukkoja voi olla ei-konveksi.

Sovelluksia löytyy optimoinnista, geometrian tilaprosessointiin ja taloudellisista malleihin. Tärkeä käsite on konveksihila conv(S), joka on pienin konveksi joukko, joka sisältää joukon S. Carathéodory’n teoreema kertoo, että missä tahansa R^n:ssa konveksihilassa esitys voidaan saavuttaa yhdistelmien avulla enintään n+1 pisteen from S.