[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,
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
More information about the R-SIG-Finance
mailing list