22

Nichtlineare Optimierung (Subject) / Nino (Lesson)

This lesson was created by Tofu_1.

Learn lesson

This lesson is not released for learning.

back  |  next 1 / 1

• will ich dieses Fach gut bestehen? JA!
• Weierstraß Existenz eines Optimums Sei eine Funktion f : D --> R mit D aus R n gegeben und stetig. Sei K teilmenge D kompakt. Dann stimmt auf K das Infimum mit dem Minimum überein. Insbesonderenimmt f sein Minimum auf K an
• Niveaumenge def. Sei eine Funktion f : D --> R mit D teilmenge R n N(f, α) := { x aus D : f(x) <= α}
• Zusammenhang Niveamennge und existenz eines MInimums Beweis? Sei f : D --> R stetig mit D Teilmenge R n und Ω Teilmenge D ist abgeschlossen. Für ein ω aus Ω sei N(f, f(ω)) kompakt. Dann hat f ein globales Minimum auf Ω.  Beweis:  Sei α := inf x aus Ω f(x) Dann gilt α <= f(ω). Es gilt Ω Schitt ((f, f(ω)) ist kompakt.  Werte aus Ω, deren Funktionswert kleiner als f(ω) ist  sind müssen in N(f, f(ω)) liege.  --> α = inf x aus Ω f(x) = inf x aus (Ω Schnitt N(f, f(ω)))  = f(y)  Da der Schitt kompakt ist und f stetig existiert f(y) f(y) ist das gesuchte Minimum
• Was können wir über die Existenz von Minima von stetigen Funktionen sagen, die folgendes erfüllen f: D --> R mit D aus R n und lim(|x| --> unendlich) = unendlich? Sie hat ein globales Minimum, da für alle y aus D ist  N(f, f(y)) kompakt.  
• positiv definit positiv semidefinit eine Matrix H aus R nxn heißt ..., falls für x aus R n /{0} gilt x T H x > 0 gilt x T H x >= 0 
• äquivalente Formulierung positiv definit : Sei x aus R n H ist pos definit <==> x T H x >= α |x| 2  mit α > 0 offenbar gilt dann x T H x --> unendlich, falls |x| --> unendlich
• Eine Menge M (teilmgene R n) heißt konvex, falls für x, y aus M und t aus [0, 1]  gilt, dass auch die Strecke [x,y] in der Menge enthalten ist mit [x,y] := {x aus R n : t*x + ((1-a)*y)}
• Eine Funktion f heißt konvex auf C, wenn f: D --> R mit D teilmenge R n, C konvex und nicht leer und C teilmenge D Seien x, y aus C a*f(x)+(1-a)*f(y) >=f(a*x+(1-a)*y) Wenn man x=/= y und t aus (0,1) und > fordert erhält man stickte konvexität
• schöne Eigenschaft konvexer Optimierungsaufgaben i) lokale Minima sind globale Minima ii) Die Lösungsmenge ist konvex Beweis? Sei Ω eine Teilmenge des Definitionsbereichs der Funktion f. f sei konvex auf Ω. i) sei x* eine lokale Lsg. Dann existiert ein r aus R, s.d. f(x) >= f(x*) für alle  x aus Ω Schnitt B(x*, r) Wähle y aus Ω beliebig. Betrachte x*+t(y-x*)  für kleine t > 0  für t aus [0,1] lieft der Wert in Ω, da  x*+t(y-x*) = x* +ty -tx*= x*(1-t) +t*y in Ω, da konvex Für hinreichend kleine t gilt auch, x*+t(y-x*) ist in B(x*, r) Daher gilt: f(x*) <= f((1-t)x*+ty)) <= (1-t) f(x*) +t*f(y) (1. gilt für alle aus Kugeln, konvex) durch umstellen erhält man f(x*) <= f(y)
• Advertisement
• schöne Eigenschaft konvexer Optimierungsaufgaben i) lokale Minima sind globale Minima ii) Die Lösungsmenge ist konvex Beweis? Sei Ω eine Teilmenge des Definitionsbereichs der Funktion f. f sei konvex auf Ω. i) sei x* eine lokale Lsg. Dann existiert ein r aus R, s.d. f(x) >= f(x*) für alle  x aus Ω Schnitt B(x*, r) Wähle y aus Ω beliebig. Betrachte x*+t(y-x*)  für kleine t > 0  für t aus [0,1] lieft der Wert in Ω, da  x*+t(y-x*) = x* +ty -tx*= x*(1-t) +t*y in Ω, da konvex Für hinreichend kleine t gilt auch, x*+t(y-x*) ist in B(x*, r) Daher gilt: f(x*) <= f((1-t)x*+ty)) <= (1-t) f(x*) +t*f(y) (1. gilt für alle aus Kugeln, konvex) durch umstellen erhält man f(x*) <= f(y)
• Simplex Algorithmus von idee:  Simplex vorgegeben mit n+1 Punkten größter Funktionswert ermittelt --> soll durch kleineren ersetzt werden 1. Versuch: An Achse der anderen Knoten spiegeln (reflektion):  erfolgreich oder =: gucken ob es gut wäre weiter zu gehen (Expasion) sonst: Kontraktion: größter Punkt wird auf geraden bewegt wie bei Spiegelung, aber nur zur hälfe an Spiegelachse rangebracht.  auch nicht gut: Kompression:  besser Punkt bleibt, Die strecken des besten Punktes zu nr. 2 und 3 werden halbiert.
• Mutations-Selektions-Verfahren 1. wähle startpunkt 2. wähle zufällige Veränderung des Startwertes,  falls besser oder = : nehme neuen Punkt und starte als neuen Stützpunkt, bis Abbruchkriterium erreicht ist falls schlechter: nehme alten PUnkt und wähle neue zufällige Abweichung
• Notwendige Bedingung für Differenzierbare Funktionen das x* ein lokales Minumum ist mit D Teilmenge R n offen, nicht leer f : D --> R Gradient(f(x*)) = 0 Zeichen für Gradient: umgedrehtes Dreieck
• Notwendige Bedingung für Differenzierbare Funktionen das x* ein lokales Minumum ist mit D Teilmenge R n offen, nicht leer f : D --> R Gradient(f(x*)) = 0 Zeichen für Gradient: umgedrehtes Dreieck wenn Gradient(f(x*)) = 0 gilt, dann heißt x* ein stationärer Punkt von f
• Notwendige Bedingung für Minima (x*), wenn f diff`bar ist Gradient(f(x*)) = 0 Zeichen für Gradient: umgedrehtes Dreieck
• stationärer Punkt einer diff`baren Funktion gradient ist in dem Punkt 0
• f ist richtungsdifferenzierbar in die Richtung h, falls f ist richtungsdifferenzierbar, falls der folgende Grenzwert existiert: lim t gegen 0 von oben [f(x + t*h) -f(x)] / t falls der Grenzwert für alle h existiert h aus R n
• Zusammenhang Lokales Minima und Richtungsableitung Ist x* ein lokales Minimum der Funktion f mit x* aus D und f an der Stelle x* Richtungsdiffbar, dann gilt f`(x*, h) >= 0 für alle h aus R n (Richtungsableitung in Richtung h)
• Beweis x* ist Minimum --> Richtungsableitung >= 0 F : D --> R, D teilmenge R n, mit D offfen D ist offen, daher existiert ein r >0, so dass f(x) >= f(x*) für alle x aus B(x*, r) Sei h beliebig, aber fest Dann gilt x* +t*h ist in B(x*, r) für kleine t, mit t > 0 f(x* + t*h) -f(x*) >= 0 [f(x* + t*h) -f(x*)] / t >= 0 f´(x*,h) >= 0  
• notwendige Bedingung für Minima 2. Ordnung Sei f in einer Umgebung von x* 2 mal diff`bar Ist x* ein lokales Minimum von  (PU) f, dann muss  hT f´´(x*) h >= 0 gelten
• Beweis notwendige Bedingung 2. Ordnung (für minima) (skizze) sei  h aus R n beliebig, aber fest Sei F(t) = f(x*+t*h) F hat lokales Minimum bei t = 0 und ist 2 mal diff`bar Taylorentwicklung: F( oliver fragen

back  |  next 1 / 1