Prof. Dr. Dr. J. Hansohm Nichtlineare Optimierung Einführung Konvexe Optimierungsprobleme Spezielle...

Prof. Dr. Dr. J. Hansohm

Nichtlineare Optimierung

EinführungKonvexe Optimierungsprobleme

Spezielle Verfahren (Penalty, etc.)Evolutionsstrategien


Nichtlineare Optimierung - Einführungx n f : n nichtlinear)

gi: n i = 1, ..., m

max f (x)gi(x) bi i = 1, ..., m

x


Nichtlineare Optimierung - Beispiel (1)p: Preis-Absatz-FunktionC: Stückkosten-Funktion unter Berücksichtigung

der Lernrate

Deckungsbeitrag = x p(x) - c(x) xx

p(x) = 1/(x x)c(x) = 0.64x

max f(x) = 1/x - x * 0.64x

x


Nichtlineare Optimierung - Beispiel (2)Beispiel Wertpapierportfolion Wertpapiere mit erwartetem Gewinn i bei einer Standardabweichung von i (i = 1, ..., n)xi Investitionshöhe in Wertpapier i

max i xi - ij xixj

xi 0 (i = 1, ..., n)

wobei ij die Kovarianz von Wertpapier i bzgl. j darstellt und 0 die Risikopräferenz des Entscheidungsträgers widerspiegelt


Literatur: Neumann/Morlock: Operations Research

München 1993, Hanser-Verlag, Kapitel 4 Seite 536-537

Domschke/Drexl: Einführung in Operations Research 3. erw. verb. Auflage, Springer-Verlag 1995, Kapitel 8 Abschnitt 8.1. Seiten 159-163


Nichtlineare Optimierung - Definitionenx n heißt zulässig gi(x) bi (i = 1, ..., m) und x 0x n heißt (global) optimal x zulässig und für alle y n, y zulässig

gilt: f(x) f(y)U (x) ={yn | || x-y || < , zulässig} heißt zulässige Umgebung von xx n heißt lokal optimal x zulässig und für alle y U(x) gilt:

f(x) f(y) für wenigstens ein > 0


Lineare - Nichtlineare OptimierungLineare Optimierung: lokales Optimum ist globales Optimum Wenn eine optimale Lösung existiert, so ist eine optimale Lösung unter den endlich vielen Ecken des Restriktionspolyeders zu finden.Nichtlineare Zielfunktion, lineare Nebenbe-dingungen: Lokales Optimum nicht notwendigerweise globales Optimum Optimum kann im Inneren des Restriktions-polyeders liegen



München 1993, Hanser-Verlag, Kapitel 4 Seite 538



Überblick über OptimierungsverfahrenZielfunktion

Restriktionen linear quadratisch beliebig, nichtlinear,differenzierbar

keine, x analytisch lösbar eindimensionaleOptimierung

keine, x n analytisch lösbar unrestringierteOptimierung

linear, x n lineareOptimierung(Simplex u.a.)

quadratischeOptimierung (z.B.Wolfe 1959)

z.B. reduzierte Gra-dienten (Wolfe1963)

linear, x n ganzzahligeOptimierung

nichtlinear (allgemeinerFall)

z.B. projizierter Lag-range (Murtagh/Saunders 1982)

Zielfunktion

Restriktionen linear quadratisch beliebig, nichtlinear,differenzierbar

keine, x analytisch lösbar eindimensionaleOptimierung

keine, x n analytisch lösbar unrestringierteOptimierung

linear, x n lineareOptimierung(Simplex u.a.)

quadratischeOptimierung (z.B.Wolfe 1959)

z.B. reduzierte Gra-dienten (Wolfe1963)

linear, x n ganzzahligeOptimierung

nichtlinear (allgemeinerFall)

z.B. projizierter Lag-range (Murtagh/Saunders 1982)


Nichtlineare Optimierung - Einfachster Fall

f: stetig differenzierbarmax f(x) x0

notwendige Bedingung für ein Optimum x > 0: f'(x) = 0

nicht hinreichend: (lokales) Minimum, Maximum oder Sattelpunktf zweimal stetig differenzierbar:

