Dynamic-programming approaches to single-and multi-stage stochastic knapsack problems for portfolio optimization
dc.contributor.advisor | Wood, R. Kevin | |
dc.contributor.author | Khoo, Wai Gea | |
dc.date | March, 1999 | |
dc.date.accessioned | 2012-09-07T15:35:06Z | |
dc.date.available | 2012-09-07T15:35:06Z | |
dc.date.issued | 1999-03 | |
dc.identifier.uri | https://hdl.handle.net/10945/13618 | |
dc.description.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. | en_US |
dc.description.uri | http://archive.org/details/dynamicprogrammi1094513618 | |
dc.format.extent | xxii, 49 p.;28 cm. | en_US |
dc.language.iso | en_US | |
dc.publisher | Monterey, California: Naval Postgraduate School | en_US |
dc.title | Dynamic-programming approaches to single-and multi-stage stochastic knapsack problems for portfolio optimization | en_US |
dc.type | Thesis | en_US |
dc.description.service | Singapore Ministry of Defense author (civilian). | en_US |
etd.thesisdegree.name | M.S. in Operations Research | en_US |
etd.thesisdegree.level | Masters | en_US |
etd.thesisdegree.discipline | Operations Research | en_US |
etd.thesisdegree.grantor | Naval Postgraduate School | en_US |
dc.description.distributionstatement | Approved for public release; distribution is unlimited. |
Files in this item
This item appears in the following Collection(s)
-
1. Thesis and Dissertation Collection, all items
Publicly releasable NPS Theses, Dissertations, MBA Professional Reports, Joint Applied Projects, Systems Engineering Project Reports and other NPS degree-earning written works.