Konvex mängd

Från Wikipedia
Hoppa till: navigering, sök
En konvex mängd
En icke-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[redigera | redigera wikitext]

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

x_1, x_2 \in X \quad

implicerar att

\lambda x_1 + (1-\lambda) x_2 \in X \quad \forall \quad \lambda\in[0,1]

Med andra ord ska linjestycket mellan x_1 och x_2 ligga i X. [1] [2] [3]

Egenskaper[redigera | redigera wikitext]

Konvexkombinationer[redigera | redigera wikitext]

Huvudartikel: Konvexkombination

Om x_1, x_2, ..., x_n är punkter i ett reellt eller komplext vektorrum är en konvexkombination av dessa punkter en punkt som kan skrivas som:

\sum_{i=1}^n \lambda_i x_i \quad \forall\lambda_i > 0; \ i = 1,2, ..., n \quad \mathrm{med} \quad \sum_{i=1}^n \lambda_i = 1

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

Skärning mellan konvexa mängder[redigera | redigera wikitext]

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

Bevis

Låt C_1, C_2, ..., C_k vara en samling konvexa mängder och låt mängden D definieras enligt nedan:

D = \bigcap_{i=1}^k \ C_i

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

\lambda x_1 + (1-\lambda)x_2, \ \lambda \in [0,1]

också ligger i D.

Man vet att om x_1, x_2 är två element i D så är x_1, x_2 också två element i alla de konvexa mängderna C_1, C_2, ..., C_k.

Således, eftersom C_1, C_2, ..., C_k är konvexa, så ligger

\lambda x_1 + (1-\lambda)x_2, \ \lambda \in [0,1]

i varje en av mängderna C_1, C_2, ..., C_k.

Därför vet man att

\lambda x_1 + (1-\lambda)x_2, \ \lambda \in [0,1]

ligger inom skärningen mellan C_1, C_2, ..., C_k, dvs inom mängden D som då också är konvex. [5]

Konvext hölje[redigera | redigera wikitext]

Huvudartikel: 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. [6]

Stjärnformighet[redigera | redigera wikitext]

I en rak stjärna kan alla andra punkter ses från mitten, den är alltså stjärnkonvex, eller stjärnformig.
Huvudartikel: Stjärnformat område

Om C är ett godtyckligt reellt eller komplext vektorrum i ett ändligt antal dimensioner så gäller det att C är stjärn-konvex om det finns något x_0 i C sådant att konvexkombinationen av x_0 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[redigera | redigera wikitext]

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

Simplexmetoden[redigera | redigera wikitext]

Huvudartikel: Simplexmetoden

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

\min \ z = \sum_{j=1}^n c_j x_j

med bivillkor enlligt:

\sum_{j=1}^n a_{ij} x_j \le b_i \ , \quad 1 = 1, ..., m
x_j \ge 0 \ , \quad j = 1, ..., n

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

Sats
Bivillkoren och det tillåtna (konvexa) området för ett tvådimensionellt LP-problem.

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

Bevis

Låt x^{(1)} , x^{(2)} vara två godtyckliga punkter som är tillåtna under samtliga bivillkor i. Detta kan skrivas som att

\sum_{j=1}^n a_{ij} x_j^{(1)} \le b_i \quad\mbox{och} \quad \sum_{j=1}^n a_{ij} x_j^{(2)} \le b_i

Betrakta sedan en punkt på linjen mellan x^{(1)} , x^{(2)} som är en konvexkombination av de båda punkterna, dvs en punkt

x = (1 - \lambda) x^{(1)} + \lambda x^{(2)},\mbox{ med }\lambda \in [0,1]

Multiplicera sedan de båda olikheterna ovan med (1 - \lambda) respektive \lambda och addera de båda. Detta ger:

(1 - \lambda) \sum_{j=1}^n a_{ij} x_j^{(1)} + \lambda \sum_{j=1}^n a_{ij} x_j^{(2)} \le (1 - \lambda) b_i + \lambda b_i = b_i

och detta kan skrivas:

\sum_{j=1}^n a_{ij} [(1 - \lambda) x_j^{(1)} + \lambda x_j^{(2)}] \le b_i

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

\sum_{j=1}^n a_{ij} x_j \le b_i

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. [7]

Se även[redigera | redigera wikitext]

Källor[redigera | redigera wikitext]

  1. ^ Bazaraa, M.S; Shetty, C.M: "Lecture Notes in Economics and Mathematical Systems - Foundations of Optimization", sidan 16. Springer-Verlag, 1976
  2. ^ Ekeland, I; Temam, R: Convex Analysis and Variational Problems", sidan 3. North-Holland Publishing Company, 1976
  3. ^ Lundgren, J; Rönnqvist, M; Värbrand, P: "Optimeringslära", sidor 28-36. Studentlitteratur, 2007
  4. ^ Cooper; Steinberg: "Introduction to Methods of Optimization", sidor 67-71. W.B. Saunders Company, 1970
  5. ^ Cooper; Steinberg: "Introduction to Methods of Optimization", sidor 68-69. W.B. Saunders Company, 1970
  6. ^ Cooper; Steinberg: "Introduction to Methods of Optimization", sidor 73-78. W.B. Saunders Company, 1970
  7. ^ Lundgren, J; Rönnqvist, M; Värbrand, P: "Optimeringslära", sidor 89-90. Studentlitteratur, 2007