The paper describes an efficient method for solving an optimal control problem that arises in robust model-predictive control. The problem is to design the input sequence that minimizes the peak tracking error between the ouput of a linear dynamical system and a desired target output, subject to inequality constraints on the inputs. The system is uncertain, with an impulse response that can take arbitrary values in a given polyhedral set. This problem can be formulated as a robust linear programming problem with structured uncertainty. The presented method is based on Mehrotra’s interior-point method for linear programming, and takes advantage of the problem structure to achieve a complexity that grows linearly with the control horizon, and increases as a cubic polynomial as a function of the system order, the number of inputs, and the number of uncertainty parameters.