In the multi-GNSS era, the observable satellites are more than needed and the benefit of processing more than enough satellites is marginal. It is thus desired to select a subset of satellites so that the receiver operation complexity and navigation performance can be balanced. In the paper, performance requirements in navigation accuracy and integrity are represented in terms of a performance index and the performance-based satellite selection is to determine the satellite combination to minimize the performance index. A linear matrix inequality (LMI) relaxation approach is developed to solve the problem and render candidates of satellites. The proposed approach quantifies the significance of each satellite on the resulting performance metric and, more importantly, provides a lower bound in satellite selection for performance-based navigation. The generalizations of the proposed approach in multi-epoch satellite selection is also discussed. Examples are provided to illustrate the effectiveness of the proposed approach.