In this paper, we consider linear time invariant (LTI) systems with parameter uncertainty. For such systems, we present global optimization techniques to determine permissible perturbations of the parameters of the system that maintain stability (the so-called parameter stability margins), for cases in which the coefficients of the characteristic equation of the system are polynomial functions of the uncertain parameters. The parameter uncertainty domains for maintaining stability are characterized as hypersolids, defined with respect to l(p)-norms for various values of p is an element of (1,infinity). Algorithms are devised based on the reformulation-linearization/convexification technique (RLT) in concert with branch-and-bound methods to solve the underlying parametric non-convex subproblems for computing the stability margins. Several illustrative examples are solved to demonstrate the efficacy of the proposed approach towards producing global optimal solutions. We also present comparative computational experience with the commercial global optimizer BARON.