A novel robust predictive control algorithm is presented for uncertain discrete-time input-saturated linear systems described by structured norm-bounded model uncertainties. The solution is based on the minimization, at each time instant, of a semi-definite convex optimization problem subject to a number of LMI feasibility constraints which grows up only linearly with the control horizon length N. The general case of arbitrary N is considered. Closed-loop stability and feasibility retention over the time are proved and comparisons with robust multi-model (polytopic) MPC algorithms are reported. (C) 2004 Elsevier Ltd. All rights reserved.