Adaptive Approximationsverfahren für
multikriterielle Optimierungsprobleme
Kathrin Klamroth
Institut für Angewandte Mathematik
Universität Erlangen-Nürnberg
B. Schandl & M.M. Wiecek
Clemson University, USA
J. Tind
Universitä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:
so dass
- Auswahl an Projekten
- das Budget nicht überschritten wird
- der Netto Barwert der Investition
maximiert wird
- der duale Nutzen maximiert wird
Projektpartner: ONR
Modellierung als
bikriterielles Rucksackproblem
max
max
s.t.
c1i
c2i
ai
b
m
i=1
m
i=1
m
i=1
c1ixi
c2ixi
aixi  b
xi  {0,1}, i = 1,...,m
NPV von Projekt i, i=1,...,m
JA/DU von Projekt i, i=1,...,m
Gesamtkosten von Projekt i, i=1,...,m
Budget
Multikriterielle Optimierung
vmin f(x) = [f1(x),...,fn(x)]T
s.t. x  X
X  m
Lösungsraum
f = [f1,...,fn]T
n unvereinbare Zielfunktionen
Y = 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:
Nichtdominierte Menge:
EX
N = f(E)  Y
Eigentlich nichtdominierte Punkte
[Geoffrion 68]
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*
______
 M.
yj* - yj
f2(x)
y* nicht eigentlich
nichtdominiert
f1(x)
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:
n
min  wi fi(x)
f2(x)
i=1
s.t.
x X
n
y*
 wi = 1, wi  0, i=1,...,n
i=1
f1(x)
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
f2(x)
nicht extremale Lösung
x
x
x
f1(x)
Extremale / nicht extremale Lösungen
beim 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 nichtdominierten
Extrempunkten
(N,(Pk)) minimiert wird.
so dass
y0
N
y0
N
Ausgewählte Beiträge
• Konvexe bikriterielle Probleme:
– Cohon 78, Polišč uk 79
– 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
Approximation von Innen
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
0
max
(y)
s.t.
y  Y  n
d1y1
d2y1
y*
Disjunctive Programming Formulierung
[Balas 85]
max

s.t.

s
i=1
( di yi  , yiY )

Spezialfall: Y = { Cx : Ax  b, x  0, x m }:
max
max 

i=1
s
s.t.
(

-
di Cx
0
A x  b
x  0
)
s.t.

s
i=1
i
i - di Cxi  0  i=1,...,s
A xi  pi b
 i=1,...,s
s
i=1 pi = 1
pi  0, xi  0  i=1,...,s
i  
 i=1,...,s
Dekomposition bzgl. Fundamentalkegeln
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}
max
s.t.
0
 i
iIj
i =y


v
i
iI
j
i  0
y Y
 iIj
vi
y*
vi+1
Konvexe Probleme
Satz: Sei Y strikt n - konvex und sei Cj ein
Fundamentalkegel der Einheitskugel des
approximierenden Gauges . Dann ist die
Optimallösung von
max
s.t.
 i
iIj
i =y


v
i
iI
j
i  0
y Y
eigentlich nichtdominiert.
 iIj
