Skip to content

Genetic Algorithms & Portfolio Optimization

12 messages · Lui ##, Guillaume Yziquel, Brian G. Peterson +3 more

Original
Lui ##
# 
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. How did you efficiently solve the constraints
(sum of all weights <1, variance < target)? Setting the solution
"infeasible" through if-clauses did not seem to be so promising ...
The example below shows what I mean:

(penalty-term)

if (variance > targetvariance){
penatly = -999999
}

"result" is to be maximized, the variance should not exceed a certain
threeshold. To me, it seemed much better to add a penalty term like

penalty = ( (abs(variance-targetvariance)/targetvariance)*100)^50

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!

Lui
Guillaume Yziquel
# 
Le Saturday 22 Jan 2011 ? 17:33:09 (-0500), Lui ## a ?crit :
Any semidefinite programming solver should do the trick for quadratic 
problem with quadratic constraints. I suggest you have a look at SDPA, 
but there a lot of such solvers available if you look well.

(Well not every quadratic constraints, but reasonable ones, yes.)

The trick is how you get to reformulate your problem into a semidefinite
one. SDPs may not be the fastest solver for your problem if it has a 
specific structure, but as a general solution or prototype, it works,
and is
adequately fast.

But I'm not so sure as what is available in R for SDPs.
Guillaume Yziquel
# 
Le Saturday 22 Jan 2011 ? 23:52:36 (+0100), Guillaume Yziquel a ?crit :
Just had a look at the following webpage:

http://cran.r-project.org/web/views/Optimization.html

You have an R binding for CSDP:

http://cran.r-project.org/web/packages/Rcsdp/index.html

Best regards,
Brian G. Peterson
#
On Saturday, January 22, 2011 04:33:09 pm Lui ## wrote:
<...>
As others have already said, for a quadtratic problem with quadratic 
constraints, there is an exact analytical solution.

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).

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).

Regards,

  - Brian
Guillaume Yziquel
# 
Le Sunday 23 Jan 2011 ? 15:56:40 (-0600), Brian G. Peterson a ?crit :
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.
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.
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.
Best regards,
ArdiaD
# 
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 ##
# 
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:
Guillaume Yziquel
# 
Le Monday 24 Jan 2011 ? 00:23:14 (-0500), Lui ## a ?crit :
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.
As mentioned earlier, add a free variable, and your quadratic objective
becomes a linear objective.
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,
Lui ##
# 
@Brian: Sorry, I realized a little bit too late that you are also
involved in developing DEoptim. Thanks a lot for this great tool!

@Daniel: Thanks :-)

2011/1/24 Daniel Cegie?ka <daniel.cegielka at gmail.com>: