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: Faculty of Physics

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.

• Item Type: Theses (Dissertation, LMU Munich)
• Keywords: Value at Risk Conditional Value at Risk Optimization
• Subjects: 500 Natural sciences and mathematics; 500 Natural sciences and mathematics > 530 Physics
• Faculties: Faculty of Physics
• Language: English
• Date of oral examination: 29. January 2009
• 1. Referee: Richert, Walter
• Signature of the printed copy: 0001/UMC 17713