On the codimension of the set of optima: large scale optimisation with few relevant variables

The complexity of continuous optimisation by comparison-based algorithms has been developed in several recent papers. Roughly speaking, these papers conclude that a precision $$\epsilon $$ can be reached with cost $$\varTheta n\log 1/\epsilon $$ in dimension n within polylogarithmic factors for the sphere function. Compared to other non comparison-based algorithms, this rate is not excellent; on the other hand, it is classically considered that comparison-based algorithms have some robustness advantages, as well as scalability on parallel machines and simplicity. In the present paper we show another advantage, namely resilience to useless variables, thanks to a complexity bound $$\varTheta m\log 1/\epsilon $$ where m is the codimension of the set of optima, possibly $$m << n$$. In addition, experiments show that some evolutionary algorithms have a negligible computational complexity even in high dimension, making them practical for huge problems with many useless variables.