ϵ Suboptimality Based Early Stop in Dual Decomposition for Model Predictive Control

Dual decomposition is an efficient tool in dealing with Model Predictive Control (MPC) problems, particularly for distributed MPC. In this paper, we propose to limit the iteration number required in solving that problem, by stopping the iterative process once the solution is close enough to the optimal one. To do so, we introduce the concepts of primal and dual suboptimality, and derive respectively the projection and stopping condition for them. By exploiting the particular structure of the MPC problem where only the first step inputs are applied to the system, we devise an early ϵ suboptimality stopping condition, focusing on components only at the first step of the prediction horizon, thus to further reduce the iteration number needed. Beyond the theoretical proofs that are developed, we illustrate the method's efficiency, both in computation time and iteration number, by various simulations