Evolution on trees: On the design of an evolution strategy for scenario-based multi-period portfolio optimization under transaction costs

Scenario-based optimization is a problem class often occurring in finance, planning and control. While the standard approach is usually based on linear stochastic programming, this paper develops an Evolution Strategy (ES) that can be used to treat nonlinear planning problems arising from Value at Risk (VaR)-constraints and not necessarily proportional transaction costs. Due to the VaR-constraints the optimization problem is generally of non-convex type and its decision version is already NP-complete. The developed ES is the first algorithm in the field of evolutionary and swarm intelligence that tackles this kind of optimization problem. The algorithm design is based on the covariance matrix self-adaptation ES (CMSA-ES). The optimization is performed on scenario trees where in each node specific constraints (balance equations) must be fulfilled. In order to evaluate the performance of the ES proposed, instances of increasing problem hardness are considered. The application to the general case with nonlinear node constraints shows not only the potential of the ES designed, but also its limitations. The latter are basically determined by the high dimensionalities of the search spaces defined by the scenario trees.