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

[Enrico Schumann]

[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