Sharpe's algorithm for portfolio improvement
[comments inline]
-----Urspr?ngliche Nachricht----- Von: Brian G. Peterson [mailto:brian at braverock.com] Gesendet: Dienstag, 2. August 2011 14:37 An: Enrico Schumann Cc: 'John P. Burkett'; R-SIG-Finance at r-project.org 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