Dynamic-programming approaches to single-and multi-stage stochastic knapsack problems for portfolio optimization
Khoo, Wai Gea
Wood, R. Kevin
MetadataShow full item record
This thesis proposes new methods, based on dynamic programming, for solving certain single-stage and multi-stage integer stochastic knapsack problems. These problems model stochastic portfolio optimization problems (SPOPs) which assume deterministic unit weight, and normally distributed unit return with known mean and variance for each item type. Given an initial wealth, the objective is to select a portfolio that maximizes the probability of achieving or exceeding a specified final return threshold; the multi-stage problem allows revisions of the portfolio at regular time intervals. An exact method is developed to solve a single-stage SPOP with independence of returns among item types. For a problem from the literature with 11 item types, this method obtains an optimal solution in a fraction of a second on a laptop computer. An approximation method, based on discretization of possible wealth values, is developed to solve a multi-stage SPOP with inter- and intra-stage independence of returns among item types. Running on a desktop computer, this approximation method solves a 3-stage problem with 6 item types in under 12 minutes. With finer discretization in a 3-stage problem with 8 item types, the solution time is about 46 minutes.
Showing items related by title, author, creator and subject.
Kujawski, Edouard; Miller, Gregory A. (2007);This paper presents a realistic and practical approach to quantitatively assess the risk-reduction capabilities of military counterterrorism systems in terms of damage cost and casualty figures. The comparison of ...
Peterson, Todd (Monterey, CA; Naval Postgraduate School, 2018-12);This research evaluated the effectiveness of the MRAP-All-Terrain Vehicle (M-ATV), joint lightweight tactical vehicle, and the High Mobility Multi-purpose Wheeled Vehicle (HMMWV) using multi-criteria effectiveness analysis ...
Klaus, Christian (Monterey, California: Naval Postgraduate School, 2014-03);We define and solve two network-design problems. In the first, (1) a defender uses limited resources to select a portfolio of paths or design a sub-network; (2) an attacker then uses limited attack resources to destroy ...