Astrid Pilorz - uni-bayreuth.denum.math.uni-bayreuth.de/.../01069/Astrid_Pilorz_Vortrag.pdfwobei p, q konvexe Funktionen auf C. Eine Funktion, die im Rn d.c. ist, ist uberall d.c

Seminar Optimierung und optimale Steuerung

Globale Optimierung

Astrid Pilorz

27. Juni 2008

Einfuhrung: Globale Optimierung

Einfuhrung: Globale Optimierung

• Die Globale Optimierung hat viele Einsatzgebiete

• Existenz von vielen lokalen Optimalpunkten verhindert dieLosung durch klassische nichtlineare Optimierung

• Ablauf:1) grundlegendes Werkzeug: konkave Minimierung2) spezielle Klasse: d.c. Programming

(I) KONKAVE MINIMIERUNG

Konkave Minimierung

Einfuhrendes Beispiel

• q Fabriken

• Nachfrage dj (j=1,..,m) an m Bestimmungsorten

• Selbstkosten g(y) :=q∑

i=1gi (yi ), Fabrik i produziert

yi Einheiten, gi (yi ) konkav

• Transportkosten linear cij pro Einheit, die von Fabrik i zumZiel j transportiert wird

Konkave Minimierung

Wir erhalten folgendes Programm:

minq∑

i=1

m∑j=1

cij · xij + g(y)

s.t.m∑

j=1xij = yi (i=1,..,q)

q∑i=1

xij = dj (j=1,..,m)

xij ≥ 0 ∀ i , jyi ≥ 0 ∀ i

Grundbegriffe

Definition: konvexes Polytop

Menge aller konvexen Linearkombinationen endlich vieler Punktedes Rn.

Grundbegriffe

Definition: Simplex

konvexes Polytop, das von n+1, nicht auf einer Hyperebeneliegenden, Punkten des Rn aufgespannt wird.

Grundbegriffe

Definition: konvexer polyedrischer Kegel

Menge aller nichtnegativen Linearkombinationen endlich vielerPunkte des Rn heißt konvexer polyedrischer Kegel.

Grundbegriffe

Definition: konvexes Polyeder

Seien P ein konvexes Polytop und C ein konvexer polyedrischerKegel. Dann nennt man P + C := {x = xp + xc |xp ∈ P, xc ∈ C}konvexes Polyeder.

Verschiedene Unterteilungen

Definition: Polyedrische Teilung

P ⊂ Rn mit int P 6= ∅I eine endliche Menge von IndicesEine Familie {Pi : i ∈ I} von Teilpolyedern aus P mit int Pi 6= ∅(i ∈ I ) heißt polyedrische Teilung von P⇐⇒ P :=

⋃i∈I Pi und int Pi ∩ int Pj = ∅ ∀ i ; j ∈ I , i 6= j

- Teilung muss die Struktur des Polyeders erhalten -


Definition: Radiale Teilung

P n-eckiger Simplex mit Eckenmenge V (P) = {v0, v1, ..., vn}.Wahle Punkt w ∈ P, w /∈ V (P), der durch

w =n∑

i=0λivi , λi ≥ 0 (i=0,..,n),

n∑i=0

λi = 1

dargestellt werden kann.Fur jedes i mit λi > 0 bilde den Simplex P(i,w) von P, durchErsetzen der Ecke vi durch w,z.B. P(i ,w) = co{v0, ..., vi−1,w , vi+1, ..., vn}.

Diese Unterteilung wird radiale Unterteilung genannt.


Bsp: Radiale Teilung

V (P) = {v0, v1, v2}v0 = (0, 0)v1 = (1, 0)v2 = (0, 1)w = ( 1

10 ,13)

P(0,w) = co{w , v1, v2}P(1,w) = co{v0,w , v2}P(2,w) = co{v0, v1,w}

Konvexkombination w = 13v2 + 1

10v1 + (1− 13 −

110)v0

BRANCH and BOUND Algorithmus

Begriffserklarung

• von engl. to branch = sich verzweigen, abzweigenbound = die Grenze, Schranke

• Lockerung der zulassigen Menge

• Aufteilung in zunehmend verfeinerte Teile (branching)

• Ermitteln der unteren und oberen Grenzen des minimalenZielfunktionswertes (bounding)


Algorithmus

• Lose konkaves Minimierungsproblem:min f (x), x ∈ D,wobei D ein Polytop im Rn, int D 6= ∅,f reele konkave Funktion auf Menge A ⊃ D

• Annahme: Mind. 1 zulassiger Punkt ist bekanntQ:= Menge der zulassigen Punkte bis zur aktuellen StufeP:= Relaxation von D zur Verbesserung der unteren Schranke


