If the sta­te \(x_{k+1}\) at time \(k+1\) depends line­ar­ly on the pre­vious sta­te \(x_k\) and the con­trol input \(u_k\), the sys­tem dyna­mics can be writ­ten as

$$x_{k+1}=Ax_k+Bu_k $$

whe­re \(x_{k+1}, x_k \in \mathbb{R}^d, u_k\in \mathbb{R}^m\) are typi­cal­ly mul­ti­di­men­sio­nal vec­tors. \(A\) and \(B\) are sys­tem matri­ces that encode the influence of the sta­te and con­trol signal on the future sta­te. If the sys­tem is to be con­trol­led such that it fol­lows a tra­jec­to­ry \(f_1, …, f_n \in \mathbb{R}^d\) with as small a con­trol input as pos­si­ble, this can be for­mu­la­ted as the optimi­zation problem

$$ \begin{align} \min_{x_1, …, x_n, u_1, …, u_n}  ~~~& \sum_{k=1}^n \|x_k-f_k\|_1+\|u_k\| \\ \text{s.t.} ~~~&x_{k+1}=Ax_k+Bu_k~~~ k=1, …, n \\ ~~~& x_1=x_{start} \end{align}$$

whe­re \(x_1\) is set as the start­ing sta­te \(x_{start}\). The optimi­zation varia­bles are the \(n\) con­trol inputs \(u_1, …, u_n\) and the sta­tes \(x_1, …, x_n\), cons­trai­ned by the dyna­mic cons­traints. It is an optimi­zation pro­blem with \(nd+nm\) variables.

It can be refor­mu­la­ted as a line­ar pro­gram with the objec­ti­ve func­tion \(\|x‑f\|_1+\|u\|_1=\|v^{\Delta}\|_1+\|v^u\|_1\) whe­re \(x=[x_1^T, …, x_n^T]^T\) and \(u=[u_1^T, …, u_n^T]^T\) with \(v^{\Delta} \in \mathbb{R}^{nd}\) and \(v^u\in \mathbb{R}^{nm}\) being the vec­tors of the abso­lu­te values of the ele­ments of \(x‑f\) and \(u\).

$$ \begin{align} \min_{x_1, …, x_n, u_1, …, u_n, v^{\Delta}, v^u}  ~~~& \sum_{k=1}^n\sum_{l=1}^d v^{\Delta}_{kl}+ \sum_{k=1}^n \sum_{l=1}^m v^u_{kl} \\ \text{s.t.} ~~~&x_{k+1}=Ax_k+Bu_k~~~ k=1, …, n \\ ~~~& v^{\Delta} \ge x‑f ~~~ v^{\Delta}\ge -(x‑f) \\ ~~~& v^u\ge u ~~~~~~~~~~~ v^u \ge ‑u \end{align}$$

The first ine­qua­li­ty repres­ents the dyna­mics of the sys­tem while the last two pairs ensu­re the posi­ti­vi­ty of the abso­lu­te resi­du­als \(v^{\Delta}\) and \(v^u\) [1, p. 294].