Adaptive Approximationsverfahren fürmultikriterielle Optimierungsprobleme

Kathrin Klamroth

Institut für Angewandte Mathematik

Universität Erlangen-Nürnberg

B. Schandl & M.M. WiecekClemson University, USA

J. TindUniversität Kopenhagen

Gliederung

• Multikriterielle Optimierung– Problemformulierung und Notation– Ansatz: Nutzenfunktionen

• Approximationsverfahren– Approximation von Innen– Approximation von Außen– Nichtkonvexe und diskrete Probleme

• Anwendungsbeispiele– Engineering Design – Capital Budgeting– Portfolio Optimierung

Multikriterielle Optimierung

Capital Budgeting Problem

Gegeben: - Projektanträge für die Einführung neuer Technologien

- Budget an Haushaltsmitteln

Gesucht: - Auswahl an Projekten

so dass- das Budget nicht überschritten wird

- der Netto Barwert der Investition maximiert wird

- der duale Nutzen maximiert wird

Projektpartner: ONR

Modellierung als bikriterielles Rucksackproblem

max i=1 c1ixi

max i=1 c2ixi

s.t. i=1 aixi b xi {0,1}, i = 1,...,m

m

m

m

c1i NPV von Projekt i, i=1,...,mc2i JA/DU von Projekt i, i=1,...,mai Gesamtkosten von Projekt i, i=1,...,mb Budget

Multikriterielle Optimierung

vmin f(x) = [f1(x),...,fn(x)]T

s.t. x X

X m Lösungsraumf = [f1,...,fn]T n unvereinbare ZielfunktionenY = f(X) n Entscheidungsraum, Zielfunktionsraum

Effiziente (Pareto optimale) Lösungen

xe X heißt effizient, wenn keine Lösung x X mit f(x) f(xe)existiert, d.h.

i{1,...,n} fi(x) fi(xe)

i{1,...,n} s.t. fi(x) < fi(xe)

Effiziente Lösungen: E X

Nichtdominierte Menge: N = f(E) Y

Eigentlich nichtdominierte Punkte

f1(x)

f2(x)

y* Ye heißt eigentlich nichtdominiert, wenn eine Konstante M > 0 existiert, so dass für alle i = 1,...,n und y Y mit yi < yi* ein Index j i existiert, für den yj > yj* und

yi - yi* yj* - yj

______ M .

y* nicht eigentlich nichtdominiert

[Geoffrion 68]

Lösungsansatz: Nutzenfunktionen

Jedem Lösungsvektor f(x) wird ein Nutzen u(f(x)) zugeordnet, indem z.B. die gewichtete Summe der einzelnen Kriterien gebildet wird:

min wi fi(x)

s.t. x X

wi = 1, wi 0, i=1,...,n

i=1

n

i=1

n

f2(x)

f1(x)

y*

Schwierigkeiten:

• Bestimmung der Gewichte wi bzw. geeigneter Nutzenfunktionen u(f(x))

• Es werden i.A. nur extremale nichtdominierte Lösungen gefunden

• Trade-off Informationen gehen verloren

x

x

x

nicht extremale Lösungf2(x)

f1(x)

Extremale / nicht extremale Lösungenbeim bikriteriellen Rucksackproblem

[Visée, Teghem, Pirlot und Ulungu 98]

Approximationsverfahren

Approximationsproblem

Gegeben: - Menge nichtdominierter Lösungen N

- Gauge (oder andere Abstandsfunktion)

Gesucht: Approximierendes (eingeschriebenes) Polyeder Pk mit k nichtdominiertenExtrempunkten

so dass (N, (Pk)) minimiert wird.y0 y0

N N

Ausgewählte Beiträge• Konvexe bikriterielle Probleme:

– Cohon 78, Polišč– Fruhwirth et al. 89, Yang & Goh 97

• Nichtkonvexe bikriterielle Probleme:– Payne 93; Li et al. 98, Li 99– Chen et al. 99, Zhang et al. 99– Klamroth et.al. 00, 01a

• Multikriterielle Probleme:– Polak 76, Helbig 91, Jahn & Merkel 92– Kaliszewski 94, Kostreva et al. 95– Sobol´ & Levitan 97, Benson & Sayin 97, Das & Dennis 00– Fonseca und Fleming 95, Czyzak und Jaszkiewicz 98,

Ulungu et al. 99– Fliege 01, 02– Klamroth et.al. 01b, 02a, 02b, Klamroth et.al. 03

uk 79

Approximation von Innen

0

d1y1

y*

