The Phase-Locked Loop(PLL) is a key component of modern electronic communication and control systems. PLL is designed to extract signals from transmission channels. It plays an important role in systems where it is required to estimate the phase of a received signal, such as carrier tracking from global positioning system (GPS) satellites. In order to robustly provide centimeter-level accuracy, it is crucial for the PLL to estimate the instantaneous phase of an incoming signal which is usually buried in random noise or some type of interference. This paper presents an approach that utilizes the recent development in the semi-definite programming and sumof-squares (SOS) field. A Lyapunov function will be searched as the certificate of the lock-in region of the PLL system. Moreover, the polynomial design technique will be used to further refine the controller parameters for system response away from the equilibrium point. Various simulation results will be provided to show the effectiveness of this approach.