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

[Brian G. Peterson]

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