Publication:
Dynamic-programming approaches to single-and multi-stage stochastic knapsack problems for portfolio optimization

Loading...
Thumbnail Image
Authors
Khoo, Wai Gea
Subjects
Advisors
Wood, R. Kevin
Date of Issue
1999-03
Date
March, 1999
Publisher
Monterey, California: Naval Postgraduate School
Language
en_US
Abstract
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.
Type
Thesis
Description
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xxii, 49 p.;28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Collections