Bounding Computational Complexity under Cost Function Scaling in Predictive Control

We present a framework for upper bounding the number of iterations required by first-order optimization algorithms implementing constrained LQR controllers. We derive new bounds for the condition number and extremal eigenvalues of the primal and dual Hessian matrices when the cost function is scaled...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-02
Main Authors: McInerney, Ian, Kerrigan, Eric C, Constantinides, George A
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Computation
Controllers
Cost function
Deviation
Eigenvalues
Hessian matrices
Horizon
Mathematical analysis
Matrix methods
Predictive control
Transfer functions
Weight
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We present a framework for upper bounding the number of iterations required by first-order optimization algorithms implementing constrained LQR controllers. We derive new bounds for the condition number and extremal eigenvalues of the primal and dual Hessian matrices when the cost function is scaled. These bounds are horizon-independent, allowing for their use with receding, variable and decreasing horizon controllers. We considerably relax prior assumptions on the structure of the weight matrices and assume only that the system is Schur-stable and the primal Hessian of the quadratic program (QP) is positive-definite. Our analysis uses the Toeplitz structure of the QP matrices to relate their spectrum to the transfer function of the system, allowing for the use of system-theoretic techniques to compute the bounds. Using these bounds, we can compute the effect on the computational complexity of trading off the input energy used against the state deviation. An example system shows a three-times increase in algorithm iterations between the two extremes, with the state 2-norm decreased by only 5% despite a greatly increased state deviation penalty.
ISSN:2331-8422