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 _______________________________________________ [hidden email] 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. |
Check the CRAN finance task view at
http://cran.r-project.org/web/views/Finance.html There is a full eBook on portfolio optimization using Rmetrics, https://wwww.rmetrics.org/ebooks-portfolio, see also http://www.rinfinance.com/RinFinance2009/presentations/yollin_slides.pdf and https://stat.ethz.ch/pipermail/r-sig-finance/2009q1/003507.html On Mon, Aug 1, 2011 at 9:48 AM, John P. Burkett <[hidden email]> wrote: > 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 > > ______________________________**_________________ > [hidden email] mailing list > https://stat.ethz.ch/mailman/**listinfo/r-sig-finance<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. > [[alternative HTML version deleted]] _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
Hi John, 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. 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. (But actually, other functions like DEoptim should work just as well. The DEoptim package even comes with a vignette that adresses portfolio optimisation.) 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. Regards, Enrico > -----Ursprüngliche Nachricht----- > Von: [hidden email] > [mailto:[hidden email]] Im Auftrag von > John P. Burkett > Gesendet: Montag, 1. August 2011 18:49 > An: [hidden email] > 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 > > _______________________________________________ > [hidden email] 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. _______________________________________________ [hidden email] 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. |
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: [hidden email] >> [mailto:[hidden email]] Im Auftrag von >> John P. Burkett >> Gesendet: Montag, 1. August 2011 18:49 >> An: [hidden email] >> 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 >> >> _______________________________________________ >> [hidden email] 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 _______________________________________________ [hidden email] 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. |
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 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). 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: [hidden email] >>> [mailto:[hidden email]] Im Auftrag von John P. >>> Burkett >>> Gesendet: Montag, 1. August 2011 18:49 >>> An: [hidden email] >>> 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 >>> >>> _______________________________________________ >>> [hidden email] 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. >> >> > > _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
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. 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/ - 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: [hidden email] > >> [mailto:[hidden email]] Im Auftrag von > >> John P. Burkett > >> Gesendet: Montag, 1. August 2011 18:49 > >> An: [hidden email] > >> 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 > >> _______________________________________________ [hidden email] 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. |
In reply to this post by alexios
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: [hidden email] >>>> [mailto:[hidden email]] Im Auftrag von John P. >>>> Burkett >>>> Gesendet: Montag, 1. August 2011 18:49 >>>> An: [hidden email] >>>> 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 >>>> >>>> _______________________________________________ >>>> [hidden email] 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 _______________________________________________ [hidden email] 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. |
In reply to this post by braverock
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. > 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/ 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: [hidden email] >>>> [mailto:[hidden email]] Im Auftrag von >>>> John P. Burkett >>>> Gesendet: Montag, 1. August 2011 18:49 >>>> An: [hidden email] >>>> 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 _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
With 120 observations and 30 assets and a smooth objective function and
relatively simple constraints, the running time should be *seconds*. One potential problem with DE is how the constraints are implemented, more specifically the lower/upper limits. When DE creates new solutions, it does not observe any constraints except for such that one "implicitly" adds (eg, like you did with the budget constraint). Thus, one typically repairs the constraints after new solutions are created, or penalises solutions that violate constraints. If you penalise too strongly, the algorithm will in effect throw away many candidate solutions, and so the algorithm may indeed have a hard time to find a solution, since in portfolio optimisation problems the solution is often on the boundary. Regarding the installation error: the \title in one Rd-file uses quotation marks (via \sQuote), which should be supported (according to R-exts since R 2.12.0). R CMD check never complained to me on Win XP or Ubuntu. Could you please send me (off-list) the R-version/OS you work on? But I will remove the quotation marks later today, so the new version should be available from R-Forge tomorrow. Please let me know if this doesn't work either. Regards, Enrico > -----Ursprüngliche Nachricht----- > Von: [hidden email] > [mailto:[hidden email]] Im Auftrag von > John P. Burkett > Gesendet: Montag, 1. August 2011 23:08 > An: Enrico Schumann; [hidden email] > Betreff: Re: [R-SIG-Finance] Sharpe's algorithm for portfolio > improvement > > 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: [hidden email] > >> [mailto:[hidden email]] Im Auftrag > von John P. > >> Burkett > >> Gesendet: Montag, 1. August 2011 18:49 > >> An: [hidden email] > >> 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 > >> > >> _______________________________________________ > >> [hidden email] 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 > > _______________________________________________ > [hidden email] 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. _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
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. 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: [hidden email] >>>>> [mailto:[hidden email]] Im Auftrag von John P. >>>>> Burkett >>>>> Gesendet: Montag, 1. August 2011 18:49 >>>>> An: [hidden email] >>>>> 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 >>>>> >>>>> _______________________________________________ >>>>> [hidden email] 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. >>>> >>>> >>> >>> >> >> > > -- Patrick Burns [hidden email] http://www.burns-stat.com http://www.portfolioprobe.com/blog twitter: @portfolioprobe _______________________________________________ [hidden email] 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. |
In reply to this post by Enrico Schumann
n Tue, 2011-08-02 at 07:31 +0200, Enrico Schumann wrote:
> One potential problem with DE is how the constraints are implemented, > more specifically the lower/upper limits. When DE creates new > solutions, it does not observe any constraints except for such that > one "implicitly" adds (eg, like you did with the budget constraint). This isn't *quite* correct. DE will observe your lower and upper bounds on each objective parameter (asset weight), but will not observe some additional overall constraint such as a full investment constraint. > Thus, one typically repairs the constraints after new solutions are > created, This mirrors Pat Burns' point about letting the optimizer do its thing, and then 'adjusting' the parameter set inside your objective function to apply the constraint. For many portfolios, this works quite well, but for those where it doesn't work, a penalty function needs to be applied. > or penalises solutions that violate constraints. If you penalise too > strongly, the algorithm will in effect throw away many candidate > solutions, and so the algorithm may indeed have a hard time to find a > solution, since in portfolio optimisation problems the solution is > often on the boundary. I would put this difficulty a little differently. If the constraint we are concerned with is the full investment constraint, then the issue is one of how large the feasible adjusted constrained space (portfolios with weight bounds min_w and max_w where sum(w)==1) in comparison to the total space the optimizer will search (all portfolios comprised of assets in any combination of weights min_w to max_w). If the feasible space is large in comparison to the total space, a global optimizer will locate the solution. If the feasible space is not large in comparison to the total space, and a large penalty function is used to tell the optimizer that it is not close, then it could take a long time to find a solution. There are several approaches to addressing this. One is to graduate your penalty response, for example penalizing with some multiplier (which should be scaled somewhat larger than a 'good' value of the objective function, so for global minima at -1, perhaps a multiplier of 10 or 100 will serve) the absolute value of the amount the sum of the weights exceeds 1. You can make this work even better by applying a fraction of the penalty for any sum of weights that is less than one, because this solution is likely closer to the feasible space. I find that it is best to pre-seed the optimizer with a population of candidate portfolios that are all inside the feasible space, so that even random perturbations are still closer to the feasible space. In PortfolioAnalytics, we pre-seed be default, and use a full-investment constraint adjustment by default (with a graduated penalty function as another supported alternative), and of course all these options are changeable by the user. I haven't been able to locate the original Sharpe paper, but I suspect he utilized a smooth objective function given the date of the paper alone. In that case, as I said previously, you don't need and *won't benefit from* a global optimizer. Some other author has probably already cited Sharpe's paper and told you how to use an exact or smooth-surface optimization technique. Of course, as soon as you want to add another layer to your objective, or more complex constraints, you're back in the land of global optimization. Regards, - Brian -- Brian G. Peterson http://braverock.com/brian/ Ph: 773-459-4973 IM: bgpbraverock _______________________________________________ [hidden email] 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. |
[comments inline]
> -----Ursprüngliche Nachricht----- > Von: Brian G. Peterson [mailto:[hidden email]] > Gesendet: Dienstag, 2. August 2011 14:37 > An: Enrico Schumann > Cc: 'John P. Burkett'; [hidden email] > Betreff: Re: [R-SIG-Finance] Sharpe's algorithm for portfolio > improvement > > n Tue, 2011-08-02 at 07:31 +0200, Enrico Schumann wrote: > > One potential problem with DE is how the constraints are > implemented, > > more specifically the lower/upper limits. When DE creates new > > solutions, it does not observe any constraints except for such that > > one "implicitly" adds (eg, like you did with the budget constraint). > > This isn't *quite* correct. DE will observe your lower and > upper bounds on each objective parameter (asset weight), but > will not observe some additional overall constraint such as a > full investment constraint. Sorry if there was a misunderstanding: when I referred to 'DE', I meant Differential Evolution in general, not 'DEoptim'. I don't know how the constraints are incorporated in 'DEoptim'. > > > Thus, one typically repairs the constraints after new > solutions are > > created, > > This mirrors Pat Burns' point about letting the optimizer do > its thing, and then 'adjusting' the parameter set inside your > objective function to apply the constraint. For many Just for the record: actually we have even two possibilities: really repair, or just map the solutions into feasible ones. In the latter case, we go on evolving the solutions that violate the constraints. > portfolios, this works quite well, but for those where it > doesn't work, a penalty function needs to be applied. > > > or penalises solutions that violate constraints. If you > penalise too > > strongly, the algorithm will in effect throw away many candidate > > solutions, and so the algorithm may indeed have a hard time > to find a > > solution, since in portfolio optimisation problems the solution is > > often on the boundary. > > I would put this difficulty a little differently. If the > constraint we are concerned with is the full investment > constraint, then the issue is one of how large the feasible > adjusted constrained space (portfolios with weight bounds > min_w and max_w where sum(w)==1) in comparison to the total > space the optimizer will search (all portfolios comprised of > assets in any combination of weights min_w to max_w). > > If the feasible space is large in comparison to the total > space, a global optimizer will locate the solution. If the if it works properly, yes :) > feasible space is not large in comparison to the total space, > and a large penalty function is used to tell the optimizer > that it is not close, then it could take a long time to find > a solution. > > There are several approaches to addressing this. One is to > graduate your penalty response, for example penalizing with > some multiplier (which should be scaled somewhat larger than > a 'good' value of the objective function, so for global > minima at -1, perhaps a multiplier of 10 or 100 will serve) > the absolute value of the amount the sum of the weights > exceeds 1. You can make this work even better by applying a > fraction of the penalty for any sum of weights that is less > than one, because this solution is likely closer to the > feasible space. Yes, the important point, I think, is that in such cases the feedback from the penalty need be constructive, ie, "how much do I violate a constraint?" (if I want to push some object from the table to the floor, then feedback like 'the object is still on the table' is less useful than 'the object is now 3cm off the edge of the table') But you can also directly use the constraint in the creation of the new solutions, which is what Sharpe suggested (and what works quite well, and not just for smooth functions/constraints): if you only add zero-sum changes to a feasible portfolio, it will remain feasible with respect to the budget constraint. If you want min/max-holding sizes, choose asset weights such that the min/max-constraints remain unviolated. This is straightforward in methods like Simulated Annealing/Threshold Accepting, but somewhat more difficult in 'DE'. (Which does not mean that 'DE' is not as good as the other methods, just that the efficient approaches possibly differ, depending on the method.) > > I find that it is best to pre-seed the optimizer with a > population of candidate portfolios that are all inside the > feasible space, so that even random perturbations are still > closer to the feasible space. In PortfolioAnalytics, we > pre-seed be default, and use a full-investment constraint > adjustment by default (with a graduated penalty function as > another supported alternative), and of course all these > options are changeable by the user. > > I haven't been able to locate the original Sharpe paper, but > I suspect he utilized a smooth objective function given the > date of the paper alone. In that case, as I said previously, > you don't need and *won't benefit from* a global optimizer. > Some other author has probably already cited Sharpe's paper > and told you how to use an exact or smooth-surface > optimization technique. Of course, as soon as you want to add > another layer to your objective, or more complex constraints, > you're back in the land of global optimization. > > Regards, > > - Brian > > -- > Brian G. Peterson > http://braverock.com/brian/ > Ph: 773-459-4973 > IM: bgpbraverock > best regards, Enrico _______________________________________________ [hidden email] 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. |
In reply to this post by Patrick Burns-2
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: [hidden email] >>>>>> [mailto:[hidden email]] Im Auftrag von John P. >>>>>> Burkett >>>>>> Gesendet: Montag, 1. August 2011 18:49 >>>>>> An: [hidden email] >>>>>> 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 >>>>>> >>>>>> _______________________________________________ >>>>>> [hidden email] 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 _______________________________________________ [hidden email] 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. |
In reply to this post by Enrico Schumann
Enrico Schumann wrote:
> But you can also directly use the constraint in the creation of the new > solutions, which is what Sharpe suggested (and what works quite well, and > not just for smooth functions/constraints): if you only add zero-sum changes > to a feasible portfolio, it will remain feasible with respect to the budget > constraint. If you want min/max-holding sizes, choose asset weights such > that the min/max-constraints remain unviolated. This is straightforward in > methods like Simulated Annealing/Threshold Accepting, but somewhat more > difficult in 'DE'. (Which does not mean that 'DE' is not as good as the > other methods, just that the efficient approaches possibly differ, depending > on the method.) Thanks, Enrico. I'm interested in using the adding-up constraint in the creation of new solutions, via methods such as simulated annealing or threshold accepting. I imagine that the DMOF package is useful for implementing that approach. Are there also other packages that I should consider? Best regards, John -- John P. Burkett Department of Economics University of Rhode Island Kingston, RI 02881-0808 USA phone (401) 874-9195 _______________________________________________ [hidden email] 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. |
[see below]
> -----Ursprüngliche Nachricht----- > Von: [hidden email] > [mailto:[hidden email]] Im Auftrag von > John P. Burkett > Gesendet: Mittwoch, 3. August 2011 18:36 > An: [hidden email] > Betreff: Re: [R-SIG-Finance] Sharpe's algorithm for portfolio > improvement > > Enrico Schumann wrote: > > > But you can also directly use the constraint in the creation of the > > new solutions, which is what Sharpe suggested (and what works quite > > well, and not just for smooth functions/constraints): if > you only add > > zero-sum changes to a feasible portfolio, it will remain > feasible with > > respect to the budget constraint. If you want > min/max-holding sizes, > > choose asset weights such that the min/max-constraints remain > > unviolated. This is straightforward in methods like Simulated > > Annealing/Threshold Accepting, but somewhat more difficult in 'DE'. > > (Which does not mean that 'DE' is not as good as the other methods, > > just that the efficient approaches possibly differ, > depending on the > > method.) > > Thanks, Enrico. I'm interested in using the adding-up > constraint in the creation of new solutions, via methods such > as simulated annealing or threshold accepting. I imagine > that the DMOF package is useful for implementing that > approach. Are there also other packages that I should consider? > There are many packages in R that handle optimisation, but I am not really familiar with most if them. The task view for optimisation was already suggested to you; you may also want to browse R-Forge/RForge. I cannot comment on the model that you gave your other e-mail -- even though, this objective function will essentially pick portfolios of just very few assets with very high returns; I hope you have faith that your return scenarios are representative of what will happen in the future. Here is a complete example with TAopt from the NMOF package; it is mostly copy--pasted from a package vignette. Since I don't have your data, I create random data and put all data into one list which I later pass to the function TAopt. # --- # require("NMOF") # the neighbourhood: see the package vignette on portfolio optimisation resample <- function(x, ...) x[sample.int(length(x), ...)] # see ?sample neighbourU <- function(sol, data){ wn <- sol$w toSell <- wn > data$winf toBuy <- wn < data$wsup i <- resample(which(toSell), size = 1L) j <- resample(which(toBuy), size = 1L) eps <- runif(1) * data$eps eps <- min(wn[i] - data$winf, data$wsup - wn[j], eps) wn[i] <- wn[i] - eps wn[j] <- wn[j] + eps Rw <- sol$Rw + data$R[,c(i,j)] %*% c(-eps,eps) list(w = wn, Rw = Rw) } # random data na <- 31L # number of assets nr <- 20L # number of return obs randomData <- rnorm(nr*na)*0.01 # random data: a plain matrix ;) dim(randomData) <- c(nr, na) # collect all in 'data': eps is stepsize for TA, winf/wsup are min/max holding sizes data <- list(R = randomData, na = na, nr = nr, eps = 0.5/100, winf = 0, wsup = 1) # --- # The neighbourhood may look a bit complicated, but it uses the following fact: in a given iteration, your objective function can be split into two pieces: first, you compute portfolio returns Rw <- Data %*% w; then you compute your actual objective for these returns, say, fun(Rw). The multiplication will typically take much of the computing time (in particular if the actual objective is quite cheap); see the following test. But the neighbourhood function changes only two weights: increase one, decrease one. So you can update the multiplication. In your case, this may not make much difference >> but try with 100 or more return observations Thus, the representation of a solution is a list with two components: the weight vector w, and the return associated with this portfolio Rw (ie, Rw <- Data %*% w). In the objective function, you can compute anything from sol$w and sol$Rw. # --- # create a feasible random solution w0 <- runif(data$na); w0 <- w0/sum(w0) x0 <- list(w = w0, Rw = randomData %*% w0) system.time(for (i in 1:100000) Rw <- randomData %*% w0) system.time(for (i in 1:100000) ignore <- sum(Rw/(0.5 + Rw))) # test the neighbourhood x1 <- neighbourU(x0, data) all.equal(data$R %*% x1$w, x1$Rw) barplot(x0$w - x1$w) # difference between x0 and x1 # the objective function Neu31 <- function(sol, data){ u <- sol$Rw/(0.5 + sol$Rw) objfun <- -sum(u)/data$nr objfun } # --- Your objective: I have droppped the x1, x2, ... since they do not appear to be needed. Also, you use an object 'nr', but never pass it. R will find it if it is in the global environment, but I like it better to pass all objects directly or make the dependence explicit by using environments. It remains to run the algorithm. # --- # settings: see ?TAopt algo <- list(x0 = x0, neighbour = neighbourU, nS = 2000L, nT = 10L, nD = 1000L, q = 0.20, printBar = FALSE, printDetail = FALSE) system.time(res <- TAopt(Neu31, algo = algo,data = data)) res$OFvalue # the obj fun value of the solution res$xbest$w # the best weights sum(res$xbest$w) # is budget satisfied? # TA is a stochastic method: run restarts allRes <- restartOpt(fun=TAopt, OF = Neu31, n = 20L, algo = algo, data = data) allF <- sapply(allRes, `[[`, "OFvalue") # realised objective functions allw <- sapply(allRes,`[[`, c("xbest","w")) # weights hope that helps, Enrico > Best regards, > John > > -- > John P. Burkett > Department of Economics > University of Rhode Island > Kingston, RI 02881-0808 > USA > > phone (401) 874-9195 > > _______________________________________________ > [hidden email] 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. _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
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. 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: [hidden email] > >>>> [mailto:[hidden email]] Im Auftrag von > >>>> John P. Burkett > >>>> Gesendet: Montag, 1. August 2011 18:49 > >>>> An: [hidden email] > >>>> 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 > > _______________________________________________ > [hidden email] 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. Brian G. Peterson http://braverock.com/brian/ Ph: 773-459-4973 IM: bgpbraverock _______________________________________________ [hidden email] 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. Burkett_bounded_utility.R (1K) Download Attachment |
In reply to this post by John P. Burkett
[comments in-line below]
Regards, - Brian On Sat, 2011-08-06 at 18:19 -0400, John P. Burkett wrote: > Brian, > > Thank you again for your script and thoughtful comments. After running > the script and trying some variations, I have a few questions about the > optimize.portfolio function and its output. > > When optimize_method='random', I suppose a user assesses convergence (or > at least the practical value of the output) by increasing search_size > and observing what if anything happens to the objective function value > and the weights. Is that correct? Yes, this is correct. Random portfolios, with any set of objectives and constraints, let you strictly bound the amount of computing power you're going to apply to a given problem, tinker with your objective, etc, before devoting more computing time to getting to the 'true' blobal objective. One major use that I have for random portfolio evaluations is to show me the feasible space. If trace=TRUE, there should be values in the objective value output that can be sent to plot() methods. Actually, there are a set of chart.* functions dispatched by plot(), plot -> plot.optimize.portfolio -> plot.optimize.portfolio.random -> charts.RP -> chart.Scatter.RP&chart.Weights All this is covered in the documentation, at least peripherally, but the various chart.* functions can be called directly as well. Another related function you may wish to examine is extractStats(). this will take the object output by optimize.portfolio() and pull out the weights and objective measured in a tabular (data.frame) format. > When optimize_method='DEoptim', the user may have some opportunities to > adjust DEoptim's default choices for the arguments of the package's > functions. My original frustration with DEoptim was that the default > choices were not producing convergence in reasonable time and I was > uncertain about what alternative choices might hasten convergence. > PortfolioAnalytics (PA) provides a nice wrapper for DEoptim but still > leaves me wondering about function arguments and their effects on > convergence. In particular, the following questions occur to me: > 1. What choices does PA make by default for the DEoptim arguments called > F, itermax, VTR, relto1, stepto1, NP, and strategy? Can a user of PA > override the defaults for these arguments? Internally, we make a call to DEoptim.control. The user may pass any parameters in dots (...) to the optimize.portfolio command that they wish to pass on to the optimization engine. For DEoptim, we now use by default: if(!hasArg(strategy)) DEcformals$strategy=6 # use DE/current-to-p-best/1 if(!hasArg(reltol)) DEcformals$reltol=.000001 # 1/1000 of 1% change in objective is significant if(!hasArg(steptol)) DEcformals$steptol=round(N*1.5) # number of assets times 1.5 tries to improve if(!hasArg(c)) DEcformals$c=.4 # JADE mutation parameter, this could maybe use some adjustment I've found these parameters to speed convergence by about an order of magnitude on portfolio problems of 100-300+ assets over the default DEoptim parameters, though as indicated by the code comment, I think that the 'c' parameter could still use some adjustment. I'll also note that we're using JADE adaptive DE by default in PortfolioAnalytics because I have found it to converge so much faster than the classical DE algorithms. Much of the work on adding JADE to DEoptim (Joshua Ulrich wrote all that code) was motivated by interest in using it for portfolio optimization. DEoptim can apply the parameter self-adaptive properties of JADE to any strategy= parameter, not just strategy 6 DE/current-to-p-best/1, though I believe this to be the best strategy for these types of problems. > 2. Can a PA user obtain information about why iterations stopped? Most likely reltol and steptol. The default reltol is why I multiplied your objective by 1000 in the script that I sent, and steptol sometimes needs to be increased as well. > 3. How does search_size affect the DEoptim arguments? I tried > increasing search_size from 10,000 to 20,000 but noted that 1550 > 'iterations' were performed in both cases. I'm not sure that convergence > was achieved in either case. Does search_size ever affect the number of > iterations? 20000 is the default for search_size When using random portfolios, search_size is precisely that, how many portfolios to test. You need to make sure to set your feasible weights in generatesequence to make sure you have search_size unique portfolios to test, typically by manipulating the 'by' parameter to select something smaller than .01 (I often use .002, as .001 seems like overkill) When using DE, search_size is decomposed into two other parameters which it interacts with, NP and itermax. NP, the number of members in each population, is set to cap at 2000 in DEoptim, and by default is the number of parameters (assets/weights) *10. itermax, if not passed in dots, defaults to the number of parameters (assets/weights) *50. This is the source of DE stopping at 1550 generations in your example (31*50). You've actually tested 20000 portfolios, using larger populations in each generation. you can pass itermax in dots to get a larger number of generations. You need to understand that there is quite a lot of interaction going on here. In DE, the rule of thumb is to make each population contain ten times the number of members as you have parameters, sometimes 5x is enough for portfolio problems, sometimes not. 20000/310 would only give 64 generations, which is almost certainly not enough. 20000/1550 only gives ~12 population members, which probably doesn't give enough opportunities to mutate/converge. 31*10*1550=480500, which is likely too many, but I don't know your utility function well enough to say that definitively. This brings me full circle to the utility of random portfolios, as pointed out years ago by Pat Burns and others. You can use a (small) finite set of random portfolios to gain an intuition for your utility function, and even to gain a perfectly close approximation of the 'true' optimal portfolio (certainly within the bounds of your estimation error!), only resorting to the global optimizer when you want to get even closer, or if your examination of the random portfolio output indicates that the feasible space is so non-smooth that you need the mutation properties of the global optimizer to help you out. Regards, - Brian _______________________________________________ [hidden email] 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. |
In reply to this post by John P. Burkett
On Sun, 2011-08-07 at 18:35 -0400, John P. Burkett wrote:
> Brian, > > Thanks for your lucid explanations of how PortfolioAnalytics works. I > have no objections to you forwarding your replies to the list. My > comments and questions are inserted below. > > Brian G. Peterson wrote: > > I think your questions and my answers would be of general interest to > > those on the list. If you don't object, I'd like to forward my relies > > on to the list as well. > > > > [comments in-line below] > > > > Regards, > > > > - Brian > > > > On Sat, 2011-08-06 at 18:19 -0400, John P. Burkett wrote: > >> Brian, > >> > >> Thank you again for your script and thoughtful comments. After running > >> the script and trying some variations, I have a few questions about the > >> optimize.portfolio function and its output. > >> > >> When optimize_method='random', I suppose a user assesses convergence (or > >> at least the practical value of the output) by increasing search_size > >> and observing what if anything happens to the objective function value > >> and the weights. Is that correct? > > > > Yes, this is correct. > > > > Random portfolios, with any set of objectives and constraints, let you > > strictly bound the amount of computing power you're going to apply to a > > given problem, tinker with your objective, etc, before devoting more > > computing time to getting to the 'true' blobal objective. > > > > One major use that I have for random portfolio evaluations is to show me > > the feasible space. If trace=TRUE, there should be values in the > > objective value output that can be sent to plot() methods. > > > > Actually, there are a set of chart.* functions dispatched by plot(), > > > > plot -> plot.optimize.portfolio -> plot.optimize.portfolio.random -> > > charts.RP -> chart.Scatter.RP&chart.Weights > > > > All this is covered in the documentation, at least peripherally, but the > > various chart.* functions can be called directly as well. > > > > Another related function you may wish to examine is extractStats(). > > this will take the object output by optimize.portfolio() and pull out > > the weights and objective measured in a tabular (data.frame) format. > > > >> When optimize_method='DEoptim', the user may have some opportunities to > >> adjust DEoptim's default choices for the arguments of the package's > >> functions. My original frustration with DEoptim was that the default > >> choices were not producing convergence in reasonable time and I was > >> uncertain about what alternative choices might hasten convergence. > >> PortfolioAnalytics (PA) provides a nice wrapper for DEoptim but still > >> leaves me wondering about function arguments and their effects on > >> convergence. In particular, the following questions occur to me: > >> 1. What choices does PA make by default for the DEoptim arguments called > >> F, itermax, VTR, relto1, stepto1, NP, and strategy? Can a user of PA > >> override the defaults for these arguments? > > > > Internally, we make a call to DEoptim.control. The user may pass any > > parameters in dots (...) to the optimize.portfolio command that they > > wish to pass on to the optimization engine. For DEoptim, we now use by > > default: > > > > if(!hasArg(strategy)) DEcformals$strategy=6 > > # use DE/current-to-p-best/1 > > > > if(!hasArg(reltol)) DEcformals$reltol=.000001 > > # 1/1000 of 1% change in objective is significant > > > > if(!hasArg(steptol)) DEcformals$steptol=round(N*1.5) > > # number of assets times 1.5 tries to improve > > > > if(!hasArg(c)) DEcformals$c=.4 > > # JADE mutation parameter, this could maybe use some adjustment > > > > I've found these parameters to speed convergence by about an order of > > magnitude on portfolio problems of 100-300+ assets over the default > > DEoptim parameters, though as indicated by the code comment, I think > > that the 'c' parameter could still use some adjustment. > > > > I'll also note that we're using JADE adaptive DE by default in > > PortfolioAnalytics because I have found it to converge so much faster > > than the classical DE algorithms. Much of the work on adding JADE to > > DEoptim (Joshua Ulrich wrote all that code) was motivated by interest in > > using it for portfolio optimization. DEoptim can apply the parameter > > self-adaptive properties of JADE to any strategy= parameter, not just > > strategy 6 DE/current-to-p-best/1, though I believe this to be the best > > strategy for these types of problems. > > > >> 2. Can a PA user obtain information about why iterations stopped? > > > > Most likely reltol and steptol. The default reltol is why I multiplied > > your objective by 1000 in the script that I sent, and steptol sometimes > > needs to be increased as well. > > When examining output from optimization packages I usually look for a > statement about whether iteration stopped because convergence criteria > had been satisfied or because iterations had hit a limit. PA does not > seem to include such a statement in the default output. I imagine that > a user with some effort can generally figure out what happened. An > automatic warning in cases of non-convergence might save some users from > mistakenly assuming convergence. With a problem needing global optimization, there's not really a good way for the optimizer to know whether it has succeeded if the global optima is not known. In many problems, you will know where the global minima lies, thus the VTR parameter. When the true global minima is not known, random portfolios can help. If you run some large number (20,000 should be enough) with a fine-grained enough by= parameter for generatesequence, you can examine the minimum attained via the random portfolios. The true global minimum will likely be only slightly smaller than the minima returned by your random portfolios, and will also likely be insigificantly different given real-money investment constraints and estimation error. DEoptim will give a little information if reltol or steptol are reached, we could examine providing more feedback to the user.' > > > >> 3. How does search_size affect the DEoptim arguments? I tried > >> increasing search_size from 10,000 to 20,000 but noted that 1550 > >> 'iterations' were performed in both cases. I'm not sure that convergence > >> was achieved in either case. Does search_size ever affect the number of > >> iterations? > > > > 20000 is the default for search_size > > > > When using random portfolios, search_size is precisely that, how many > > portfolios to test. You need to make sure to set your feasible weights > > in generatesequence to make sure you have search_size unique portfolios > > to test, typically by manipulating the 'by' parameter to select > > something smaller than .01 (I often use .002, as .001 seems like > > overkill) > > > > When using DE, search_size is decomposed into two other parameters which > > it interacts with, NP and itermax. > > > > NP, the number of members in each population, is set to cap at 2000 in > > DEoptim, and by default is the number of parameters (assets/weights) > > *10. > > > > itermax, if not passed in dots, defaults to the number of parameters > > (assets/weights) *50. This is the source of DE stopping at 1550 > > generations in your example (31*50). > > That's important information. Evidently, I'd need to raise itermax to > attain convergence. Possibly. Is there a value that signifies convergence in this objective function? > > You've actually tested 20000 > > portfolios, using larger populations in each generation. you can pass > > itermax in dots to get a larger number of generations. You need to > > understand that there is quite a lot of interaction going on here. In > > DE, the rule of thumb is to make each population contain ten times the > > number of members as you have parameters, sometimes 5x is enough for > > portfolio problems, sometimes not. 20000/310 would only give 64 > > generations, which is almost certainly not enough. 20000/1550 only gives > > ~12 population members, which probably doesn't give enough opportunities > > to mutate/converge. 31*10*1550=480500, which is likely too many, but I > > don't know your utility function well enough to say that definitively. > > > > The cases we've examined seem to fit the equation search_size = > itermax*NP. Are there exceptions? If a user specifies any two of the > three variables, will PA derive the third? If a user specifies values > for all three variables but violates the equation, does PA change one > variable, report an error, or what? We default to this: NP = round(search_size/itermax) > It seems reasonable to me to set NP = 10*(number of parameters) and > itermax = 50*(number of parameters). Those settings and the equation > above imply search_size = 500*(number of parameters)^2. As you point > out, in the case of 31 parameters, the calculation yields search_size = > 480500, a quantity which you say "is likely too many." Not sure whether > it is too many in the sense of being larger than necessary to attain > convergence or in the sense of being too large to be processed in > acceptable time, I tried running the following code: > DEResult <- optimize.portfolio(R=returns, constraints=Util_constr, > optimize_methods='DEoptim', search_size=480500, NP=310, intermax=1550, > trace=TRUE, verbose=FALSE, steptol=100). So far it has been running for > 6 hours and 13 minutes. I'll be interested to see when it stops and > for what reason. See above for a recommendation to test with a finite number of random portfolios first. > Best regards, > John > > > > > This brings me full circle to the utility of random portfolios, as > > pointed out years ago by Pat Burns and others. You can use a (small) > > finite set of random portfolios to gain an intuition for your utility > > function, and even to gain a perfectly close approximation of the 'true' > > optimal portfolio (certainly within the bounds of your estimation > > error!), only resorting to the global optimizer when you want to get > > even closer, or if your examination of the random portfolio output > > indicates that the feasible space is so non-smooth that you need the > > mutation properties of the global optimizer to help you out. > > > > Regards, > > > > - Brian > > > > > > > > -- Brian G. Peterson http://braverock.com/brian/ Ph: 773-459-4973 IM: bgpbraverock _______________________________________________ [hidden email] 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. |
In reply to this post by braverock
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: [hidden email] >>>>>> [mailto:[hidden email]] Im Auftrag von >>>>>> John P. Burkett >>>>>> Gesendet: Montag, 1. August 2011 18:49 >>>>>> An: [hidden email] >>>>>> 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 >> >> _______________________________________________ >> [hidden email] 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 _______________________________________________ [hidden email] 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. |
I am looking to install rjava 0.8-8 or earlier to use RBloomberg, in windows and having trouble to build one. Is there any place I can download the prebuilt one? thanks. [[alternative HTML version deleted]] _______________________________________________ [hidden email] 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. |
Powered by Nabble | Edit this page |