I am interested in formulating a discrete finite time constrained LQR in CVXPY.
\begin{align} \text{minimize } J = & \sum_{k=0}^N x'(k)Qx(k) + u'(k)Ru(k) \\\\ \text{subject to } & x(k+1) = Ax(k) + Bu(k) \\\\ & Cx(k) + Du(k) \leq e \end{align}
I came across the batch-approach [1] in a paper solving a similar problem [2]. As I understand it, the method is describing the problem only in terms of the inputs $u$ and initial state $x_0$, which would reduce the total amount of variables in CVXPY in exchange for computing some large matrices beforehand.
\begin{align} \begin{bmatrix} x(0) \\\\ x_1 \\\\ \dots \\\\ \dots \\\\ x_k \end{bmatrix} &= \begin{bmatrix} I \\\\ A \\\\ \dots \\\\ \dots \\\\ A^N \end{bmatrix} x(0) + \begin{pmatrix} 0 & \dots & \dots & 0 \\\\ B & 0 & \dots & 0 \\\\ AB & \ddots & \ddots & \vdots \\\\ \vdots & \ddots & \ddots & \vdots \\\\ A^{N-1}B & \dots & \dots & B \end{pmatrix} \begin{bmatrix} u_0 \\\\ \vdots \\\\ \vdots \\\\ u_{N-1} \end{bmatrix} \\\\ X &= S^x x(0) + S^uU_0 \\\\ \end{align}
So the cost function can be rewritten to be dependent only on $x_0$ and $u$
$$ J(x(0), U_0) = X'\bar{Q}X + U_0'\bar{R}U_0 $$
The linear constraints on $x(k)$ can be rewritten similarly.
Would this be a more efficient way to define my problem in CVXPY, assuming I would be creating these large matrices in numpy? Is this something that's done in practice?
This transformation isn't applied or anywhere mentioned in CVXPY's example on control
[1]: Borrelli, F., A. Bemporad . M. Morari: Predictive control for linear
and hybrid systems. Cambridge University Press, 2017.
[2] Gutjahr B, Gröll L, Werling M. Lateral vehicle trajectory optimization using constrained linear time-varying MPC. IEEE Transactions on Intelligent Transportation Systems. 2016 Oct 19;18(6):1586-95.
From the mathematics point of view the reformulated problem is the same. Only the different formulation fits the more general quadratic programming problem framework. Therefore, it might be that a more efficient solvers has been developed for it.
The given structure of the optimization problem cast as a quadratic programming problem might benefit from using sparse matrices. But the best way to know which implementation is more efficient/faster for any particular problem, is by implementing both and test which one is better.
Also note that the problem that you are solving, LQR+inequality constraints, is also a form of model predictive control, for which quadratic programming solvers are used [1].
[1]: Schwenzer, M., Ay, M., Bergs, T., & Abel, D. (2021). Review on model predictive control: An engineering perspective. The International Journal of Advanced Manufacturing Technology, 117(5), 1327-1349.