A Polynomial Algorithm for a NP-hard to solve Optimization Problem

Eberle, Stefan (2009): A Polynomial Algorithm for a NP-hard to solve Optimization Problem. Dissertation, LMU München: Fakultät für Physik

Abstract

Since Markowitz in 1952 described an efficient and practical way of finding the 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 different asset classes, an efficient algorithm is developed for finding the exact 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 VaR optimum. However, in this case, upper bounds for the euclidean distance between the exact optimum and the output of the proposed algorithm are given. An investigation of these upper bounds shows, that in general the algorithm results in quite good approximations to the VaR optimum. Finally, an application of a stochastic branch & bound algorithm to the current problem is discussed.

• Dokumententyp: Dissertationen (Dissertation, LMU München)
• Keywords: Value at Risk Conditional Value at Risk Optimization
• Themengebiete: 500 Naturwissenschaften und Mathematik ; 500 Naturwissenschaften und Mathematik > 530 Physik
• Fakultäten: Fakultät für Physik
• Sprache der Hochschulschrift: Englisch
• Datum der mündlichen Prüfung: 29. Januar 2009
• 1. Bericht­erstatter:in: Richert, Walter