Gaussian mixture model (GMM) is widely used in many applications because it can approximate various forms of probability distributions. In this paper, we are concerned with GMM estimation problem using the variational Bayes (VB) method. In this approach, one can only find local optima because the free energy function of the problem is multimodal. In order to find better solutions, deterministic annealing was recently adapted to the VB method (DAVB method). In this paper, we offer an alternative approach to the DAVB method for GMM estimation problem. We propose a multi-directional search method from the primitive initial point (PIP), which is defined as the solution of the DAVB method at the highest temperature. Investigation on the curvature information of the original (not annealed) free energy function reveals that the PIP is a saddle point. An efficient multi-directional search strategy from the neighborhoods of the PIP is proposed using the eigen-analysis of the Hessian matrix. Numerical experiments using real data sets demonstrate the effectiveness of our method. (C) 2009 Elsevier Ltd. All rights reserved.