f'(x) = 0, f''(x) < 0 hinreichend für

x lokales Optimum und x > 0


Einfache Nichtlineare Optimierung - Beispiel

(lokales) Maximum

lokales Minimum

lokales Maximum

Sattelpunkt

x

f(x)

eigentliches Maximum


Nichtlineare unrestringierte Optimierung

f: nzweimal stetig differenzierbarmax f(x) x n

notwendige Bedingung für ein (lokales) Optimumgrad f(x) = 0

hinreichende Bedingung für ein lokales Optimumgrad f(x) = 0, H(x) negativ definit

gradf x fx

x fx

xn

T

( ) ( ),..., ( )

1

H xxx

fx x

x

fx x

xfx

x

n

n n

( )

( ) ... ( )

( ) ( )

2

12

2

1

2

1

2

2


Nichtlineare unrestringierte Optimierung (1)Definitheit einer Matrix:Eine symmetrische Matrix H heißt positiv (semi-)definit, wenn xT x > 0 (> 0) für alle x 0 gilt. Satz: Eine symmetrische Matrix H ist positiv definit genau dann, wenn alle Hauptabschnittsdeterminanten

positiv sind.Satz: Eine symmetrische Matrix H ist positiv definit genau dann, wenn alle Eigenwerte positiv sind.

H h

Hh hh h h h h h

Hn H

1 11

211 1221 22

11 22 12 21


Nichtlineare unrestringierte Optimierung - Beispiel (1)

min x12 + 3x2

2 + x1x2 - 3x1 - 7x2

grad f(x) = (2x1 + x2 - 3, 6x2 + x1 - 7) = 0 x1 =1, x2 = 1

2 - = 0 (2 - ) (6 - ) - 1 = 02 - 8+ 11 = 0

= 4 ± > 0 positiv definit

H x( )

2 11 6

5


Nichtlineare unrestringierte Optimierung - Beispiel (2)



München 1993, Hanser-Verlag, Kapitel 4 Abschnitt 4.3. Seite 555-567

Domschke/Drexl: Einführung in Operations Research 3. erw. verb. Auflage, Springer-Verlag 1995, Kapitel 8 Abschnitt 8.2. - 8.3 Seiten 163-168


Konvexe Menge

Definition Konvexität von Mengen:

Eine (Punkt-)Menge K ist konvex, wenn mit je zwei Punkten P1, P2 K auch alle Punkte