Idee: Die Approximation selbst definiert eine polyedrische Abstandsfunktion , mit Hilfe derer die nächste nichtdominierte Lösung bestimmt werden kann

y0 = 0 Referenzpunkt (z.B. Nadir Punkt)d1,...,ds Normalen der Facetten von B n

Annahme: B n = { y 0 : diy 1, i=1,...,s } Y

max (y)

s.t. y Y n d2y1

Disjunctive Programming Formulierung

max

s.t. i=1 ( di yi , yiY )

s

Spezialfall: Y = { Cx : Ax b, x 0, x m }:

max i=1 i

s.t. i - di Cxi 0 i=1,...,s A xi pi b i=1,...,si=1 pi = 1pi 0, xi 0 i=1,...,si i=1,...,s

s

s

max - di Cx 0

s.t. A x b x 0

s i=1 ( )

[Balas 85]

Dekomposition bzgl. Fundamentalkegeln

0

vi+1y*

Idee: Zerlegung des Problems in einfache Teilprobleme, formuliert auf den Fundamentalkegeln von B

C1,...,Cs Fundamentalkegel von B n

v1,...,vt Fundamentalvektoren von B n

Ij Indexmenge der Fundamentalvektoren, die Cj erzeugen, j{1,…,s}

vi

max i

s.t. i vi = y

i 0 iIj

y Y

iIj

iIj

Konvexe Probleme

Satz: Sei Y strikt n - konvex und sei Cj ein Fundamentalkegel der Einheitskugel des approximierenden Gauges . Dann ist die Optimallösung von

eigentlich nichtdominiert.

max i

s.t. i vi = y

i 0 iIj

y Y

iIj

iIj

Innerer Approximationsalgorithmus

y0=0

y2

y1

y3

y4

Eigenschaften des Verfahrens

• Komplexität: O([ k log(k) + k(n+1)2 ] + kT) ;Beneath-Beyond Algorithmus: O(k log(k) + k(n+1)2)

• Die Approximation wird immer dort verbessert, wo der Fehler am größten ist

• Das Verfahren ist skaleninvariant

• Die Approximation liefert einen problem-bezogenen Bewertungsmaßstab

• Der Approximationsfehler ist in jeder Iteration bekannt

Skaleninvarianz

y0 y0

y* y*

Skalierung 1 Skalierung 2

Problembezogener Bewertungsmaßstab

y0

y2

y1

Quadratische Konvergenz für bikriterielle Probleme

Satz: Nach k Iterationen beträgt der Approximationsfehler höchstens

r: Radius einer in B eingeschriebenen Kugel

D: Umfang von Y

D 2 r k2

______|(y*) - 1| = O(1/ k2)

Approximation von Außen

0v1

y*

v2

Idee: Benutze geometrische Dualität bzgl. der Einheitskugel

y0 = 0 Referenzpunktv1,...,vt Fundamentalvektoren von B n

Annahme: (Yn) { y 0 : y i=1ivi, i=1i = 1, 0 } t t

max s.t. vi = yi i{1,…,t}

0 yi Y v3

Dekomposition bzgl. Fundamentalrichtungen

0

vj

y*

Idee: Zerlegung des Problems in einfache Teilprobleme, formuliert bzgl. der Fundamentalvektoren von B

vj {v1,...,vt }: Fundamentalvektor von B n

max s.t. vj = y

0, yY

Äußerer Approximationsalgorithmus

y0=0 y1

y2

y3

y4

Nichtkonvexe und diskrete Probleme

Nc

N Y

Gegeben: Y n, n - abgeschlossen, int Y ,0 Y = Y + n

Notation: Nc := { y Y : y´Y s.t. y´ y }

Approximation von Innen

0d1

y*

d2

d3

v1

v2

v3

max (v) di + i(vi -di ) = v

s.t. i 0, v yi yiY

s

Idee: Benutze Ordnungskegel um eine stückweise lineare Approximation zu erzeugen

y0 = 0 Referenzpunkt d1,...,ds n

B := clos ( n \ (di + n ) )

Annahme: { vn : v = i=1 idi, 0 } = n

s i=1,…,s

i=1( )

Dekomposition bzgl. Tchebycheff-Boxen

Idee: Formulierung bzgl. lokaler Tchebycheff-Boxen ermöglicht die Zerlegung des Problems in einfache Teilprobleme

(dj,vj): Lokaler Nadir- und Utopia Punkt

Lemma: (v*) = 1 + *

max

s.t. i=1

s di + [(vi -di ) ((vi)-1)] yi

yiY

( )

Innerer Approximationsalgorithmus

