Optimal preconditioning and iteration complexity bounds for gradient-based optimization in model predictive control

In this paper, optimization problems arising in model predictive control (MPC) and in distributed MPC are solved by applying a fast gradient method to the dual of the MPC optimization problem. Although the development of fast gradient methods has improved the convergence rate of gradient-based methods considerably, they are still sensitive to ill-conditioning of the problem data. Since similar optimization problems are solved several times in the MPC controller, the optimization data can be preconditioned offline to improve the convergence rate of the fast gradient method online. A natural approach to precondition the dual problem is to minimize the condition number of the Hessian matrix. However, in MPC the Hessian matrix usually becomes positive semi-definite only, i.e., the condition number is infinite and cannot be minimized. In this paper, we show how to optimally precondition the optimization data by solving a semidefinite program, where optimally refers to the preconditioning that minimizes an explicit iteration complexity bound. Although the iteration bounds can be crude, numerical examples show that the preconditioning can significantly reduce the number of iterations needed to achieve a prespecified accuracy of the solution.