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

Prof. Dr. Dr. J. Hansohm

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

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

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

x

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

Literatur: Neumann/Morlock: Operations Research

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

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

Prof. Dr. Dr. J. Hansohm

Ü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)

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

Einfache Nichtlineare Optimierung - Beispiel

(lokales) Maximum

lokales Minimum

lokales Maximum

Sattelpunkt

x

f(x)

eigentliches Maximum

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

Nichtlineare unrestringierte Optimierung - Beispiel (2)

Prof. Dr. Dr. J. Hansohm

Literatur: Neumann/Morlock: Operations Research

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

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

Konvexe und Nichtkonvexe Menge - Beispiele

Beispiele für konvexe und nicht-konvexe Mengen

Satz: Der Durchschnitt zweier konvexer Mengen ist konvex.

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

Konvexe Funktionen - Beispiel

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

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

Konkave Funktionen - Beispiel

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

Konvexe Optimierungsprobleme - Beispiel

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

Satz: Ein lokales Optimum eines konvexen Optimierungsproblems ist global.

Prof. Dr. Dr. J. Hansohm

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)

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

Literatur: Neumann/Morlock: Operations Research

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

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

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

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.

Prof. Dr. Dr. J. Hansohm

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

Prof. Dr. Dr. J. Hansohm

Beispiel eines quadratischen Optimierungsproblems - Graph