Konvex mängd

En mängd i ett reellt eller komplext vektorrum är konvex om varje punkt längs en sträcka mellan två godtyckligt valda punkter i mängden också ligger i mängden. Man kan även uttrycka det som att alla andra punkter går att "se" från varje punkt i mängden.

Konvex mängd är ett begrepp som är vanligt förekommande inom optimeringsläran och olika grenar av mängdläran.

Definition
En mängd X i ett reellt eller komplext vektorrum sägs vara konvex om

implicerar att

Med andra ord ska linjestycket mellan  och  ligga i X.

Egenskaper

Konvexkombinationer

Om  är punkter i ett reellt eller komplext vektorrum är en konvexkombination av dessa punkter en punkt som kan skrivas som:

En mängd är konvex om och endast om den innehåller alla sina konvexkombinationer.

Skärning mellan konvexa mängder
Snittet mellan ett ändligt antal konvexa mängder är också konvext.

Bevis
Låt  vara en samling konvexa mängder och låt mängden D definieras enligt nedan:

Då önskar man visa att för två godtyckliga punkter x1 och x2 i D så gäller att

också ligger i D.

Man vet att om  är två element i D så är  också två element i alla de konvexa mängderna .

Således, eftersom  är konvexa, så ligger

i varje en av mängderna .

Därför vet man att

ligger inom skärningen mellan , dvs inom mängden D som då också är konvex.

Konvext hölje

För varje mängd X i ett reellt eller komplext vektorrum finns en minsta konvex mängd som innehåller mängden. Denna mängd kallas för X:s konvexa hölje. Det konvexa höljet till X kan ses som snittet av alla konvexa mängder som innehåller X, eller som mängden av alla konvexkombinationer av punkterna i X.

Stjärnformighet

Om C är ett godtyckligt reellt eller komplext vektorrum i ett ändligt antal dimensioner gäller det att C är stjärnkonvex om det finns något  i C sådant att konvexkombinationen av  och alla andra punkter i C ligger inom C.

Således vet man att en konvex mängd alltid är stjärnformig, men stjärnformiga mängder är inte alltid konvexa.

Tillämpningar
Konvexa mängder, tillsammans med konvexa funktioner används för att lösa flera typer av problem inom flera olika matematiska områden.

Simplexmetoden

Simplexmetoden används för att lösa LP-problem vars allmänna form är:

med bivillkor enligt:

Ovan så är  koefficienten i målfunktionen för variabeln .  är motsvarande koefficient i bivillkor i, och  är motsvarande högerledskoefficient.

Sats

Det tillåtna området (området som definieras av bivillkoren) i ett LP-problem utgör en konvex mängd.

Bevis
Låt  vara två godtyckliga punkter som är tillåtna under samtliga bivillkor i. Detta kan skrivas som att

Betrakta sedan en punkt på linjen mellan  som är en konvexkombination av de båda punkterna, dvs en punkt

Multiplicera sedan de båda olikheterna ovan med  respektive  och addera de båda. Detta ger:

och detta kan skrivas:

Detta säger att även den godtyckliga punkten är tillåten med avseende på bivillkor i, och detta är definitionen på en konvex mängd. En slutsats som kan dras av detta är att mängden av alla lösningar till villkoret

då utgör en konvex mängd. Detta resonemang kan tillämpas på alla övriga bivillkor till det allmänna LP-problemet, vilket ger slutsatsen att det tillåtna området i ett LP-problem är en konvex mängd.

Se även
Konvex funktion

Källor

Externa länkar 

Geometri
Konvex analys