y0=0

y1

y2

y3

Anwendungsbeispiele

Approximations-ablauf

EngineeringDesign

Capital Budgeting

Portfolio Optimierung

y0

Evaluation von Flugzeug-Technologien

min f1(x)min - f2(x)

s.t. g(x) 150-1 xi 1, i=1,...,9

Name Abk. Beschr. Ziel

f1 LCC Life cycle cost min

f2 PS Leistung max

g VAPP Landegeschwindigkeit 150

x1,...,x9 : k-Faktoren

Projektpartner: Georgia Institute of Technology

Zielfunktionenf1(x) = 0.7781145 - 0.000243x1 - 0.000129x2 - 0.008703x3 - 0.018481x4

- 0.001338x5 - 0.001332x6 + 0.002002x7 + 0.0407985x8 + 0.0635737x9 + 0.0000195x1

2 + 0.0000304x1x2 - 0.00008x22 - 0.000016x1x3

+ 0.0000031x2x3 + 0.0002275x32 - 0.000025x1x4 + 0.0000011x2x4

+ 0.0004497x3x4 + 0.0003035x42 + 0.0000063x1x5 + 0.0000144x2x5

+ 0.0000508x3x5 + 0.0000748x4x5 - 0.000075x52 + 0.0000035x1x6

- 0.0000128x2x6 + 0.000037x3x6 + 0.0000583x4x6 + 0.0000056x5x6 - 0.000077x6

2 - 0.000027x3x7 - 0.00005x4x7 - 0.000003x6x7 + 0.0001197x72

- 0.000017x1x8 + 0.0002761x3x8 - 0.000621x4x8 - 0.000014x7x8 + 0.0016644x8

2 - 0.000012x1x9 - 0.00139x3x9 - 0.001816x4x9 - 0.00018x5x9 - 0.000179x6x9 - 0.000014x7x9 + 0.0002337x8x9 + 0.0025803x9

2

f2(x) = 718.25546 - 13.28308x1 - 1.69x2 - 18.79769x3 - 23.95615x4 - 2.422308x5

- 2.406154x6 + 0.3348272x12 + 0.121875x1x2 - 0.115173x2

2 + 0.24375x1x3

- 0.046875x2x3 + 0.5848272x32 + 0.36875x1x4 + 0.015625x2x4 + 0.6875x3x4

+ 0.6848272x42 + 0.0625x1x5 + 0.009375x2x5 + 0.05625x3x5 + 0.10625x4x5

- 0.115173x52 + 0.046875x1x6 + 0.0125x2x6 + 0.034375x3x6 + 0.071875x4x6

+ 0.003125x5x6 - 0.165173x62

Nebenbedingung

g(x) = 151.47993 + 0.4261538x1 + 0.2346154x2 + 1.9292308x3 + 2.4615385x4

+ 0.2530769x5 + 0.25x6 - 0.078675x12 - 0.034375x1x2 + 0.0713251x2

2

+ 0.03125x1x3 + 0.0125x2x3 - 0.078675x32 + 0.0125x1x4 - 0.01875x2x4

- 0.009375x3x4 - 0.078675x42 + 0.003125x1x5 - 0.003125x2x5

+ 0.00625x3x5 - 0.00625x4x5 + 0.0713251x52 - 0.00625x2x6

+ 0.009375x3x6 - 0.003125x4x6 + 0.0713251x62

Approximation (20 Iterationen)

y0

Zooming

y0

Capital Budgeting Problem

Gegeben: - Projektanträge für die Einführung neuer Technologien

- Budget an Haushaltsmitteln

Gesucht: - Auswahl an Projekten

so dass- das Budget nicht überschritten wird

- der Netto Barwert der Investition maximiert wird

- der duale Nutzen maximiert wird

Projektpartner: ONR

Projektdaten

Project name Total cost NPV JA/DU

ACEM 115 8617 90AESA Radar 90 684 40Row Bulb 34 199 45Common CM 54 18 50CVX Coatings 95 29 90CVX Deck 177 7 40CVX Nano 68 75 90CVX Radar 135 366 10Deck Module 85 33 45EA Filter 10 7 50FDM 230 163 40Green Rounds 90 89 30HMI Tech 230 1943 90ICAS 110 1666 70MMM Receiver 38 613 70PTC Cooling 75 6 0Quiet Electro 132 117 10Tactical WCS 210 56 80TP 52 49 50Urethane 36 44 25UUV Batt 49 8 70Vertical GN 110 179 80Water Mitigator 14 54 80Waveguide 27 87 40

Modellierung als bikriterielles Rucksackproblem

