We present a new approach for the construction of lower bounds for the inf-sup stability constants required in a posteriori error analysis of reduced basis approximations to affinely parametrized partial differential equations. We combine the ``linearized'' inf-sup statement of the natural-norm approach with the approximation procedure of the Successive Constraint Method (SCM): the former (natural-norm) provides an economical parameter expansion and local concavity in parameter-a small(er) optimization problem which enjoys intrinsic lower bound properties; the latter (SCM) provides a systematic optimization framework a Linear Program (LP) relaxation which readily incorporates continuity and stability constraints. The natural-norm SCM requires a parameter domain decomposition: we propose a greedy algorithm for selection of the SCM control points as well as adaptive construction of the optimal subdomains. The efficacy of the natural-norm SCM is illustrated through numerical results for two types of non-coercive problems: the Helmholtz equation (for acoustics, elasticity, and electromagnetics), and the convection-diffusion equation. (C) 2010 Elsevier B.V. All rights reserved.