  Optimizing a high-dimensional non-convex function is, in general,
computationally hard and many problems of this type are hard to solve even
approximately. Complexity theory characterizes the optimal approximation ratios
achievable in polynomial time in the worst case. On the other hand, when the
objective function is random, worst case approximation ratios are overly
pessimistic. Mean field spin glasses are canonical families of random energy
functions over the discrete hypercube $\{-1,+1\}^N$. The near-optima of these
energy landscapes are organized according to an ultrametric tree-like
structure, which enjoys a high degree of universality. Recently, a precise
connection has begun to emerge between this ultrametric structure and the
optimal approximation ratio achievable in polynomial time in the typical case.
A new approximate message passing (AMP) algorithm has been proposed that
leverages this connection. The asymptotic behavior of this algorithm has been
analyzed, conditional on the nature of the solution of a certain variational
problem.
  In this paper we describe the first implementation of this algorithm and the
first numerical solution of the associated variational problem. We test our
approach on two prototypical mean-field spin glasses: the
Sherrington-Kirkpatrick (SK) model, and the $3$-spin Ising spin glass. We
observe that the algorithm works well already at moderate sizes ($N\gtrsim
1000$) and its behavior is consistent with theoretical expectations. For the SK
model it asymptotically achieves arbitrarily good approximations of the global
optimum. For the $3$-spin model, it achieves a constant approximation ratio
that is predicted by the theory, and it appears to beat the `threshold energy'
achieved by Glauber dynamics. Finally, we observe numerically that the
intermediate states generated by the algorithm have the properties of ancestor
states in the ultrametric tree.
