Four-dimensional variational data assimilation in meteorology and oceanography suffers from the presence of local minima in the cost function. These local minima arise when the system under study is strongly nonlinear. The number of local minima further dramatically increases with the length of the assimilation period and often renders the solution to the problem intractable. Global optimization methods are therefore needed to resolve this problem. However, the huge computational burden makes the application of these sophisticated techniques unfeasible for large variational data assimilation systems. In this study, a Simulated Annealing (SA) algorithm, complemented with an order-reduction of the control vector, is used to tackle this problem. SA is a very powerful tool of combinatorial minimization in the presence of several local minima at the cost of increasing the execution time. Order-reduction is then used to reduce the dimension of the search space in order to speed up the convergence rate of the SA algorithm. This is achieved through a proper orthogonal decomposition. The new approach was implemented with a realistic eddy-permitting configuration of the Massachusetts Institute of Technology general circulation model (MITgcm) of the tropical Pacific Ocean. Numerical results indicate that the reduced-order SA approach was able to efficiently reduce the cost function with a reasonable number of function evaluations.