Quantcast

Sharpe's algorithm for portfolio improvement

classic Classic list List threaded Threaded
24 messages Options
12
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Marc Delvaux
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Enrico Schumann
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

alexios
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

braverock
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
>
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Enrico Schumann
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Patrick Burns-2
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

braverock
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Enrico Schumann
[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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

Enrico Schumann
[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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

braverock
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
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

braverock
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

braverock
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Sharpe's algorithm for portfolio improvement

John P. Burkett
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.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

rjava & RBloomberg

Yihao Lu aeolus_lu

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.
12
Loading...