A polynomial algorithm for a NP-hard to solve optimization problem [Elektronische Ressource] / vorgelegt von Stefan Eberle

Stefan Eberle

Sujets

• Mathematics

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2009
• Nombre de lectures: 12
• Langue: English

Extrait

A Polynomial Algorithm for a NP-hard to
Solve Optimization Problem
Dissertation der Fakultät für Physik
der
Ludwig-Maximilians-Universität München
vorgelegt von
Stefan Eberle
aus Kaufbeuren
eingreicht am 17. Oktober 20081. Gutachter: Prof. Dr. W. Richert
2. Gutachter: Prof. Dr. A. Schenzle
Tag der mündlichen Prüfung: 29. Januar 2009Abstract
SinceMarkowitzin1952describedane fficientandpracticalwayoffindingthe
optimal portfolio allocation in the normal distributed case, a lot of progress
in several directions has been made. The main objective of this thesis is
to replace the original risk measure of the Markowitz setting by a more
suitable one, Value-at-Risk. In adressing the optimal allocation problem in
a slightly more general setting, thereby still allowing for a large number of
di fferentassetclasses,ane fficientalgorithmisdevelopedforfindingtheexact
solution in the case of specially distributed losses. Applying this algorithm
to even more general loss distributions results in a not necessarily exact
matching of the VaRoptimum. However, in this case, upper bounds for
theeuclideandistancebetweentheexactoptimumandtheoutputofthe
proposedalgorithmaregiven. Aninvestigationoftheseupperboundsshows,
thatingeneralthealgorithmresultsinquitegoodapproximationstotheVaR
optimum. Finally, an application of a stochastic branch & bound algorithm
to the current problem is discussed.Contents
1Introduction 1
2 Problem Statement and Conjecture 8
2.1 General Notations and Definitions................ 8
2.2FormulationoftheAlgorithm..................12
2.3ComplexityoftheVaR-OptimizationProblem.........14
2.4PropertiesofVaRandCVaR17
2.4.1 CoherentMeasuresofRisk................17
2.4.2 RelationsbetwenVaRandCVaR............18
2.4.3 SubadditivityofCVaR..................19
2.4.4 Di fferentiabilityofVaRandCVaR...........21
2.5 SomeCommentsonStable/G-and-HDistributedAssetReturns 24
2.5.1 Properties of Stable Distributed Asset Returns . . . . . 24
2.5.2 Generation of Stable Distributed Random Variables . . 29
2.5.3 VaR Computation in the α-stableCase.........30
2.5.4 CVaR Computation in the α-stableCase32
2.5.5 PropertiesoftheG-and-HDistribution.........34
i2.5.6 SubadditivityofVaR...................37
3 VaR and CVaR Optimization 41
3.1CVaROptimization........................41
3.1.1 LinearityofCVaROptimization.............41
3.1.2 Reduction of Dimensionality using Benders Decompo-
sition............................42
3.2 VaR Optimization for Certain Classes of Asset Returns . . . . 45
3.2.1 SphericalandElipticalDistributions..........45
3.2.2 Stable Distributions with Constant Skewness Parameter 48
3.2.3 StableDistributions...................50
A Polynomial Algorithm for Stable Distributed Asset
Returns.....................50
STNumerical Evaluations of Assumption A .......52
3.2.4 First Estimations for G-and-H distributed asset returns 57
3.3ApproximativeResultsfortheVaROptimum.........62
3.3.1 UsingG-and-HDistributionstoMatchReal-WorldOp-
timizationProblems...................62
Numericalevaluationsoftheconditionsfortheapprox-
imateapproach.................65
3.3.2 VaR-optimizationforgeneraldistributions.......73
Estimationsforarbitrarydistributions.........73
Error estimations using best linear and quadratic pre-
dictors......................74
3.3.3 An illustrative example..................77iii
4StochasticBranch&Bound 85
4.1GeneralMethod..........................85
4.1.1 TheAlgorithm......................86
4.2 Application toVaROptimization................88
4.3 An Analysis of the Algorithm’s E fficiency............94
5 Conclusion and Further Investigations 96
A Abbreviations and Notations 98
B Subadditivity of VaR for Stable Distributions 100
C Karush-Kuhn-Tucker Conditions 103Danksagung
An dieser Stelle möchte ich Herrn Prof. Dr. Richert ganz herzlich für
die Unterstützung bei meiner Dissertation danken. Ein weiterer Dank gilt
allen Freunden und Kollegen bei der Münchener Rück, welche meine Arbeit
durchanregendeDiskussionenunterstützten. DerfinanziellenUnterstützung
durch die Münchener Rück in Form eines Promotionsstipendiums sei eben-
falls gedankt.
ivZusammenfassung
Die vorliegende Dissertation beschäftigt sich mit der Lösung einer sehr all-
gemeinen Problemstellung, bei der für n gegebene Zufallsvariablen
X ,...,X ∈R1 n
diegewichtete”Mischung”
X(x):=x ·X +...+x ·X (0.1)1 1 n n
für x ,...,x ∈ R näher untersucht werden soll. Hierbei wird unterstellt,1 n
dass die Abhängigkeitsstruktur der Zufallsvariablen X ,...,X als bekannt1 n
angenommen werden kann und als explizite Szenarienvektoren⎛ ⎞
1Xi⎜ ⎟. j.X = ,X ∈R⎝ ⎠i . i
kXi
der Länge k vorliegen. In dieser SchreibweiseistdieAbhängigkeitsstruktur
j 1durch die Ausprägungen von X für i=1,...,n implizit gegeben.Weiteri
sollen die Gewichte x für i=1,...,n unter Einhaltung einer festgelegten er-i
warteten AusprägungE(X(x)) so gewählt werden, dass X(x) eine möglichst
geringe Varianz aufweist.
Darüber hinaus wurde der Fall untersucht, bei welchem einseitige positive
AbweichungenvomErwartungswertkeinerBeschränkungunterliegen,während
das Unterschreiten eines vorgegebenen Schwellenwertes als Abweichung von
der Erwartung mit möglichst hoher Konfidenz ausgeschlossen werden kann.
1 Durch die Verwendung einer geeigneten Anzahl an Szenarien k können über diesen
Ansatz auch als stetig vorausgesetzte Zufallsvariable hinreichend approximiert werden.
v
eeeevi
Mit anderen Worten soll die optimierte Mischung der X für zulässige Wertei
x bestimmtwerden,sodasszugegebenerKonfidenzdasUnterschreiteneinesi
Schwellenwertes durch die Zufallsvariable X(x) ausgeschlossen werden kann.
AuchwennderobenbeschriebeneallgemeineFallaneinemkonkretenBeispiel
erarbeitet wird, so ist hervorzuheben, dass an keiner Stelle der Analysen die
Allgemeinheit der Aussage beschränkende Annahmen einfließen. Wird also
das vorliegende Problem an einem konkreten Praxisbeispiel erläutert, so di-
ent dies einzig und alleinder Anschaulichkeit. Unbenommenhiervonhandelt
es sichbeidemvorgestelltenAlgorithmus umeine sehrallgemeine”Quantils-
Optimierung” einer beliebigen Mischung von Zufallsvariablen, wobei der Er-
wartungswert der untersuchten Verteilung als bekannt vorausgesetzt wer-
den darf. Bei dem beschriebenen Lösungsalgorithmus handelt es sich um
eine Vorgehensweise, welche ohne weiteren Anpassungsbedarf auf allgemeine
mathematisch-statistische Problemstellungen angewendet werden kann.
Wie bereits erwähnt wurde, wird die oben beschriebene allgemeine Problem-
stellung anhand einer konkreten Problemstellung eingehend analysiert. In
der Tat beschäftigen wir uns im vorliegenden Fall mit einer Erweiterung des
klassischen Portfoliooptimierungsproblems, welches erstmals von Markowitz
in seiner wegweisenden Arbeit [34] im Detail untersucht wurde. Die bere-
its beschriebenen Zufallsvariablen X werden in diesem Zusammenhang alsi
Verlustverteilungen einzelner Assetklassen interpretiert und in der Markow-
itzschen Analyse als normalverteilt unterstellt. Basierend auf dieser An-
nahme wird das optimale Portfolio als eine Positionierung zwischen Risiko
und erwartetem Verlust formuliert. Über den ursprünglich von Markowitz
gewähltenAnsatzhinauswollenwirunsjedochnichtaufdenFallnormalverteil-
ter Zufallsvariablen beschränken, sondern die Verlustverteilungen, gegeben
als die Zufallsvariablen X,i=1,...,n mit größtmöglichem Freiheitsgradi
nwählbarerlauben. Interpretierenwirx ∈R alsPortfolioallokationdernver-
schiedenen Assetklassen, so ergibt sich die entsprechende Verlustverteilung
X(x) mittels Gleichung 0.1.
EinesehrverbreiteteVorgehensweisezurRisikomessungbeinichtnormalverteil-
ten Verlustverteilungen stellt die Verwendung des Value-at-Risks zum Kon-
fidenzniveau η (VaR oder kurzVaR) dar. Dieses Risikomaß mißt den kle-η
insten zu erwartenden Verlust, so dass die Wahrscheinlichkeit eines denVaR
übersteigenden Verlust nicht höher als (1 − η)·100% ist. Obwohl dieses sehr
bedeutende Risikomaß weite Verbreitung gefunden hat, fehlen ihm einige
sehr wichtige Eigenschaften, welche Risikomaße im Allgemeinen aufweisen
sollten (vgl. [4]). Neben der Tatsache, dass es sich beimVaRum ein im
Allgemeinen äußerst instabiles und in der Optimierung als komplex zu klas-vii
sifizierendes Risikomaß handelt, wird die Ausprägung der den VaRüber-
steigenden Verluste nicht berücksichtigt. In diesem Sinne wird bei gleicher
Wahrscheinlichkeit des den VaRübersteigenden Verlusts die Situation, in
welcher eine Konzentration von Verlusten den VaR deutlich übersteigt nicht
unterschieden von einer (oftmals favorisierten) Verlustverteilung, bei welcher
dieVerlustegeglättetübereinweitesSpektrumunterschiedlicherVerlustaus-
prägungen auftreten.
Es gibt eine Vielzahl an Bemühungen, Optimierungsprobleme der vorliegen-
den Art e ffizientzulösen. EinGrunddafür, dasses nochimmerkeinenAlgo-
rithmus zur e ffizienten Lösung großdimensionierter Problemstellungen gibt,
ist hauptsächli