Superposition of plane waves in high spatial dimensions: From landscape complexity to the deepest minimum value

In this article, we introduce and analyze some statistical properties of a class of models of random landscapes of the form H(x)=μ2x2+∑l=1Mϕl(kl⋅x),x∈RN,μ>0 where both the functions ϕl(z) and vectors kl are random. An important example of such landscape describes superposition of M plane waves with random amplitudes, directions of the wavevectors, and phases, further confined by a parabolic potential of curvature μ. Our main efforts are directed toward analyzing the landscape features in the limit N → ∞, M → ∞ keeping α = M/N finite. In such a limit we find (i) the rates of asymptotic exponential growth with N of the mean number of all critical points and of local minima known as the annealed complexities and (ii) the expression for the mean value of the deepest landscape minimum (the ground-state energy). In particular, for the latter we derive the Parisi-like optimization functional and analyze conditions for the optimiser to reflect various phases for different values of μ and α: replica-symmetric, one-step and full replica symmetry broken, as well as criteria for continuous, Gardner and random first order transitions between different phases.