The parameter or state estimation with bounded noises is getting increasingly important in many applications of practical systems with some uncertainties. The problem to estimate a deterministic parameter or state which is known to lie in an intersection of some ellipsoids can be formulated to find the Chebyshev center of the intersection set in the case of l(2) norm of the estimation error. In this paper, an appropriate positive semidefinite relaxation of non-convex optimization problem is derived, and then a new algorithm for robust minimax estimation is provided. Some examples are given to compare the approximate estimate with the existing relaxed Chebyshev center. (C) 2013 Elsevier Ltd. All rights reserved.