A branch-and-bound algorithm for the solution of a class of mixed-integer nonlinear programming problems arising from the field of investment portfolio selection is presented. The problems in this class are characterized by the inclusion of the fixed transaction costs associated with each asset, a constraint that explicitly limits the number of distinct assets in the selected portfolio, or both. Modeling either of these forms of limiting the cost of owning an investment portfolio involves the introduction of binary variables, resulting in a mathematical programming problem that has a nonconvex feasible set. Two objective functions are examined in this thesis; the first is a positive definite quadratic function which is commonly used in the selection of investment portfolios. The second is a convex function that is not continuously differentiable; this objective function, although not as popular as the first, is, in many cases, a more appropriate objective function. To take advantage of the structure of the model, the branch-and-bound algorithm is not applied in the standard fashion; instead, we generalize the implicit branch-and-bound algorithm introduced by Bienstock (3). This branch-and-bound algorithm adopts many of the standard techniques from mixed-integer linear programming, including heuristics for finding feasible points and cutting planes. Implicit branch-and-bound involves the solution of a sequence of subproblems of the original problem, and thus it is necessary to be able to solve these subproblems efficiently. For each of the two objective functions, we develop an algorithm for solving its corresponding subproblems; these algorithms exploit the structure of the constraints and the objective function, simplifying the solution of the resulting linear systems. Convergence for each algorithm is proven. Results are provided for computational experiments performed on investment portfolio selection problems for which the cardinality of the universe of assets available for inclusion in the selected portfolio ranges in size from 52 to 1140.
| Identifer | oai:union.ndltd.org:RICE/oai:scholarship.rice.edu:1911/19140 |
| Date | January 1997 |
| Creators | Butera, Gwyneth Owens |
| Contributors | Bixby, Robert E., Dennis, John E., Jr. |
| Source Sets | Rice University |
| Language | English |
| Detected Language | English |
| Type | Thesis, Text |
| Format | 143 p., application/pdf |
Page generated in 0.0163 seconds