Sharpe's algorithm for portfolio improvement

Mon, Aug 1, 2011 7:57 PM

Brian G. Peterson wrote:

On Mon, 2011-08-01 at 17:07 -0400, John P. Burkett wrote:

Enrico Schumann wrote:

what kind of "difficulty" did you encounter? If you would give more details
on what you tried, and how, then people should be better able to help you.

Thank you, Enrico, for your prompt and helpful response.  Focusing on 
Sharpe's algorithm, I originally omitted specifics about difficulties I 
have encountered with packages based on other algorithms.  However, in 
case it is of interest, I will now outline my project and difficulties. 
     I have about 120 monthly observations on gross real returns for 
about 30 assets. [Trying to mitigate estimation error, I've shrunk 
observed returns toward a common value as proposed by Philippe Jorion, 
"Bayes-Stein Estimation for Portfolio Analysis",
Journal of Financial and Quantitative Analysis, v. 21, n. 3 (Sept., 
1986), pp. 279-92.]   I initially specified the utility function as U = 
R/(0.5 + R) where R is R is the gross return on a portfolio and 
specified long-only constraints. The restriction that portfolio shares 
sum to 1 is handled by specifying n-1 variables (where n is the nubmer 
of assets) and making the share asset n be 1 minus the sum of other 
shares. If I apply DEoptim to a sufficiently small subset of the assets, 
it converges and  selects a plausible portfolio.  Yet if I ask DEoptim 
to analyze as many as 30 assets, it fails to converge in any number of 
iterations that I've tried.  Given the same problem, Rgenoud converged 
after 44 hours (more than 2 million generation, if memory serves).  I 
subsequently tried changing the utility function to ln(R) and asking 
Rgenoud to maximize that.  Thus far it has run for over 1.5 million 
generations without converging.  The portfolio shares have barely 
changed over many recent generations.  Perhaps I could just relax the 
default convergence criteria and declare the problem solved for 
practical purposes.  However, that might result in mistaking a local for 
a global maximum.  These experiences may just indicate that a 30 asset 
portfolio is hard to optimize using general purpose algorithms. Kris 
Boudt et al. note that "portfolio problems encountered in practice may 
require days to optimize on a personal computer" ("Large-scale portfolio 
optimization with DEoptim," p. 1). These experiences motivated my 
interest in trying an algorithm, such as that of Sharpe, designed 
specifically for portfolio optimization.

As one of the authors of the paper in question, I'll note that I was
talking about portfolios with hundreds or thousands of assets, and/or
with many rebalancing periods or observations.  Monthly series of 120
observations each shouldn't take millions of iterations to converge.  It
is possible that the starting set is not feasible, given the way your
full investment constraint is being applied.

Thanks, Brian.  I'll double check my code to see if it's given DEoptim 
an impossible task.

These are very helpful leads.  I'll pursue them tomorrow morning. 
Thanks again!

Best regards,
John

- Brian

I don't know the paper you mentioned, but I know a paper of W. Sharpe in
which he suggests to do repeated zero-sum changes to the portfolio, like
"increase one asset by x%, and decrease another one by x%". If that is what
you mean, this can be done with a local search.

The algorithm you describe sounds very much like that covered in the 
articles I cited in my previous note.  It's probably the same algorithm.

(But actually, other

functions like DEoptim should work just as well. The DEoptim package even
comes with a vignette that adresses portfolio optimisation.)

Perhaps I should just be more patient with DEoptim or buy a faster computer!

An example for a local search procedure is given in one of the vignettes of
the NMOF package (which is available from
https://r-forge.r-project.org/R/?group_id=1128 ), even though I am not sure
how self-explanatory the vignette is.

Thank you for the NMOF reference.  I've printed "Examples and Extensions 
for the NMOF package" and tried the command
install.packages("NMOF", repos = "http://R-Forge.R-project.org")
That command elicited the following messages:
Warning in install.packages("NMOF", repos = 
"http://R-Forge.R-project.org") :
   argument 'lib' is missing: using 
'/home/john/R/i486-pc-linux-gnu-library/2.8'
trying URL 'http://R-Forge.R-project.org/src/contrib/NMOF_0.14-2.tar.gz'
Content type 'application/x-gzip' length 1352123 bytes (1.3 Mb)
opened URL
==================================================
downloaded 1.3 Mb

* Installing *source* package 'NMOF' ...
** R
** data
**  moving datasets to lazyload DB
** inst
** preparing package for lazy loading
** help

  >>> Building/Updating help pages for package 'NMOF'

      Formats: text html latex example
   DEopt                             text    html    latex   example
   EuropeanCall                      text    html    latex   example
   GAopt                             text    html    latex   example
   LSopt                             text    html    latex   example
   MA                                text    html    latex   example
   NMOF-package                      text    html    latex   example
   NS                                text    html    latex   example
   NSf                               text    html    latex   example
   PSopt                             text    html    latex   example
   TAopt                             text    html    latex   example
   bundData                          text    html    latex   example
   callHestoncf                      text    html    latex   example
   fundData                          text    html    latex   example
   gridSearch                        text    html    latex   example
   qTable                            text    html    latex   example

ERROR in file 'repairMatrix.Rd': Environment (text enclosed in {}) found 
in \title{...}.
The title must be plain text!

ERROR: building help failed for package 'NMOF'
** Removing '/home/john/R/i486-pc-linux-gnu-library/2.8/NMOF'

The downloaded packages are in
	/tmp/RtmpNAuDvf/downloaded_packages
Warning message:
In install.packages("NMOF", repos = "http://R-Forge.R-project.org") :
   installation of package 'NMOF' had non-zero exit status

***************************************

Any suggestions for how to successfully install NMOF would be greatly 
appreciated.

Best regards,
John

Regards,
Enrico

-----Urspr?ngliche Nachricht-----
Von: r-sig-finance-bounces at r-project.org 
[mailto:r-sig-finance-bounces at r-project.org] Im Auftrag von 
John P. Burkett
Gesendet: Montag, 1. August 2011 18:49
An: R-SIG-Finance at r-project.org
Betreff: [R-SIG-Finance] Sharpe's algorithm for portfolio improvement

An attractive sounding algorithm for maximizing the expected 
utility of of a portfolio was proposed by William F. Sharpe 
in "An algorithm for portfolio improvement," Advances in 
Mathematical Programming and Financial Planning, 1987, pp. 
155-170 and summarized by the same author in "Expected 
utility asset allocation," Financial Analysts Journal, vol. 
63, no. 5 (Sep.-Oct., 2007), pp. 18-30.

Has this algorithm been implemented in R?

If not, is there a substitute that is likely to work well for 
a user-specified concave utility function?  I've tried optim, 
DEoptim, and Rgenoud but encountered difficulty in getting 
them to converge for a long-only portfolio of around 30 assets.

Best regards,
John

--
John P. Burkett
Department of Economics
University of Rhode Island
Kingston, RI 02881-0808
USA

John P. Burkett
Department of Economics
University of Rhode Island
Kingston, RI 02881-0808
USA

phone (401) 874-9195

Sharpe's algorithm for portfolio improvement

Thread (22 messages)