In this paper, a new semi-definite programming approach is devised for approximating nonlinear estimation problems. The main idea is to include the noise components as parameters of interests, which increases the flexibility in the convex optimization formulation. Using the source localization as an illustration, we develop semi-definite relaxation (SDR) positioning algorithms using angle-of-arrival, time-of-arrival and time-difference-of-arrival measurements. Numerical examples are included to show the effectiveness of the proposed SDR approach.