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

[Guillaume Yziquel]

Le Monday 24 Jan 2011 à 00:23:14 (-0500), Lui ## a écrit :
> First of all: Thank you very much everybody for the vast number of
> replies! I really appreciate your help! I didn't expect so many
> responses!
> 
> @ Guillaume Yziquel: Thank you very much for your quick responses and
> keeping track of the answers! I have to admit that I know very little
> about SDPs, so please excuse my stupid question: am I able to solve
> the Markowitz portfolio (at given risk, so w x Cov x w' with target
> function w x E(r)) ? Especially when my covariance matrix is changing
> and I need to have an optimizer that just uses the vektor E(r) and the
> matrix (Cov) as Input. Is that still possible when the my target
> function (maximize) is also in a quadratic form ( e.g. w x MATRIX x w)
> - without having to transform the problem manually? Thanks again for
> your great help!

Suppose you have to maximise some quadratic objective f(x), where x are
multivariate variables. Introduce another 'free' variable h.

Then, maximising f(x) under constraints C(x) is the same as maximising h
under the constraints C(x) and h <= f(x).

That's a simple relaxation method allowing you to convert a quadratic
objective into a linear objective by introducing a free relaxation
variable.

As to how to formulate your problem into an SDP, there is literature on
the web about that. Do not have any links handy, but google for Schur
complement along with semidefinite programming and relaxation.

More suited mailing-lists for these questions may be the one for CVXOPT,
Coinor mailing lists such as for IPOPT, and generally mailing lists for
SDPs solvers. For your specific case, I'd google for second-order cone
programming.
 
> @Brian: I actually had troubles finding a solver for quadratic
> problems and quadratic constraints. I think quadprog was intended for
> quadratic problems with linear constraints or am I mistaken?

As mentioned earlier, add a free variable, and your quadratic objective
becomes a linear objective.

> But as my
> constraints will probably get more complex, or I will want to try out
> new ideas quickly I think I will go with the GAs/DEs first (unless you
> have a good recommendation for a flexible / easy to modify solver that
> is even aimed a little at portfolio problems

You have a tradeoff between speed/accuracy and flexibility.

Depends what your constraints really are. Quadratic? Use second-order
cone programming. Multivariate polynomials? Use semi-definite
programming. Some convex constraints, or quasi-convex, or can be turned
into convex constraints? Interior-point methods (IPOPT, for instance)?
Anything else? Well, DEOptim, GAs, simulated annealing or whatever you
find experimentally handy.

Best regards,

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