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

A Polynomial Algorithm for a NP-hard toSolve Optimization ProblemDissertation der Fakultät für PhysikderLudwig-Maximilians-Universität Münchenvorgelegt vonStefan Eberleaus Kaufbeureneingreicht am 17. Oktober 20081. Gutachter: Prof. Dr. W. Richert2. Gutachter: Prof. Dr. A. SchenzleTag der mündlichen Prüfung: 29. Januar 2009AbstractSinceMarkowitzin1952describedane fficientandpracticalwayoffindingtheoptimal portfolio allocation in the normal distributed case, a lot of progressin several directions has been made. The main objective of this thesis isto replace the original risk measure of the Markowitz setting by a moresuitable one, Value-at-Risk. In adressing the optimal allocation problem ina slightly more general setting, thereby still allowing for a large number ofdi fferentassetclasses,ane fficientalgorithmisdevelopedforfindingtheexactsolution in the case of specially distributed losses. Applying this algorithmto even more general loss distributions results in a not necessarily exactmatching of the VaRoptimum. However, in this case, upper bounds fortheeuclideandistancebetweentheexactoptimumandtheoutputoftheproposedalgorithmaregiven. Aninvestigationoftheseupperboundsshows,thatingeneralthealgorithmresultsinquitegoodapproximationstotheVaRoptimum. Finally, an application of a stochastic branch & bound algorithmto the current problem is discussed.Contents1Introduction 12 Problem Statement and Conjecture 82.1 General Notations and Definitions................