[R-SIG-Finance] Genetic Algorithms & Portfolio Optimization

[Guillaume Yziquel]

Le Sunday 23 Jan 2011 à 15:56:40 (-0600), Brian G. Peterson a écrit :
> On Saturday, January 22, 2011 04:33:09 pm Lui ## wrote:
> > Dear group,
> > 
> > I was just wondering whether some of you have some experience with the
> > package "rgenoud" which does provide genetic algorithms for complex
> > optimization problems. 
> 
> <...>
> 
> > What is your general experience? Did you ever try solving the
> > Markowitz portfolio with the rgenoud package?
> > I know that there are good solvers around for the qudratic programming
> > problem of the markowitz portfolio, but I want to go into a different
> > direction which translates into a quadratic problem with quadratic
> > constraints (and I havent found a good solver for that...).
> > 
> > I am interested in your replies! Have a good weekend!
> 
> As others have already said, for a quadtratic problem with quadratic 
> constraints, there is an exact analytical solution.

I wouldn't qualify dual interior point methods as an "exact" solution, but,
yes, that's the basic idea: they're better suited for that.
 
> In these cases, you will be much better off both from a performance and 
> accuracy perspective in using a quadratic solver (quadprog is most often 
> applied in R, see list archives and many packages for examples).

Is quadprog a second-order cone programming solver? If that is the case,
yes, it probably solves quadratic objective function with quadratic
constraints faster and with more accuracy than a full-fledged SDP
solver.

> Other portfolio problems may be stated in terms of linear solvers, which will 
> likewise be faster than a global optimizer for finding an exact analytical 
> solution.
> 
> If, however, your portfolio problem is non-convex and non-smooth, then a 
> genetic algorithm, a migration algorithm, grid search, or random portfolios 
> may be a good option for finding a near-optimal portfolio.  If this is your 
> true goal, perhaps you can say a little more about your actual constraints and 
> objectives (and use assets that are outside of your true area of interest, 
> such as the S&P sector indices).

Yes, the problem structure often gives good insight as to which method
to apply. It may be noted, however, that quite a lot of non-convex
problems may be transformed into convex ones. And using some relaxation
methods, you can often use SDPs to optimise multivariate polynomial
objective under multivariate polynomial constraints, without too many
convexity hypothesis.

SDPs are not always easy to manipulate, but they do solve a broad range
of optimisation problems.

> Regards,
> 
>   - Brian 

Best regards,

-- 
     Guillaume Yziquel
http://yziquel.homelinux.org