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

John P. Burkett burkett at uri.edu
Mon Aug 8 23:19:47 CEST 2011


Brian G. Peterson wrote:
> Just to round out this thread on-list, I've attached a script for the
> problem as described by Prof. Burkett that uses the Munger and Arrow
> bounded utility function to construct a portfolio via PortfolioAnalytics
> using both random portfolios and DEoptim as alternate optimization
> engines.

Thanks again for your ingenious script and illuminating comments.

The only contribution I can make to the discussion now is to provide 
some references on bounded utility functions.  Karl Menger (a 
mathematician and son of the Austrian economist Carl Menger) made a case 
for bounded utility functions in a 1934 article in German.  An English 
translation was published as "The Role of Uncertainty in Economics", ch. 
16 in Essays in Mathematical Economics in Honor of Oskar Morenstern, ed. 
Martin Shubik (Princeton University Press, 1967).  Other arguments for 
bounded utility functions have been made by Kenneth J. Arrow, Essays in 
the Theory of Risk-bearing (Markham, 1971) and by John W. Pratt, Howard 
Raiffa, and Robert Schlaifer, Introduction to Statistical Decision 
Theory (MIT Press, 1995), pp. 80-81.  The particular utility function I 
have been using is just one example of a bounded utility function, 
expressed in terms of gross return. To the best of my knowledge, none of 
the authorities cited above have recommended this particular function. 


Best regards,
John



> 
> I've modified the script to use the 'edhec' data series included with
> PerformanceAnalytics for reproducibility.
> 
> As Enrico noted in an earlier post, this utility function tends towards
> creating very concentrated portfolios in only a small number of assets.
> 
> Regards,
> 
>    - Brian
> 
> 
> On Mon, 2011-08-01 at 22:57 -0400, John P. Burkett wrote:
>> 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,
>> 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
>>
>> _______________________________________________
>> R-SIG-Finance at r-project.org mailing list
>> https://stat.ethz.ch/mailman/listinfo/r-sig-finance
>> -- Subscriber-posting only. If you want to post, subscribe first.
>> -- Also note that this is not the r-help list where general R questions should go.
> 


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

phone (401) 874-9195



More information about the R-SIG-Finance mailing list