Foundations and Trends® in Optimization > Vol 1 > Issue 1

Performance Bounds and Suboptimal Policies for Multi–Period Investment

Stephen Boyd, Stanford University, USA, boyd@stanford.edu Mark T. Mueller, Massachusetts Institute of Technology, USA, mark.t.mueller@mac.com Brendan O’Donoghue, Stanford University, USA, bodonoghue85@gmail.com Yang Wang, Stanford University, USA, ang1024@gmail.com
 
Suggested Citation
Stephen Boyd, Mark T. Mueller, Brendan O’Donoghue and Yang Wang (2014), "Performance Bounds and Suboptimal Policies for Multi–Period Investment", Foundations and Trends® in Optimization: Vol. 1: No. 1, pp 1-72. http://dx.doi.org/10.1561/2400000001

Published: 01 Jan 2014
© 2014 S. Boyd, M. T. Mueller, B. O’Donoghue, and Y. Wang
 
Subjects
Optimization
 

Free Preview:

Article Help

Share

Download Free Copy
In this article:
1. Introduction
2. Stochastic Control Formulation
3. Optimal Policy
4. Performance Bounds
5. Approximate Dynamic Programming
6. Model Predictive Control
7. Numerical Examples
8. Conclusions
Appendices
References

Abstract

We consider dynamic trading of a portfolio of assets in discrete periods over a finite time horizon, with arbitrary time-varying distribution of asset returns. The goal is to maximize the total expected revenue from the portfolio, while respecting constraints on the portfolio such as a required terminal portfolio and leverage and risk limits. The revenue takes into account the gross cash generated in trades, transaction costs, and costs associated with the positions, such as fees for holding short positions. Our model has the form of a stochastic control problem with linear dynamics and convex cost function and constraints. While this problem can be tractably solved in several special cases, such as when all costs are convex quadratic, or when there are no transaction costs, our focus is on the more general case, with nonquadratic cost terms and transaction costs.

We show how to use linear matrix inequality techniques and semidefinite programming to produce a quadratic bound on the value function, which in turn gives a bound on the optimal performance. This performance bound can be used to judge the performance obtained by any suboptimal policy. As a by–product of the performance bound computation, we obtain an approximate dynamic programming policy that requires the solution of a convex optimization problem, often a quadratic program, to determine the trades to carry out in each step. While we have no theoretical guarantee that the performance of our suboptimal policy is always near the performance bound (which would imply that it is nearly optimal) we observe that in numerical examples the two values are typically close.

DOI:10.1561/2400000001
ISBN: 978-1-60198-672-6
92 pp. $70.00
Buy book
 
ISBN: 978-1-60198-673-3
92 pp. $120.00
Buy E-book
Table of contents:
1. Introduction
2. Stochastic Control Formulation
3. Optimal Policy
4. Performance Bounds
5. Approximate Dynamic Programming
6. Model Predictive Control
7. Numerical Examples
8. Conclusions
Appendices
References

Performance Bounds and Suboptimal Policies for Multi–Period Investment

Performance Bounds and Suboptimal Policies for Multi–Period Investment examines dynamic trading of a portfolio of assets in discrete periods over a finite time horizon, with arbitrary time–varying distribution of asset returns. The goal is to maximize the total expected revenue from the portfolio, while respecting constraints on the portfolio like a required terminal portfolio and leverage and risk limits. The revenue takes into account the gross cash generated in trades, transaction costs, and costs associated with the positions, such as fees for holding short positions. The model that is presented takes the form of a stochastic control problem with linear dynamics and convex cost function and constraints. While this problem can be tractably solved in several special cases – for example, when all costs are convex quadratic, or when there are no transaction costs – the focus is on the more general case, with nonquadratic cost terms and transaction costs.

Performance Bounds and Suboptimal Policies for Multi–Period Investment shows how to use linear matrix inequality techniques and semidefinite programming to produce a quadratic bound on the value function, which in turn gives a bound on the optimal performance. This performance bound can be used to judge the performance obtained by any suboptimal policy. As a by–product of the performance bound computation, an approximate dynamic programming policy is obtained that requires the solution of a convex optimization problem, often a quadratic program, to determine the trades to carry out in each step.

 
OPT-001