這次介紹 最佳化理論 (Optimization Theory)，一般而言最佳理論是應用數學的一個分支，有著極為廣泛的應用：比如說
如果我們把最佳理論 用到 控制問題上面，就稱為最佳控制：
如果應用到金融市場，可以是 最佳資產分配、最大化預期收益、最小化風險
如果應用到工廠排程問題：可以是 最少工時、最大收益、最小花費 等等
當然應用實在太多太多，這邊不再贅述
不過一般而言，如果由理論面來分，最佳化問題可以考慮由是否有 拘束條件來分類：
對上述問題各自求解的工具也不同，但可以想見 有拘束最佳化問題 會比 無拘束最佳化問題 在求解上會更加困難。主要來說，有拘束的最佳問題也比無拘束的最佳問題更接近真實情況。比如說如果我們考慮要控制一個 馬達 使其達到某個預期的輸出力矩，則馬達的出力必定有一定限制。或者說要控制汽車的車速，油門也有一定的限制，不可能到無窮大。把這些限制加入問題一併考慮做最佳化就稱作 有拘束最佳化問題。
再者是求解的工具：這邊簡要介紹
那麼注意到在求解問題之前，我們必須先知道 "是否有解?" 因為如果沒有解 又何必費心呢? 舉例而言，考慮下列最佳化問題：
\[
\min \{x| x \in (0,1)\}
\]沒有解。因為我們知道 $\inf \{x| x \in (0,1)\} = 0$ 但是 $x = 0$ 並沒有落在拘束集合 $(0,1)$ 之中。
所幸 Weierstrass Extreme Value Theorem 告訴我們一件重要的事實，以免去我們心頭大患。在此陳述如下：
=====================
Weierstrass Extreme Value Theorem ：
若拘束集合 $U$ 為 compact set 且 cost function $J$ 為連續函數，則 $J$ 必定存在 至少一個 最大 與 最小值；亦即 存在 $u_1,u_2 \in U$ 使得 對任意 $x \in U$
\[
J(u_1) \ge J(x) \ge J(u_2)
\]=====================
注意到上述 compact set 在有限維度空間 (; i.e., $\mathbb{R}^n$) 等價為 $U$ 需 closed 與 bounded；我們在此給出 boundedness 與 closedness 的定義：
Bounded Set:
集合 $X \in \mathbb{R}^n$ 為 bounded 若下列條件成立：
存在 $M< \infty$ 使得 對任意 $x \in X$，$|x| \le M$。
Closed Set:
集合 $X \in \mathbb{R}^n$ 為 closed 若 其包含所有的 limit point (對任意 sequence $\{p_n\} $ in $X$ 收斂到 $p$ 且 $p \in X$)。
Question: 若我們最佳化的拘束集合為 $\mathbb{R}^n$ (NOT compact ! ) 該怎麼辦? 可透過 建構 水平集 (level set) 將 $\mathbb{R}^n$ 砍成 compact set ，則此時我們可再度使用 Weiestrass Theorem 保證最佳解的存在性。
現在我們看個例子：
常見的拘束集合
控制力的拘束與其 標準式
一般而言，簡潔起見我們亦可將對控制力 $u$ 的拘束表示為以下線性不等式
\[
E u(t) \le e
\]
Example
考慮 $u(t) \in \mathbb{R}^m$，試將 $U_{min} \le u(t) \le U_{max}$ 表示成 $E u(t) \le e$ 的形式。
Solution
\[\begin{array}{l}
{U_{min}} \le u(t) \le {U_{max}} \Leftrightarrow \left\{ \begin{array}{l}
u(t) \le {U_{max}}\\
{U_{min}} \le u(t)
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \Leftrightarrow \left\{ \begin{array}{l}
u(t) \le {U_{max}}\\
- u(t) \le - {U_{min}}
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \Leftrightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]}_Eu(t) \le \underbrace {\left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]}_e
\end{array}\]
狀態 or 輸出的拘束與其 標準式
如果我們把最佳理論 用到 控制問題上面，就稱為最佳控制：
如果應用到金融市場，可以是 最佳資產分配、最大化預期收益、最小化風險
如果應用到工廠排程問題：可以是 最少工時、最大收益、最小花費 等等
當然應用實在太多太多，這邊不再贅述
不過一般而言，如果由理論面來分，最佳化問題可以考慮由是否有 拘束條件來分類：
- 無拘束最佳化問題 (Unconstrained Optimization)
- 有拘束最佳化問題 (Constrained Optimization)
對上述問題各自求解的工具也不同，但可以想見 有拘束最佳化問題 會比 無拘束最佳化問題 在求解上會更加困難。主要來說，有拘束的最佳問題也比無拘束的最佳問題更接近真實情況。比如說如果我們考慮要控制一個 馬達 使其達到某個預期的輸出力矩，則馬達的出力必定有一定限制。或者說要控制汽車的車速，油門也有一定的限制，不可能到無窮大。把這些限制加入問題一併考慮做最佳化就稱作 有拘束最佳化問題。
再者是求解的工具：這邊簡要介紹
- 若問題考慮為拘束條件具有 Convex 函數性質，一般泛稱 Convex Optimization 問題，則多半採用 Convex Analysis 或者 Convex Program 來著手 (為何此類最佳化問題有額外名詞? 最根本原因是一旦最佳化函數具有 convexity (or concavity) 且若拘束條件可寫作 convex set 則局部最佳解等同全域最佳解 )。
- 若問題拓展到 非線性 (可以是 convex or non-convex) 有拘束的最佳化問題 ，可以採用 Largrange multipliers method/ Dynamic Programming / Iterative Algorithm Search 對付 。
- 若問題是 線性 有拘束 的最佳化問題，可以採用 線性規劃 Linear Programming 對付 。(線性規劃亦屬於 Convex Program )
一個最佳化問題需要甚麼?
- 拘束集合 An admissible set (or constraint set): $u \in U \in \mathbb{R}^n$
- 成本函數(或稱性能指標) Cost function (or performance index): $J(u)$
一個最佳化問題應該長甚麼樣子?
- 找出最佳控制力 $u^* \in U$ (if $u^*$ exists) 使得 \[J(u^*) = \displaystyle \min_{u \in U} J(u)\]
簡單說就是，從拘束集合中找到一個最佳的 $u^*$ (前提是我們找的到) 使得給定的成本函數能最小(or 最大)
那麼注意到在求解問題之前，我們必須先知道 "是否有解?" 因為如果沒有解 又何必費心呢? 舉例而言，考慮下列最佳化問題：
\[
\min \{x| x \in (0,1)\}
\]沒有解。因為我們知道 $\inf \{x| x \in (0,1)\} = 0$ 但是 $x = 0$ 並沒有落在拘束集合 $(0,1)$ 之中。
所幸 Weierstrass Extreme Value Theorem 告訴我們一件重要的事實，以免去我們心頭大患。在此陳述如下：
=====================
Weierstrass Extreme Value Theorem ：
若拘束集合 $U$ 為 compact set 且 cost function $J$ 為連續函數，則 $J$ 必定存在 至少一個 最大 與 最小值；亦即 存在 $u_1,u_2 \in U$ 使得 對任意 $x \in U$
\[
J(u_1) \ge J(x) \ge J(u_2)
\]=====================
注意到上述 compact set 在有限維度空間 (; i.e., $\mathbb{R}^n$) 等價為 $U$ 需 closed 與 bounded；我們在此給出 boundedness 與 closedness 的定義：
Bounded Set:
集合 $X \in \mathbb{R}^n$ 為 bounded 若下列條件成立：
存在 $M< \infty$ 使得 對任意 $x \in X$，$|x| \le M$。
Closed Set:
集合 $X \in \mathbb{R}^n$ 為 closed 若 其包含所有的 limit point (對任意 sequence $\{p_n\} $ in $X$ 收斂到 $p$ 且 $p \in X$)。
Question: 若我們最佳化的拘束集合為 $\mathbb{R}^n$ (NOT compact ! ) 該怎麼辦? 可透過 建構 水平集 (level set) 將 $\mathbb{R}^n$ 砍成 compact set ，則此時我們可再度使用 Weiestrass Theorem 保證最佳解的存在性。
現在我們看個例子：
Example: Unconstrained Optimization Problem
考慮線性非時變(LTI)系統
\[
\frac{dx}{dt} = u, \;\; x(0)=1
\]且我們定義成本函數為
\[J:=\int_0^T{[{x^2}(t) + {u^2}(t)]dt},\;\; 0 < T< \infty \]
試找出一個最佳的 $u^*(t)$ 使得 上述成本函數 "最小"。
Solution
由於我們要使成本函數 $J$ 最小。故首先觀察下式
\[
(x(t)+u(t))^2 = x(t)^2 + 2x(t)u(t) + u(t)^2
\]對兩邊 對 $t$ 積分從 $0$ 到固定常數 $T$可得
\[\int_0^T {{{\left( {x\left( t \right) + u\left( t \right)} \right)}^2}dt} = \int_0^T {\left( {{x^2}\left( t \right) + {u^2}\left( t \right)} \right)} dt + 2\int_0^T {x\left( t \right)u\left( t \right)} dt
\]由系統方程可知 $dx/dt = u$，故我們可改寫上式如下
\[\begin{array}{*{20}{l}}
{\int_0^T {{{\left( {x + u} \right)}^2}dt} = \int_0^T {\left( {{x^2} + {u^2}} \right)} dt + 2\int_0^T {x\left( t \right)dx} }\\
\begin{array}{l}
\Rightarrow \int_0^T {{{\left( {x + u} \right)}^2}dt} = \underbrace {\int_0^T {\left( {{x^2} + {u^2}} \right)} dt}_{ = J} + {x^2}\left( T \right) - x\left( 0 \right)\\
\Rightarrow J = \int_0^T {\left( {{x^2} + {u^2}} \right)} dt = \int_0^T {{{\left( {x + u} \right)}^2}dt} + x\left( 0 \right) - {x^2}\left( T \right)
\end{array}
\end{array}\]現在觀察上式，若欲使上式積分最小，則等號右方積分必須為零亦即
\[\int_0^T {\left( {{x^2} + {u^2}} \right)} dt =0\]故我們選 $u^*(t) := -x(t)$即可達成。$\square$
在知道了最佳化問題需要甚麼以及長甚麼樣子之後，我們便可以更細部的來探討到底甚麼是拘束集合，甚麼是成本函數
考慮線性非時變(LTI)系統
\[
\frac{dx}{dt} = u, \;\; x(0)=1
\]且我們定義成本函數為
\[J:=\int_0^T{[{x^2}(t) + {u^2}(t)]dt},\;\; 0 < T< \infty \]
試找出一個最佳的 $u^*(t)$ 使得 上述成本函數 "最小"。
Solution
由於我們要使成本函數 $J$ 最小。故首先觀察下式
\[
(x(t)+u(t))^2 = x(t)^2 + 2x(t)u(t) + u(t)^2
\]對兩邊 對 $t$ 積分從 $0$ 到固定常數 $T$可得
\[\int_0^T {{{\left( {x\left( t \right) + u\left( t \right)} \right)}^2}dt} = \int_0^T {\left( {{x^2}\left( t \right) + {u^2}\left( t \right)} \right)} dt + 2\int_0^T {x\left( t \right)u\left( t \right)} dt
\]由系統方程可知 $dx/dt = u$，故我們可改寫上式如下
\[\begin{array}{*{20}{l}}
{\int_0^T {{{\left( {x + u} \right)}^2}dt} = \int_0^T {\left( {{x^2} + {u^2}} \right)} dt + 2\int_0^T {x\left( t \right)dx} }\\
\begin{array}{l}
\Rightarrow \int_0^T {{{\left( {x + u} \right)}^2}dt} = \underbrace {\int_0^T {\left( {{x^2} + {u^2}} \right)} dt}_{ = J} + {x^2}\left( T \right) - x\left( 0 \right)\\
\Rightarrow J = \int_0^T {\left( {{x^2} + {u^2}} \right)} dt = \int_0^T {{{\left( {x + u} \right)}^2}dt} + x\left( 0 \right) - {x^2}\left( T \right)
\end{array}
\end{array}\]現在觀察上式，若欲使上式積分最小，則等號右方積分必須為零亦即
\[\int_0^T {\left( {{x^2} + {u^2}} \right)} dt =0\]故我們選 $u^*(t) := -x(t)$即可達成。$\square$
在知道了最佳化問題需要甚麼以及長甚麼樣子之後，我們便可以更細部的來探討到底甚麼是拘束集合，甚麼是成本函數
一般而言，大部分物理系統的 控制力 $u$ 都為有界，此性質可用數學的 norm 來體現，故現在考慮 $\mathbb{R}^n$ 空間，則下列三種 norm constraint 為最常見的拘束集合
1. $l^2$ -norm constraint set (or 又稱球狀(spherical shape)拘束集合)
\[ \displaystyle \sqrt {\sum_{i=1}^n u_i^2} \leq r\]注意：上式左側即為 $l^2$ -norm ，可簡寫為\[ || u ||_2:= \sqrt{u^T u} = \displaystyle \sqrt {\sum_{i=1}^n u_i^2} \]此 $l^2$ -norm 又稱 classical norm 因為此種形式(符合一般Euclidean 長度的計算)最為常見。
2. $l^1$ -norm constraint set(or 有時候稱 鑽石狀(diamond shape)拘束集合)
\[||u||_1:=\displaystyle \sum_{i=1}^n |u_i| \leq r\]
3. $l^{\infty}$ -norm constraint set(or 有時候稱 矩形狀(rectangular shape)拘束集合)
\[||u||_{\infty}:= max\{|u_1|,|u_2|,...,|u_n| \} \leq r\]上述三種 norm 在 $\mathbb{R}^2$可以繪製如下圖
 |