Bestimme P, Q mit D ⊂ P und Q ⊂ Dγ ← min{f (x) : x ∈ Q}Wahle v ∈ Q mit f (v) = γBerechne untere Schranke µ(P) ≤ min{f (x) : x ∈ D}M := {P}µ← µ(P), stop ← false, k ← 1While stop = false do

if γ = µ thenstop ← true

else· · ·

end ifSetze M ← R , k ← k + 1end while


else

P1, ...,Pr mit P =⋃r

i=1 Pi , int Pi ∩ int Pj = ∅Berechne untere Schranke µ(Pi ) uber D ∩ Pi mit µ(Pi ) ≥ µAktualisiere Q durch Einschließen aller gefundenen PunkteAktualisiere γ = min {f (x) : x ∈ Q}, v ∈ Q mit f (v) = γM ← (M \ P) ∪ {P1, ...,Pr}Losche P ∈ M mit µ(P) ≥ γ , P ∩ D = ∅Bezeichnet R die zuruckbleibende Menge

µ←

{γ if R = ∅min{µ(P) : P ∈ R} sonst

Wahle P ∈ R mit µ(P) = µ


Konvergenz

Fur jede unendliche Folge {Pkq},Pkq ⊃ Pkq+1 (q=1,2,...)von aufeinanderfolgenden Teilmengen sind die Grenzen desSchrittes kq

limq→∞(γkq − µkq ) = limq→∞(γkq − µ(Pkq )) = 0=⇒ µ = limk→∞ µk = limk→∞ f (vk) = limk→∞ γk = γ

und jeder Haufungspunkt v∗ der Folge {vk}ist Optimallosung von min{f (x) : x ∈ D}.

Simplizialer Branch and Bound

Modifizierung

• Bestimme D = {x ∈ Rn : A · x ≤ b} mit A ∈ Rmxn, b ∈ Rm

• Simplex S ⊃ D mit mindestens 1 Schnittpunkt

• Untere Schranke µ(S) ≤ min{f (x) : x ∈ S ∩ D}dazu min {F (x) : x ∈ S ∩ D} mit F (x) = co(f(x))

• Wir erhalten F (x) =n+1∑i=1

αi f (vi )

mit x =n+1∑i=1

αivi ,n+1∑i=1

αi = 1


Modifizierung

• M := {Si}, Teilung in Untersimplices radial

• µ(S) ist Losung des LP

µ(S) = min{n+1∑i=1

αi f (vi ) : A V α ≤ b,n+1∑i=1

αi = 1}

mit V:= Matrix mit Spalten {v1, ..., vn+1}


Beispiel

f (x) = − | x1 + 12x2 + 2

3x3 |32 −x2

1

A=

1 1 11 1 −1

4−2 −2 10 0 1

b=

2113

Iteration 1: S1 =

[000

,

400

,

040

,

004

]Lose das LP mit S1, man erhaltOptimallosung α1 = (0.5, 0.3, 0, 0.2)T

untere Schranke µ1 = µ(S1) = −0.8071zulassiger Punkt x(S1) = (1.2, 0, 0.8)T

obere Schranke γ1 = f (x(S1)) = −3.722



Iteration 2:S1 wird radial unterteilt in 3 weitere Simplices

S1,1 =

[1.20

0.8

,

400

,

040

,

004

]µ(S1,1) = γ1

S1,2 =

[000

,

1.20

0.8

,

040

,

004

]µ(S1,2) = γ1

S1,3 =

[000

,

400

,

040

,

1.20

0.8

]µ(S1,3) = −6.0

S1,1 und S1,2 werden geloscht



Iteration 3:S1,3 wird unterteilt in 2 weitere Simplices

S2,1 =

[100

,

400

,

040

,

1.20

0.8

]µ(S2,1) = γ2

S2,2 =

[000

,

100

,

040

,

1.20

0.8

]µ(S2,2) = γ2

Optimallosung x(S1) = (1.2, 0, 0.8)T

Optimalwert f (x) = −3.722


(II) D.C. PROGRAMMING

Grundlagen

Definition: d.c. Funktion

Reele Funktion f auf konvexer Menge C ⊆ Rn

f wird d.c. auf C genannt, wenn ∀ x ∈ C gilt:

f (x) = p(x)− q(x) ,

wobei p, q konvexe Funktionen auf C.

Eine Funktion, die im Rn d.c. ist, ist uberall d.c.

Grundlagen

Definition: d.c. Optimierungsproblem

Ein globales Optimierungsproblem heißtd.c. Optimierungsproblem oder d.c. Programm

⇐⇒ min f (x)s.t. x ∈ C , gj(x) ≤ 0 (j = 1...m)

mit C abgeschlossener, konvexer Teilmenge des Rn undf und gj d.c. Funktionen

Raum von d.c. Funktionen

Eigenschaften von d.c. Funktionen

Seien f , fi (i=1...m) d.c. Funktionen.Folgende Funktionen sind auch d.c.:

i)m∑

