Lyapunov's 2nd method can be formulated as a convex optimization problem by means of Sum-of-Squares (SOS) optimization. This gives a powerful tool for robust stability analysis of nonlinear systems. The use of SOS optimization is limited to small dynamical systems, because of the demanding numerical complexity underlying SOS optimization. For systems where scaling of SOS is a concern, diagonally dominant SOS (DSOS) is a possible alternative. DSOS approximates the SOS problem from within and results in a less complex optimization problem. The shortcoming of DSOS, however, is conservatism within the robust stability analysis, entailed by the approximation. In this thesis, we consider the problem of conservatism in robust stability analysis due to the application of DSOS. We propose new DSOS-based formulations which aim to reduce conservatism in robust stability analysis. Furthermore, we show how to formulate optimization problems which don't require an initial Lyapunov function candidate, and stabilize the numerical solutions of the DSOS problems. The main tool we leverage in this study is the Positivstellensatz in combination with DSOS. We demonstrate the proposed formulations on three numerical experiments. We estimate the region of attraction of the van der Pol oscillator, investigate stability of an uncertain nonlinear system and proof stability of a nonlinear system, which is documented to suffer from numerical issues when approached with SOS methods. The results show a reduction in conservatism and improvement in numerical robustness when compared to the DSOS formulation found in literature.