max i=1 c1ixi

max i=1 c2ixi

s.t. i=1 aixi b xi {0,1}, i = 1,...,24

24

24

24

c1i NPV von Projekt i (in Millionen US $), i=1,...,24c2i JA/DU von Projekt i, i=1,...,24ai Gesamtkosten von Projekt i (über 3 Jahre,

in 100.000 US $), i=1,...,24b Budget (in 100.000 US $)

Approximation (20 Iterationen)

y0

Portfolio Optimierung

• Gegeben:– Aktienfonds in

verschiedenen Marktsegmenten

– Zu investierendes Kapital

• Gesucht:Portfolio von Aktienfonds,so dass– das vorhandene Kapital

investiert wird,– der zu erwartende Gewinn

maximiert wird,– das Risiko minimiert wird.

Projektpartner: Standard & Poors (Hochheim, Taunus)

Projektdaten

Aktienfonds3-Jahres

PerformanceVolatilität

Invesco GT Japan Enterprise C 333.20 39.01Mercury ST Opps A 265.15 38.47HSBC GIF Indian Equity 336.49 37.27Flemming FF Japanse 105.46 29.17Flemming FF Pacific 176.94 29.28Pacific Growth Trust 131.27 26.32Uni Japan 81.60 24.75Volksbank Pacific Invest 61.99 42.42Lazard Japan Yen (Dublin) 65.88 22.84DWS Telemedia 266.23 20.77Deutscher Vermögensbildungs I 196.29 19.95Baring Eastern -13.40 10.35Intervest 116.50 18.39SMH International UBS Fonds 151.65 21.27Interglobal 144.29 18.46MMWI AMERAK Fonds 182.03 20.45HSBC GIF UK Equity 119.23 16.12Allianz Aktien International 136.93 18.84Anglo Irish Global Equity 175.30 21.26HWG Fonds 117.00 14.69M.Lynch Global Allocation 73.78 15.39DBIM Emerging Markets Bond 31.16 15.76GF 40 130.21 17.41Ring International DWS 93.05 12.36Oberbank Stock Mix (exATS) 112.26 17.52State Street Actions Framce C 138.70 22.07Gartmore CSF JPY Bond 33.46 13.56Henderson HF Sterling Bond 88.51 9.78Zürich Invest Global 66.69 10.45DBIM Csh USD 43.35 8.76OIM Vermögensaufbau Fonds 51.01 2.37AIB Grofounds Sterling Mgd Curr 37.64 7.76BTGAF Global Bond funds 32.50 7.86DBIM Euro Reserve 14.93 1.27Metzler Geldmarkt 8.94 0.85HIS Renten Deutschland 17.31 2.77BL Rent DWS 16.76 2.90CS Bond funds (Lux) Euro A 24.55 3.77BBV Fonds Union 15.83 3.34Oppenheim Priva Rent M 13.01 2.38

Markowitz Kovarianz Modell

• Eine lineare und eine nichtlineare Zielfunktion• Eine lineare Nebenbedingung

max Gewinn = r1 x1+ ··· + r40 x40

min Risiko = i=1 j=1 xi xj ij

s.t. x1+ ··· + x40 = 1 xi 0 i = 1,...,40

40 40

_____________

Approximation (20 Iterationen)

y0

Zusammenfassung

• Norm-basierte Approximationsverfahren sind– skaleninvariant – unabhängig, d.h., es werden keine Gewichte,

Nutzenfunktionen usw. benötigt– verfeinern die Approximation, wo es am Nötigsten ist

• Trade-off Information ist für die gesamteAlternativenmenge verfügbar

• Effizienz:– Dominiert durch den Beneath-Beyond Algorithmus– Quadratische Konvergenz für bikriterielle Probleme

• Zooming ermöglicht ein mehrstufiges Vorgehenbei der Bestimmung einer „besten“ Lösung

Geplante Forschungsarbeiten

• Approximationsverfahren:– Übertragung der Approximationsverfahren auf konvexe

und nichtkonvexe Mengen in der Ebene und im n

– Effiziente Implementierung in höheren Dimensionen

• Generierung aller nichtdominierter Lösungen:– Dynamische Programmierung [KlaWie00] – Klassische Methoden (e-Constraint, Tchebycheff,...)

• Weitere Lösungsansätze:– Metaheuristiken [EhrKlaSchw]– Nutzenfunktionen, Abschätzungen und Dualität [KlaTiZu]

Vielen Dank für Ihre Aufmerksamkeit !

http://www2.am.uni-erlangen.de/~klamroth/