i=1λi fi (x) ∀λi ∈ R

ii) maxi=1...m fi (x) und mini=1...m fi (x)

iii) | f (x) |, f +(x) := max{0, f (x)}, f −(x) := min{0, f (x)}

iv)m∏

i=1fi (x)


Eigenschaften von d.c. Funktionen

v) f : Rn → R heißt lokal d.c.⇐⇒ ∀ x0 ∈ Rn ∃ ein Ball B(x0, ε) = {x ∈ Rn : ‖x − x0‖ < ε}

(ε > 0), s.d. f d.c. auf B(x0, ε)

vi) Jede lokale d.c. Funktion ist d.c.

vii) Jede Funktion f : Rn → R , deren 2. Ableitung uberallstetig ist, ist d.c.


Differenzierbarkeitseigenschaften von d.c. Funktionen

viii) d.c. Funktionen sind lokal Lipschitz-stetig im Rn,da ∀ x0 ∈ Rn ∃ Ball B(x0, ε) und eine Konstante L,s.d. ∀ x , y ∈ B(x0, ε) gilt: |f (x)− f (y)| ≤ L · ‖x − y‖

ix) die Richtungsableitung f ′(x , d) der d.c. Funktionf = p − q (p,q konvex) existiert in jedem x ∈ Rn

in jede Richtung d ∈ Rn und f ′(x , d) = p′(x , d)− q′(x , d),wobei f ′(x , d) wieder d.c. Funktion

x) der Gradient einer d.c. Funktion existiert fast uberall

Zusammenhang mit konkaver Minimierung

Betrachte d.c. Programm

min f (x)− g(x)s.t. x ∈ D

wobei D Polytop im Rn mit int D 6= ∅ undg , f konvexe Funktionen im R

Aquivalent dazu

min t − g(x)s.t. x ∈ D, f (x)− t ≤ 0

mit Zielfunktion t − g(x) konkav undzulassiger Menge {(x , t) ∈ Rn+1 : x ∈ D, f (x)− t ≤ 0} konvex

Anwendungen: Aufgeteiltes d.c. Programm

Bsp: Produktions-Transport-Planungsproblem

• q Fabriken

• Nachfrage dj (j=1,..,m) an m Bestimmungsorten

• Selbstkosten g(y) =q∑

i=1gi (yi ), wenn Fabrik i

yi Einheiten produziert (i=1,..,q) mit gi (yi ) konkav

• Transportkosten linear cij pro Einheit, die von Fabrik izum Ziel j transportiert wird


Bsp: Produktions-Transport-Planungsproblem

• Strafe h(z) =m∑

j=1hj(zj), wenn Ziel j

zj 6= dj Einheiten erhalt (j=1,..,m)

• Annahme:hj nichtnegative, fallende, konvexe Funktion in [0, dj ] mithj(dj) = 0


Wir erhalten folgendes aufgeteiltes d.c. Programm:

minq∑

i=1

m∑j=1

cij · xij + g(y) + h(z)

s.t.m∑

j=1xij = yi (i=1,..,q)

q∑i=1

xij = zj (j=1,..,m)

xij ≥ 0 ∀ i , j , yi ≥ 0 ∀ i

dj ≥ zj ≥ 0 ∀ j

Anwendungen: Konstruktive Entwurfsarbeit

Zentriertes Anordnungsproblem

• D ⊂ Rn abgeschlossene Menge mit int D 6= ∅• gi : Rn → R, gi (x) ≤ 0, i ∈ I ,

endliche Zahl von Ungleichungen, d.c.

• K ⊂ Rn kompakte, konvexe Menge mit 0 ∈ int K

• Definiere rD : D → R mit rD(x) := max{r : x + r · K ⊂ D}• Problem: max rD(x)

s.t. x ∈ D

Anwendungen: Konstruktive Entwurfsarbeit

Zentriertes Anordnungsproblem in der Praxis

Anwendung: Diamantenindustrie

Anwendungen

Weitere Anwendungen

• MiniMax-Problem(Packprobleme, Steiner-Baum-Problem,..)

• Standortplanung (Anziehung und Abstoßung)

• Qualitatskontrolle (Abweichung nur um bestimmten Faktor)

• ...

Vielen Dank fur IhreAufmerksamkeit!

Documents

Astrid Pilorz - uni-bayreuth.denum.math.uni-bayreuth.de/.../01069/Astrid_Pilorz_Vortrag.pdfwobei p, q konvexe Funktionen auf C. Eine Funktion, die im Rn d.c. ist, ist uberall d.c