Min max MPC based on a graph problem

Min max predictive controllers have a high computational burden. In this work, a polynomial time implementation is presented for linear plants with additive uncertainties and quadratic cost function. The new approach relies on the equivalence of the maximization problem with a min cut graph problem. If a given condition is satisfied, the computational burden is polynomial with the control and prediction horizon, while the original problem has an exponential complexity. A modified controller has been proposed for those systems that do not satisfy the condition required to solve the graph problem in polynomial time. This modified controller can be shown to preserve stability. Simulation examples are presented. The proposed implementation broadens the family of real plants to which a min max MPC control can be applied.