Innerer Approximationsalgorithmus
y0=0
y1
y2
y4
y3
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 problembezogenen Bewertungsmaßstab
• Der Approximationsfehler ist in jeder Iteration
bekannt
Skaleninvarianz
y0
y*
Skalierung 1
y0
y*
Skalierung 2
Problembezogener Bewertungsmaßstab
y0
y1
y2
Quadratische Konvergenz
für bikriterielle Probleme
Satz: Nach k Iterationen beträgt der
Approximationsfehler höchstens
|(y*) - 1| 
r:
D:
D
______
2)
=
O(1/
k
2 r k2
Radius einer in B eingeschriebenen Kugel
Umfang von Y
Approximation von Außen
Idee:
Benutze geometrische Dualität
bzgl. der Einheitskugel
y0 = 0 Referenzpunkt
v1,...,vt Fundamentalvektoren von B n
t
t
Annahme: (Yn)  { y 
 0 : y
 i=1ivi, i=1i = 1,   0 }
v1
max

s.t.
 vi = yi
0
yi  Y
0
 i{1,…,t}
y*
v2
v3
Dekomposition bzgl. Fundamentalrichtungen
Idee:
Zerlegung des Problems in einfache Teilprobleme,
formuliert bzgl. der Fundamentalvektoren von B
vj  {v1,...,vt }: Fundamentalvektor von B n
0
max

s.t.
 vj = y
  0, yY
y*
vj
Äußerer Approximationsalgorithmus
y0=0
y1
y3
y2
y4
Nichtkonvexe und diskrete Probleme
Gegeben:
Notation:
Y  n, n - abgeschlossen, intY   ,
0 Y = Y + n
Nc := { y Y :  y´Y s.t. y´  y }
N
Y
Nc
Approximation von Innen
Idee:
Benutze Ordnungskegel um eine stückweise lineare
Approximation zu erzeugen
y0 = 0 Referenzpunkt
d1,...,ds  n
B := clos ( n \
Annahme: {
max
(v)
i=1
s
s.t.
(

(di +n ) )
i=1,…,s
vn
: v=
s
i=1 idi,
di + i(vi -di ) = v
i  0, v  yi
yiY
 0 } = n
 
d1
v1
)
v2
0
d2
y*
d3
v3
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
max
s.t.

s
i=1
di + [(vi -di )  ((vi)-1)]  yi
(
Lemma: (v*) = 1 + *
yiY
)
Innerer Approximationsalgorithmus
y0=0
y1
y3
y2
Anwendungsbeispiele
Approximationsablauf
Capital
Budgeting
Engineering
Design
Portfolio
Optimierung
y0
Evaluation von Flugzeug-Technologien
Name
Abk.
f1
LCC
f2
PS
g
VAPP
x1,...,x9 :
Beschr.
Ziel
Life cycle cost
Leistung
Landegeschwindigkeit
k-Faktoren
min
max
 150
min
min
f1(x)
- f2(x)
s.t.
g(x)  150
-1  xi  1, i=1,...,9
Projektpartner: Georgia Institute of Technology
Zielfunktionen
f1(x) = 0.7781145 - 0.000243x1 - 0.000129x2 - 0.008703x3 - 0.018481x4
- 0.001338x5 - 0.001332x6 + 0.002002x7 + 0.0407985x8 + 0.0635737x9
+ 0.0000195x12 + 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.000077x62 - 0.000027x3x7 - 0.00005x4x7 - 0.000003x6x7 + 0.0001197x72
- 0.000017x1x8 + 0.0002761x3x8 - 0.000621x4x8 - 0.000014x7x8
+ 0.0016644x82 - 0.000012x1x9 - 0.00139x3x9 - 0.001816x4x9 - 0.00018x5x9
- 0.000179x6x9 - 0.000014x7x9 + 0.0002337x8x9 + 0.0025803x92
f2(x) = 718.25546 - 13.28308x1 - 1.69x2 - 18.79769x3 - 23.95615x4 - 2.422308x5
- 2.406154x6 + 0.3348272x12 + 0.121875x1x2 - 0.115173x22 + 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.0713251x22
+ 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:
so dass
- Auswahl an Projekten
- 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
AESA Radar
Row Bulb
Common CM
CVX Coatings
CVX Deck
CVX Nano
CVX Radar
Deck Module
EA Filter
FDM
Green Rounds
HMI Tech
ICAS
MMM Receiver
PTC Cooling
Quiet Electro
Tactical WCS
TP
Urethane
UUV Batt
Vertical GN
Water Mitigator
Waveguide
115
90
34
54
95
177
68
135
85
10
230
90
230
110
38
75
132
210
52
36
49
110
14
27
8617
684
199
18
29
7
75
366
33
7
163
89
1943
1666
613
6
117
56
49
44
8
179
54
87
90
40
45
50
90
40
90
10
45
50
40
30
90
70
70
0
10
80
50
25
70
80
80
40
Modellierung als
bikriterielles Rucksackproblem
max
max
s.t.
c1i
c2i
ai
b
24
i=1
24
i=1
24
i=1
c1ixi
c2ixi
aixi  b
xi  {0,1}, i = 1,...,24
NPV von Projekt i (in Millionen US $), i=1,...,24
JA/DU von Projekt i, i=1,...,24
Gesamtkosten von Projekt i (über 3 Jahre,
in 100.000 US $), i=1,...,24
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
Aktienfonds
Invesco GT Japan Enterprise C
Mercury ST Opps A
HSBC GIF Indian Equity
Flemming FF Japanse
Flemming FF Pacific
Pacific Growth Trust
Uni Japan
Volksbank Pacific Invest
Lazard Japan Yen (Dublin)
DWS Telemedia
Deutscher Vermögensbildungs I
Baring Eastern
Intervest
SMH International UBS Fonds
Interglobal
MMWI AMERAK Fonds
HSBC GIF UK Equity
Allianz Aktien International
Anglo Irish Global Equity
HWG Fonds
M.Lynch Global Allocation
DBIM Emerging Markets Bond
GF 40
Ring International DWS
Oberbank Stock Mix (exATS)
State Street Actions Framce C
Gartmore CSF JPY Bond
Henderson HF Sterling Bond
Zürich Invest Global
DBIM Csh USD
OIM Vermögensaufbau Fonds
AIB Grofounds Sterling Mgd Curr
BTGAF Global Bond funds
DBIM Euro Reserve
Metzler Geldmarkt
HIS Renten Deutschland
BL Rent DWS
CS Bond funds (Lux) Euro A
BBV Fonds Union
Oppenheim Priva Rent M
3-Jahres
Performance
Volatilität
333.20
265.15
336.49
105.46
176.94
131.27
81.60
61.99
65.88
266.23
196.29
-13.40
116.50
151.65
144.29
182.03
119.23
136.93
175.30
117.00
73.78
31.16
130.21
93.05
112.26
138.70
33.46
88.51
66.69
43.35
51.01
37.64
32.50
14.93
8.94
17.31
16.76
24.55
15.83
13.01
39.01
38.47
37.27
29.17
29.28
26.32
24.75
42.42
22.84
20.77
19.95
10.35
18.39
21.27
18.46
20.45
16.12
18.84
21.26
14.69
15.39
15.76
17.41
12.36
17.52
22.07
13.56
9.78
10.45
8.76
2.37
7.76
7.86
1.27
0.85
2.77
2.90
3.77
3.34
2.38
Markowitz Kovarianz Modell
max Gewinn = r1 x1+ ··· + r40 x40
_____________
40
40
min Risiko =  i=1
j=1
xi xj ij
s.t.
x1+ ··· + x40 = 1
xi  0
 i = 1,...,40
• Eine lineare und eine nichtlineare Zielfunktion
• Eine lineare Nebenbedingung
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 gesamte
Alternativenmenge verfügbar
• Effizienz:
– Dominiert durch den Beneath-Beyond Algorithmus
– Quadratische Konvergenz für bikriterielle Probleme
• Zooming ermöglicht ein mehrstufiges Vorgehen
bei 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/

Adaptive Approximationsverfahren für multikriterielle