This paper addresses the problem of designing fixed-order output feedback controllers and tuning parameters for reducing the instability of linear time-invariant (LTI) systems. Specifically, continuous-time (CT) and discrete-time (DT) LTI systems are considered, whose coefficients are rational functions of design parameters that are searched for in a given semi-algebraic set. Two instability measures are considered, the first defined as the spectral abscissa (CT case) or the spectral radius (DT case), and the second defined as the sum of the real parts of the unstable eigenvalues (CT case) or the product of the magnitudes of the unstable eigenvalues (DT case). Two sufficient conditions are given for establishing either the non-existence or the existence of design parameters that reduce the considered instability measure under a desired value. These conditions require to solve a semidefinite program (SDP), which is a convex optimization problem, and to find the roots of a multivariate polynomial, which is a difficult problem in general. To overcome this difficulty, a technique based on linear algebra operations is exploited, which easily provides the sought roots in common cases by taking into account the structure of the polynomial under consideration. Also, it is shown that these conditions are also necessary by increasing enough the size of the SDP under some mild assumptions. Lastly, it is explained how the proposed methodology can be used to search for design parameters that minimize a given cost function while reducing the instability.