2010年1月1日 星期五

[控制理論] 淺談最佳化理論 - (I)

這次介紹 最佳化理論 (Optimization Theory),一般而言最佳理論是應用數學的一個分支,有著極為廣泛的應用:比如說

如果我們把最佳理論 用到 控制問題上面,就稱為最佳控制:
如果應用到金融市場,可以是 最佳資產分配、最大化預期收益、最小化風險
如果應用到工廠排程問題:可以是 最少工時、最大收益、最小花費 等等
當然應用實在太多太多,這邊不再贅述

不過一般而言,如果由理論面來分,最佳化問題可以考慮由是否有 拘束條件來分類:
  1. 無拘束最佳化問題 (Unconstrained Optimization) 
  2. 有拘束最佳化問題 (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 )
當然事實上最佳理論還有諸多各式各樣的方法。但這邊主要是簡單介紹一個統一的架構:也就是拔除這些花俏 (又難懂) 的名詞,最佳理論的核心問題到底長甚麼樣子? 想表達甚麼?

一個最佳化問題需要甚麼?

  1. 拘束集合 An admissible set (or constraint set):  $u \in U \in \mathbb{R}^n$
  2. 成本函數(或稱性能指標) 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$


在知道了最佳化問題需要甚麼以及長甚麼樣子之後,我們便可以更細部的來探討到底甚麼是拘束集合,甚麼是成本函數


常見的拘束集合
一般而言,大部分物理系統的 控制力 $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}\]