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

[Lui ##]

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!

@ Daniel & Dave: Thank you very much for your links! The paper is
really great and I have already started implementing the DE
algorithm... Do you have any experience with the parameters with
respect to PF optimization? The portfolio I am looking at is quite
large (400+ stocks) and the algorithm is converging quite slowly (e.g.
for the minimum risk portfolio). I tried NP = 6000, iterations at
2000.

@Pat: Thank you very much for the link! I will take a look at it after
"playing around with GAs and DEs a little". The reason is that I
currently have a quadratic program and quadratic constraints but the
constraints might become a little bit "ugly" (hold portfolio turnover
in a certain range, assets from certain asset classes should only have
a certain weight,...), so I want to be a little bit flexible...

@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? I tried
to get Rscop run but had problems installing the library. The solvers
for linear problems and quadratic constraints as described in the
fPortfolio package did not work out the way I wanted them either
(there were some threads in R-Sig-Finance on that topic... 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

@Ulrich: Thanks for the link! I see that genoud was used here - do you
have any suggestions in terms of penalty functions for portfolio
problems?


Just to give you an overview on what I am trying to achieve:

I am working on an investment strategy and want to compare it to
Markowitz (with the risk level being the same...) Therefore I am
currently trying implement Markowitz with GAs or Deoptim. I found
going the "dirty" way in solving min w x Cov x w' with a target return
saves me the pain from quadratic constraints but leaves me with many
points on the efficient frontier to calculate - if I want to find an
optimal E(r) for a given sigma (which I currently find most suitable,
as both portfolios should have the same risk). That approach is not
very "lean" and nice. My investment strategy leaves me (in the
simplest form) with a quadratic problem (and the quadratic constraints
still remain - since I am interested in the Variance).
As there is lots of "try and try again" I appreciate the flexibility
of "more general complex problem solvers" as the problem may get more
complex with the constraints.

I currently face the problem that the target sigma I want to achieve
is kind of far from what the algorithms give me... I suspect the
penalty function is the "problem". Do you have suggestions for good
penalty function?
I already "cut out" the sum(w) = 1 constraint by adding w <- w /
sum(w) (see DEoptim paper). Currently, my penalty function looks like
this:

return <- return(w)
variance <- variance (w)

penalty_faktor = 20
penalty <- max((variance - targetvariance)/targetvariance,0)
	
if (((variance - targetvariance)/targetvariance) < 0.1){
	penalty_faktor = 1
	penalty = 0
	}
		

	ret <-  (penalty*100)^penalty_faktor - return

I dont care so much if the true variance is little bigger (10%) and
found if-then routines "spitting" out 99999 values if the constraints
are not met to be very inefficient... If somebody has suggestions for
good penalty function - please let me know!

Have a great weekend!
Lui
On Sun, Jan 23, 2011 at 5:32 PM, ArdiaD <david.ardia at unifr.ch> wrote:
> This might be of interest:
> http://papers.ssrn.com/sol3/papers.cfm?abstract_id=1584905
> Regards
> Dave
>
> On 01/23/2011 11:23 PM, Ulrich Staudinger wrote:
>> Lui,
>>
>> you can also have a look at
>> http://aqr.activequant.org/index.php/2010/08/genetically-optimizing-a-trading-system/for
>> inspiration on how to genetically optimize a trading system, whether
>> it's quadratic or not. It's just some snipplet but exemplifies it pretty
>> well ...
>>
>> Regards,
>> Ulrich
>>
>>
>> On Sun, Jan 23, 2011 at 11:15 PM, Guillaume Yziquel <
>> guillaume.yziquel at citycable.ch> wrote:
>>
>>> 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
>>>
>>> _______________________________________________
>>> R-SIG-Finance at r-project.org mailing list
>>> https://stat.ethz.ch/mailman/listinfo/r-sig-finance
>>> -- Subscriber-posting only. If you want to post, subscribe first.
>>> -- Also note that this is not the r-help list where general R questions
>>> should go.
>>>
>>
>>
>
> _______________________________________________
> R-SIG-Finance at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-sig-finance
> -- Subscriber-posting only. If you want to post, subscribe first.
> -- Also note that this is not the r-help list where general R questions should go.
>