We present a new approach to a class of non-convex LMI-constrained problems in robust control theory. The problems we consider may be recast as the minimization of a linear objective subject to linear matrix inequality (LMI) constraints in tandem with non-convex constraints related to rank deficiency conditions. We solve these problems using an extension of the augmented Lagrangian technique. The Lagrangian function combines a multiplier term and a penalty term governing the non-convex constraints. The LMI constraints, due to their special structure, are retained explicitly and not included in the Lagrangian. Global and fast local convergence of our approach is then obtained either by an LMI-constrained Newton type method including line search or by a trust-region strategy. The method is conveniently implemented with available semi-definite programming (SDP) interior-point solvers. We compare its performance to the well-known D - K iteration scheme in robust control. Two test problems are investigated and demonstrate the power and efficiency of our approach.