Permuted orthogonal block-diagonal transformation matrices for large scale optimization benchmarking

We propose a general methodology to construct large-scale testbeds for the benchmarking of continuous optimization algorithms. Our approach applies an orthogonal transformation on raw functions that involve only a linear number of operations in order to obtain large scale optimization benchmark problems. The orthogonal transformation is sampled from a parametrized family of transformations that are the product of a permutation matrix times a block-diagonal matrix times a permutation matrix. We investigate the impact of the different parameters of the transformation on its shape and on the difficulty of the problems for separable CMA-ES. We illustrate the use of the above defined transformation in the BBOB-2009 testbed as replacement for the expensive orthogonal (rotation) matrices. We also show the practicability of the approach by studying the computational cost and its applicability in a large scale setting.