[R-SIG-Finance] Sharpe's algorithm for portfolio improvement

John P. Burkett burkett at uri.edu
Tue Aug 2 04:57:40 CEST 2011

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.

> If your objective function is truly a smooth convex function, then
> optim() or some other linear or conical solver should be sufficient.  If
> the function is not smooth (and real portfolio objectives and
> constraints rarely are), then a random portfolios or a global optimizer
> will be required.  
> Perhaps you should start with a couple hundred random portfolio survey
> of your feasible space?
> This may be accomplished in R with Pat Burns' excellent Portfolio Probe
> (commercial non-free), or with PortfolioAnalytics (open source/free, on
> R-Forge).
> PortfolioAnalytics will also allow you to use DEoptim after using random
> portfolios to get close to the global minima.  
> See out R/Finance seminar presentation here:
> http://www.rinfinance.com/agenda/2010/Carl+Peterson+Boudt_Tutorial.pdf
> and the code to replicate here:
> https://r-forge.r-project.org/scm/viewvc.php/*checkout*/pkg/PortfolioAnalytics/sandbox/script.workshop2010.R?root=returnanalytics
> PortfolioAnalytics does some of the heavy lifting to set good defaults
> and give you a good set of starting population values to speed
> convergence.
> Also, Pat Burns' Portfolio Probe blog is here:
> http://www.portfolioprobe.com/blog/
These are very helpful leads.  I'll pursue them tomorrow morning. 
Thanks again!

Best regards,

> - 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

phone (401) 874-9195

More information about the R-SIG-Finance mailing list