| The plot of vector norms in separately. from wiki |
亦可將此三者疊合(nested)一起如下
 |
| vector norms |
關於 Norm 有興趣的讀者可參考：[線性系統] 淺談各種基本範數 (Norm)
控制力的拘束與其 標準式
一般而言，簡潔起見我們亦可將對控制力 $u$ 的拘束表示為以下線性不等式
\[
E u(t) \le e
\]
Example
考慮 $u(t) \in \mathbb{R}^m$，試將 $U_{min} \le u(t) \le U_{max}$ 表示成 $E u(t) \le e$ 的形式。
Solution
\[\begin{array}{l}
{U_{min}} \le u(t) \le {U_{max}} \Leftrightarrow \left\{ \begin{array}{l}
u(t) \le {U_{max}}\\
{U_{min}} \le u(t)
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \Leftrightarrow \left\{ \begin{array}{l}
u(t) \le {U_{max}}\\
- u(t) \le - {U_{min}}
\end{array} \right.\\
\begin{array}{*{20}{c}}
{}&{}&{}&{}&{}&{}&{}&{}
\end{array} \Leftrightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]}_Eu(t) \le \underbrace {\left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]}_e
\end{array}\]
狀態 or 輸出的拘束與其 標準式
有些時候我們亦會考慮將狀態列入拘束之中，其標準式為
\[
F x(t) \le f
\] 或者進一步推廣的 混合型 拘束形式
\[
F x(t) + E u(t) \le e
\]
Example: (Discrete Increment of Control Input)
試將 $U_{min} \le u(k) - u(k-1) \le U_{max}$ 表示成 $F x(k) + E u(k) \le e $。
Solution
首先定義 擴增狀態向量 (augmented state vector) 如下
\[\tilde x(k): = \left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right]
\]則其對應的擴增 系統 (augmented system)
\[\begin{array}{l}
\left\{ \begin{array}{l}
\tilde x(k + 1) = \tilde A\tilde x\left( k \right) + \tilde Bu\left( k \right)\\
y\left( k \right) = \tilde C\tilde x\left( k \right)
\end{array} \right.\\
\Rightarrow \left\{ \begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{x\left( {k + 1} \right)}\\
{u\left( k \right)}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
A&0\\
0&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
I
\end{array}} \right]u\left( k \right)\\
y\left( k \right) = \left[ {\begin{array}{*{20}{c}}
C&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right]
\end{array} \right.
\end{array}\]則拘束 $U_{min} \le u(k) - u(k-1) \le U_{max}$ 可表為
\[\begin{array}{l}
{U_{min}} \le u(k) - u(k - 1) \le {U_{max}}\\
\Leftrightarrow \left\{ \begin{array}{l}
u(k) - u(k - 1) \le {U_{max}}\\
- u(k) + u(k - 1) \le - {U_{min}}
\end{array} \right.\\
\Leftrightarrow \left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]u(k) + \left[ {\begin{array}{*{20}{c}}
{ - I}\\
I
\end{array}} \right]u(k - 1) \le \left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]\\
\Leftrightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]}_Eu(k) + \underbrace {\left[ {\begin{array}{*{20}{c}}
0&{ - I}\\
0&I
\end{array}} \right]}_F\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right] \le \underbrace {\left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]}_e
\end{array}\]
\] 或者進一步推廣的 混合型 拘束形式
\[
F x(t) + E u(t) \le e
\]
Example: (Discrete Increment of Control Input)
試將 $U_{min} \le u(k) - u(k-1) \le U_{max}$ 表示成 $F x(k) + E u(k) \le e $。
Solution
首先定義 擴增狀態向量 (augmented state vector) 如下
\[\tilde x(k): = \left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right]
\]則其對應的擴增 系統 (augmented system)
\[\begin{array}{l}
\left\{ \begin{array}{l}
\tilde x(k + 1) = \tilde A\tilde x\left( k \right) + \tilde Bu\left( k \right)\\
y\left( k \right) = \tilde C\tilde x\left( k \right)
\end{array} \right.\\
\Rightarrow \left\{ \begin{array}{l}
\left[ {\begin{array}{*{20}{c}}
{x\left( {k + 1} \right)}\\
{u\left( k \right)}
\end{array}} \right] = \left[ {\begin{array}{*{20}{c}}
A&0\\
0&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right] + \left[ {\begin{array}{*{20}{c}}
0\\
I
\end{array}} \right]u\left( k \right)\\
y\left( k \right) = \left[ {\begin{array}{*{20}{c}}
C&0
\end{array}} \right]\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right]
\end{array} \right.
\end{array}\]則拘束 $U_{min} \le u(k) - u(k-1) \le U_{max}$ 可表為
\[\begin{array}{l}
{U_{min}} \le u(k) - u(k - 1) \le {U_{max}}\\
\Leftrightarrow \left\{ \begin{array}{l}
u(k) - u(k - 1) \le {U_{max}}\\
- u(k) + u(k - 1) \le - {U_{min}}
\end{array} \right.\\
\Leftrightarrow \left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]u(k) + \left[ {\begin{array}{*{20}{c}}
{ - I}\\
I
\end{array}} \right]u(k - 1) \le \left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]\\
\Leftrightarrow \underbrace {\left[ {\begin{array}{*{20}{c}}
I\\
{ - I}
\end{array}} \right]}_Eu(k) + \underbrace {\left[ {\begin{array}{*{20}{c}}
0&{ - I}\\
0&I
\end{array}} \right]}_F\left[ {\begin{array}{*{20}{c}}
{x\left( k \right)}\\
{u\left( {k - 1} \right)}
\end{array}} \right] \le \underbrace {\left[ {\begin{array}{*{20}{c}}
{{U_{max}}}\\
{ - {U_{min}}}
\end{array}} \right]}_e
\end{array}\]
留言
張貼留言