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

[John P. Burkett]

Patrick Burns wrote:
> Another alternative to get the budget
> constraint is to let the optimizer see
> unconstrained solutions but then scale
> the weights before evaluating the utility.
> 
> This has the possibility of confusing some
> optimizers, but can work pretty well.

Thank you, Patrick, for this suggestion.  I tried implementing it in 
DEoptim by writing the function to be minimized as shown below.  This 
code is intended to handle a long-only portfolio of 31 assets.  The 
variable x is meant to be a vector representing the shares of the assets 
in the portfolio. The Data matrix has dimensions 20x31. Each row 
corresponds a time period (six months for all but the first period, 
which is only four months long).  Each column corresponds to an asset. 
The elements of the matrix are gross returns. (The gross returns for the 
short first period are raised to the 3/2 power to make them comparable 
to those for the other periods.)  My attempt to rescale the variables to 
assure that they add up to one can be found 5 lines from the bottom of 
the code below.

Neu31<- function(x){
x1 <- x[1]
x2 <- x[2]
x3 <- x[3]
x4 <- x[4]
x5 <- x[5]
x6 <- x[6]
x7 <- x[7]
x8 <- x[8]
x9 <- x[9]
x10 <- x[10]
x11 <- x[11]
x12 <- x[12]
x13 <- x[13]
x14 <- x[14]
x15 <- x[15]
x16 <- x[16]
x17 <- x[17]
x18 <- x[18]
x19 <- x[19]
x20 <- x[20]
x21 <- x[21]
x22 <- x[22]
x23 <- x[23]
x24 <- x[24]
x25 <- x[25]
x26 <- x[26]
x27 <- x[27]
x28 <- x[28]
x29 <- x[29]
x30 <- x[30]
x31 <- x[31]
if (sum(x) == 0) {x <- x + 1e-2}
x = x/sum(x)
grp <- Data%*%x
  u <- grp/(.5 + grp)
objfun <- -sum(u)/nr
return(objfun)
}

To create initial shares summing to one, I used the following code:
npar = 31
NP = 10*npar
rum <- matrix(runif(npar*NP), ncol=npar, nrow=NP)
rowsums <- rowSums(rum)
ip <- rum/rowsums

Finally I invoked DEoptim as follows:
out <- DEoptim(Neu31, lower, upper, control=list(NP=NP, initial=ip, 
itermax=5000, F=.8))

That started the iterations, which progressed plausibly until getting 
stuck at iteration 4055.  At that point my computer became unresponsive 
and remained so until I rebooted.

Any suggestions for improving the code to obtain convergence would be 
greatly appreciated.

Best regards,
John





> 
> On 02/08/2011 03:24, John P. Burkett wrote:
>> 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