Stückweise Linearität - Param. Optimierung

Darksun · Newbie Anmeldungsdatum: 18.08.2009 Beiträge: 7

Hi Leute,

ich habe ein kleines Problem. Ich habe einen Seminarvortrag über o.g. Thema und hänge an einer Beweisstelle fest.

(LP)(c) max c^T x
unter Ax ≤ b, x ≥ 0,
dabei sei also c variabel.

Satz:
Es sei A ∈ R^(m,n) eine Matrix und b ∈ R^m ein Vektor, für die
P+(A, b) := {x ∈ R^n : Ax ≤ b, x ≥ 0} ein nichtleeres Polyeder ist. Sei
BP(A, b) := {c ∈ R^n : c^T x ist auf P+(A, b) nach oben beschränkt}
sowie für c ∈ BP(A, b)
M(c) := max {c^T x: x ∈ P+(A, b)}.

Dann gilt:

(1) BP(A, b) ist ein konvexer Kegel.
(2) Es gibt endlich viele Vektoren v_1, . . . , v_N ∈ R^n mit M(c) = max {c^T v_i : i = 1, . . . , N} für alle c ∈ BP(A, b).
(3) M(c) ist konvex und stückweise linear auf BP(A, b).

Beweis:
(...) Da jede beschränkte lineare Zielfunktion c^T x ihr Maximum auf einer der endlich vielen Ecken von P+(A, b) annimmt,
können wir die v_i als die Ecken von P+(A, b) wählen. Das zeigt (2); Behauptung (3) ist dann eine unmittelbare Folgerung.

Frage: Warum ist (3) eine unmittelbare Folgerung? Vor allem, wie zeigt man hier die stückweise Linearität?

Wäre nett, wenn Ihr mir hier auf die Sprünge helfen könntet.

Grüße

Darksun · Newbie Anmeldungsdatum: 18.08.2009 Beiträge: 7

Hi, hat keiner eine Idee wie das gehen könnte?

Also ich habe so die Konvexität der Funktion M(c) gezeigt:
λ∈[0,1] und c, c' ∈ BP(A,b)

M(λc+(1-λ)c') = max {(λc+(1-λ)c')^T v_i : i = 1, . . . , N}
= max {λc^T v_i +(1-λ)c'^T v_i : i = 1, . . . , N}
≤ max {λc^T v_i : i = 1,...,N} + max {(1-λ)c'^T v_i : i = 1,...,N}
= λmax {(c^T v_i : i = 1,...,N} + (1-λ)max {c'^T v_i : i = 1,...,N}
= λM(c) + (1-λ)M(c')

Ist das so Okay? Beweisen ist leider nicht meine Stärke.

Aber die stckw. lin. von M(c) auf BP(A,b) sehe ich immer noch nicht...