One of the most fundamental problems in model predictive control (MPC) is the lack of guaranteed stability and feasibility. It is shown how Farkas' Lemma in combination with bilevel programming and disjoint bilinear programming can be used to search for problematic initial states which lack recursive feasibility, thus invalidating a particular MPC controller. Alternatively, the method can be used to derive a certificate that the problem is recursively feasible. The results are initially derived for nominal linear MPC, and thereafter extended to the additive disturbance case. (C) 2011 Elsevier Ltd. All rights reserved.