[線性規劃] Discrete Time Dynamic System Linear Programming

這次要介紹的是如何把一個 有拘束條件 離散時間的動態系統
透過 線性規劃問題來求解。

考慮 離散時間系統的狀態空間表示(state space representation)：
\[
x(k+1) = A x(k) + B u(k), \ \ \ \ \text{given $x(0)$}
\]其中 $x(k) \in \mathbb{R}^n$ 表系統狀態， $u(k)$ 表控制力。

接著我們考慮一些實際的情況：

1. 我們希望系統狀態 隨著時間流逝 與 控制力的幫助，可以在某個時間點達到某個 指定的目標狀態 $x^1$，亦即考慮 終止狀態 $x(N) := x^1$
2. 由於我們是透過控制力來幫助我們讓系統狀態逐步移動到 指定的目標狀態，考量到一班情況，控制力的出力大小須受到一定程度拘束(不可以有無限大的控制力)，亦即
 \[
|u(k)| \leq M \Leftrightarrow -M \leq u(k) \leq M
\]

現在我們定義目標成本函數 (cost function)
\[
J(u) = \displaystyle \sum_{k=0}^{N-1} | u(k)|
\]

Comments:
1. 上述目標為 讓 控制力最小。簡單來說就是要 可以達到目標狀態的情況下 盡可能省力 (可以想像成要要開車 從 A 到 B地點，且盡可能省油。)

2. 上述cost function 最多只能是 取絕對值 (儘管是非線性但可透過一些技巧將其轉換成LP問題)，超過  一般 2階 (or 以上)的 cost function，比如
\[
J(u) = \displaystyle \sum_{k=0}^{N-1} | u(k)|^2
\]不可使用 Linear Programming。因為上述cost function 不再是線性! 。Forget LP in this case..

故我們手上有了一個標準的最佳化問題：
\[\begin{array}{l}
\min J\left( u \right) = \sum\limits_{k = 0}^{N - 1} {\left| {u\left( k \right)} \right|} \\
s.t.\\
\begin{array}{*{20}{c}}
{}
\end{array}x(k + 1) = Ax(k) + Bu(k)\\
\begin{array}{*{20}{c}}
{}
\end{array}x(N): = {x^1}\\
\begin{array}{*{20}{c}}
{}
\end{array}|u(k)| \le M
\end{array}
\]

首先注意到因為我們的成本函數是對 $u(k)$ 最小化，故上式中的拘束應改寫成由 $u(k)$表示：
故我們先改寫 目標狀態拘束 $x(N) = x^1$ 用 $u(k)$ 表示：

怎麼做呢!? 由 離散時間系統的狀態方程
\[
x(k+1) = A x(k) + B u(k), \ \ \ \ \text{given $x(0)$}
\]我們可以進行 跌代求解如下：
\[\begin{array}{l}
x(1) = Ax(0) + Bu(0)\\
x(2) = Ax(1) + Bu(1) = A\left[ {Ax(0) + Bu(0)} \right] + Bu(1)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^2}x(0) + ABu(0) + Bu(1)\\
x(3) = Ax(2) + Bu(2) = A\left[ {{A^2}x(0) + ABu(0) + Bu(1)} \right] + Bu(2)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^3}x(0) + {A^2}Bu(0) + ABu(1) + Bu(2)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} \vdots \\
x(N) = {A^N}x(0) + {A^{N - 1}}Bu(0) +  \cdots  + ABu(N - 2) + Bu(N - 1)\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} = {A^N}x(0) + \sum\limits_{k = 0}^{N - 1} {{A^{N - 1 - k}}Bu(k)}
\end{array}
\]又因為 $x(N) := x^1$，故我們得到
\[\begin{array}{l}
{x^1} = {A^N}x(0) + \sum\limits_{k = 0}^{N - 1} {{A^{N - 1 - k}}Bu(k)} \\
 \Rightarrow {x^1} - {A^N}x(0) = \left[ {\begin{array}{*{20}{c}}
{{A^{N - 1}}B}&{{A^{N - 2}}B}& \cdots &{{A^1}B}&{{A^0}B}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{u(0)}\\
{u(1)}\\
 \vdots \\
{u(N - 1)}
\end{array}} \right]
\end{array}
\] 由於上式左方 $x^1$ 與 $x(0)$ 已給定，故我們可以聯合上式與 控制力拘束條件 $ |u(k)| \leq M$，將其改寫成LP問題：

對於每一個固定的 $N$，求解 進行求解 LP問題:
\[\begin{array}{l}
\min J\left( u \right) = \sum\limits_{k = 0}^{N - 1} {\left| {u\left( k \right)} \right|} \\
s.t.\\
\left\{ \begin{array}{l}
\begin{array}{*{20}{c}}
{}
\end{array}{x^1} - {A^N}x(0) = \left[ {\begin{array}{*{20}{c}}
{{A^{N - 1}}B}&{{A^{N - 2}}B}& \cdots &{{A^1}B}&{{A^0}B}
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{u(0)}\\
{u(1)}\\
 \vdots \\
{u(N - 1)}
\end{array}} \right]\\
\begin{array}{*{20}{c}}
{}
\end{array}|u(k)| \le M
\end{array} \right.
\end{array}\]