P1 + (1 - P2 für 0 1

zu K gehören.


Konvexe und Nichtkonvexe Menge - Beispiele

Beispiele für konvexe und nicht-konvexe Mengen

Satz: Der Durchschnitt zweier konvexer Mengen ist konvex.


Konvexe FunktionenDefinition Konvexität von Funktionen:Eine Funktion f: K , welche eine konvexe Menge K in abbildet, heißt konvex, wenn für je zwei Punkte x1, x2 K gilt:

f (x1 + (1 - x2)f(x1) + (1 - f(x2)

für alle 0 1;d.h.: wenn die Menge (Epigraph)

{(z,x) | z > f(x), x K} “oberhalb” der Funktion f konvex ist.


Konvexe Funktionen - Beispiel

Beispiel für eine konvexe Funktion: f(x) = x2


Konkave Funktionen

Definition Konkavität von Funktionen:

Eine Funktion f: K , welche eine konvexe Menge K in abbildet, heißt konkav, wenn g = -f eine konvexe Funktion ist.


Konkave Funktionen - Beispiel

Beispiel für eine konkave Funktion: f(x) = -x4


Konvexe und konkave Funktionen

Eine Funktion ist genau dann linear, wenn sie konvex und konkav ist.

Beispiel:

Satz: Die Summe konvexer Funktionen ist konvex.Satz: Ist f(x) eine auf K konvexe Funktion, dann ist auch f(x) für alle reellen 0 auf K konvex.

f x x 12

1

-2 -1 0 1

1


Konvexität von Optimierungsproblemen

Satz: Ist f(x) eine auf K konkave Funktion, die nur positive Werte annimmt, dann ist

auf K konvex.

Satz: Seien gi: n konvex. Dann ist

M = {X Rn gi(x) 0}

eine konvexe Menge

g xf x

( )( )

1


Konvexe OptimierungsproblemeDefinition Konvexität von Optimierungsproblemen:Ein Optimierungsproblem

max (min) f(x) u.d.N. gi(x) 0

x 0heißt konvex, wenn bei Maximierung (Minimierung) die Zielfunktion f konkav (konvex) und die Funktionen gi der Nebenbedingungen konvex sind.


Konvexe Optimierungsprobleme - Beispiel

Beispiel Maximierung einer konkaven Funktion über einen konvexen zulässigen Bereich:

Satz: Ein lokales Optimum eines konvexen Optimierungsproblems ist global.


Kuhn-Tucker-BedingungenVerallgemeinerung der klassischen Multiplikatorenmethode von Lagrange zur Bestimmung von Extremstellen unter Nebenbedingungen, wobei diese nicht nur Gleichungen, sondern auch Ungleichungen enthalten

Verallgemeinerte Lagrange-Funktion:

L (x1, ..., xn; u1, ..., um) = f(x1, ..., xn) - i1ui gi (x1, ..., xn)


Theorem von Kuhn/Tucker (1)Gegeben sei ein konvexes Optimierungs-problem

max f(x1, ..., xn)

u.d.N. gi(x1, ...., xn) 0 i = 1, ..., m

xj 0 j = 1, ..., n.

Die Funktionen f und gi, i = 1, ..., m, seien partiell nach allen xj differenzierbar.


Theorem von Kuhn/Tucker (2)Der Vektor (x1, ..., xn) ist genau dann eine optimale Lösung des konvexen Optimie-rungsproblems, wenn es einen Vektor (u1, ..., um) gibt, so daß die folgenden Bedingungen (Kuhn-Tucker-Bedingungen) erfüllt sind:

1 0 11 1 1. ( , , ) , , ,...,

Lx

fx

x x ugxx x j n

j jn ii

m i

jn

2 0 11 1 1. , , , , ,...,xLx

xfxx x u

gxx x j nj

jj

jn ii

m i

jn

3 0 1 0 1. ,..., ; ,...,x j n u i nj i

4 0 0 11 1. ( ,..., ) ; ( ) ( ,..., ) ,...,

Lu

g x x uLu

u g x x i mi

i n ii

i i n



München 1993, Hanser-Verlag, Kapitel 4 Seite 544-555



Quadratische Optimierung (1)max f(x) = cT x + xT D x

u.d.N. g(x) = A x - b x , x n

O.B.d.A.: Für die Elemente der Matrix D gilt:dkj = djk, d.h. D ist symmetrisch

Falls dkj djk, so sind die Elemente durch das arithmetisches Mittel (dkj + djk)/2 zu ersetzen.


Quadratische Optimierung (2)

Satz: Die quadratische Funktion

f(x) = cT x+ xT D xist konvex (konkav) genau dann, wenn die symmetrische Matrix D positiv (negativ) semidefinit ist.


Beispiel eines quadratischen Optimierungsproblems

Ein Monopolist bietet 2 Produkte in den Mengen x1 und x2 an. Seine beiden Preis-Absatz-Funktionen lauten:1. p1(x1) = 6 - x1/40 < x1 < 242. p2(x2) = 10 - x2 0 < x2 < 10.Gesucht wird das erlösmaximale Produktionsprogramm. Die Zielfunktion lautet dann:max E(x1, x2) = p1(x1) x1 + p2(x2) x2 Folgende Absatzbeschränkungen werden untersucht:A: x1 < 15 x2 < 7B: x1 < 10 x2 < 4C: x1 + x2 < 10


Beispiel eines quadratischen Optimierungsproblems - Graph

Date post:	06-Apr-2016
Category:	Documents
Upload:	vreni-heiler
View:	213 times
Download:	0 times

Prof. Dr. Dr. J. Hansohm Nichtlineare Optimierung Einführung Konvexe Optimierungsprobleme Spezielle...

Documents