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

Tue Aug 2 04:24:58 CEST 2011

alexios wrote:
> I've found the cmaes (Covariance Matrix Adapting Evolutionary Strategy) 
> solver on CRAN to be quite robust to some nonconvex portfolio
> problems which required a global optimizer. Like other such global 
> solvers which do not accept explicit constraint functions, you would 
> need to create a sort of penalty barrier function i.e
> 
> -obj(x) + 100*(1-sum(x))^2
> 
Alexios,
Thank you for your suggestions.  CMAES looks promising for some 
applications. However, for maximizing expected utility or minimizing -1* 
(expected utility), detection of CMAES convergence could be tricky.  The 
reference manual, in the section on the cma_es function, states that "no 
sophisticated convergence detection is included" (p. 3)  If the user 
specifies a value for stopfitness, the computation will halt once the 
objective function value "is smaller than or equal to stopfitness" (p. 
3).  "This is the only way for CMA-ES to 'converge'" (p. 3). If we knew 
the minimum attainable value for -1*(expected utility), we could specify 
stopfitness as a number slightly greater than that value. 
Unfortunately, in portfolio optimization problems we seldom know the 
minimum attainable value of -1*(expected utility) until we have found 
the optimal portfolio.


> For state of the art global solvers you'll probably need to look outside 
> R to a commercial implementation or try submitting your problem to the 
> NEOS server (http://www.neos-server.org/neos/solvers/index.html...see in 
> particular the Branch and Bound type solver BARON).
Thanks for drawing my attention to BARON.  It looks good; when I've 
learned enough about GAMS format, I'll give it a try.

Best regards,
John


> 
> Regards,
> 
> Alexios
> 
> On 01/08/2011 22:07, 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.
>>
>>> 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
>>>>
>>>> _______________________________________________
>>>> 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