There are lots of geophysical problems that include computationally expensive functions (forward models). Polynomial chaos (PC) expansion aims to approximate such an expensive equation or system with a polynomial expansion on the basis of orthogonal polynomials. Evaluation of this expansion is extremely fast because it is a polynomial function. This property of the PC expansion is of great importance for stochastic problems, in which an expensive function needs to be evaluated thousands of times. We have developed PC expansion as a novel technique to solve nonlinear geophysical problems. To better evaluate the methodology, we use PC expansion for automating the velocity analysis. For this purpose, we define the optimally picked velocity model as an optimizer of a variational integral in a semblance field. However, because computation of a variational integral with respect to a given velocity model is rather expensive, it is impossible to use stochastic methods to search for the optimal velocity model. Thus, we replace the variational integral with its PC expansion, in which computation of the new function is extremely faster than the original one. This makes it possible to perturb thousands of velocity models in a matter of seconds. We use particle swarm optimization as the stochastic optimization method to find the optimum velocity model. The methodology is tested on synthetic and field data, and in both cases, reasonable results are achieved in a rather short time.