Additive Drift as an Optimization Problem for the (1 + 1)-ES

We present a novel method for constructing a close-to-optimal potential function for drift analysis of evolution strategies and other numerical optimization algorithms. It is based on a piecewise linear ansatz for the potential function, defined by potential values on a discrete grid of states together with a corresponding interpolation scheme. We compute or approximate the algorithm dynamics on the grid and then construct a linear program from expected progress and (weighted) state transitions. The solution of the optimization problem gives rise to parameters of the potential function maximizing (additive) drift. Under mild assumptions, the proceeding yields an arbitrarily close approximation of the optimal potential function at the expense of growing computational demands. As a proof of concept we apply the method to the (1+1) evolution strategy on the two-dimensional sphere function.