1/30/2010

[線性系統] 矩陣的二次式 與 正定矩陣

=======================
Definition: (Symmetric matrix)
一個 $n \times n$ 實數 矩陣 $M$ 稱為 對稱 (symmetric) 矩陣 若 $M^T = M$。

Definition: (Quadratic form of matrix)
令 $x \in \mathbb{R}^n$ 實數向量 與  $M$ 為 $n \times n$ 實數對稱矩陣 ( $M^T =M$),則我們稱下列形式
\[
x^T M x
\]為一個 M矩陣的二次式 (quadratic form of matrix) 
=======================
Comment
1. 若 $x$ 為 complex vector,則 $M$ 的 二次式表示為 $x^* M x$。
2. 矩陣的二次式 $x^TMx$ 幫我們把 矩陣 轉成 純量

上面矩陣二次式 與 對稱矩陣 實際上有甚麼用呢? 事實上 對稱矩陣 具有非常特殊的 eigenvalue 性質,也就是 eigenvalue 保證必定是 實數 (沒有 complex part) 。而在系統理論裡面我們又知道 eigenvalue 對系統穩定性與系統性能至關重要,故我們先看一個結果:

=====================
FACT: 對任意 實數對稱矩陣 $M$ 其 eigenvalue 必定為實數。
=====================
Proof:
由於實數矩陣可能具有 complex 的 eigenvalue 與 eigenvector,故我們必須考慮 eigenvalue 為複數的情況。現在令 $x$ 為 complex number 且我們透過 $M$ 的二次式 $x^* M x$ 來幫助我們
首先對 $M$ 的二次式再取一次 complex conjugate 可得
\[\begin{array}{l}
{\left( {{x^*}Mx} \right)^*} = {x^*}{M^*}x\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array}\mathop  = \limits^{M\begin{array}{*{20}{c}}
{}
\end{array}is\begin{array}{*{20}{c}}
{}
\end{array}real} {x^*}{M^T}x\\
\begin{array}{*{20}{c}}
{}&{}&{}
\end{array}\mathop  = \limits^{M\begin{array}{*{20}{c}}
{}
\end{array}is\begin{array}{*{20}{c}}
{}
\end{array}symmetric} {x^*}Mx \ \ \ \ \ (*)
\end{array}\]由上式可知 對任意 complex vector $x$,$x^*Mx$ 皆為 實數。

現在我們令 $\lambda$ 為 $M$ 的 eigenvalue 且 $v$ 為對應 $\lambda$ 的 eigenvector,亦即此兩者必須滿足 eigenvalue-eigenvector 關係 $M v = \lambda v$,故我們可改寫 $(*)$ 如下:
\[{v^*}\underbrace {Mv}_{ = \lambda v} = {v^*}\lambda v = \lambda {v^*}v = \lambda {\left\| v \right\|^2}\]且由於 $v^*Mv$ 與 $v^*v$ 皆為 實數,故 $\lambda$ 必定為實數。$\square$


現在我們介紹矩陣的正定性質,一般而言我們對於數字純量可以很容易判斷正負,但是對於矩陣而言便有所困難;故此我們引入 "正定 (positive definiteness)" 的概念:

=================================
Definition: (Positive definiteness and positive semidefinite)
一個 對稱 矩陣 $M$ 稱為 正定 (positive definite) 記做 $M \succ 0$ 若下列條件成立:
對任意非零向量 $x$,其二次式 $x^T M x >0$。

一個對稱矩陣 $M$ 稱為 半正定 (positive semidefinite) 記做 $M \succeq 0$ 若下列條件成立:
對任意非零向量 $x$,其二次式 $x^T M x \ge 0$。
=================================

Comment:
若 $M \succ 0$ 且 $x^T Mx =0$ 若且為若 $x =0$。
若 $M  \succeq 0$ ( $x^TMx \ge 0\;\;\text{for} \; x \ne 0$) $\Rightarrow$ 存在一個 $x \ne 0$ 使得 $x^T M x =0$。

現在我們看看除了定義之外,還有甚麼方法判別矩陣是否為正定?

================================
Theorem: Criterion of positive definiteness
一個對稱的 $n \times n$ 矩陣 $M$ 為 positive definite 若且為若 下列任一條件成立:
1. 所有 $M$ 的 eigenvalue $\lambda$ 都為正  ($\lambda > 0$)。
2. 所有 $M$ 的 leading principal minors 皆為正。
3. 存在一個 $n \times n$ 的 nonsingular 矩陣 $N$ 使得 $M = N^TN$
================================
Proof: omitted.

這邊我們省略證明,有興趣得讀者可參閱任何一本 線性系統或者線性代數的教科書即可。我們這邊只關注第三點:
若 $M = N^TN$,則我們觀察其 二次式:對任意 $x$ 而言,我們有
\[{x^T}Mx = {x^T}{N^T}Nx = \left( {N{x^T}} \right)Nx = \left\| {Nx} \right\|_2^2 \ge 0
\]現在若 $N$ 為 nonsingular 則我們知道 對任意 $x$,$N x \ne 0$,故只有當 $x =0$ 時候才會使 $Nx =0$。故可推知 $M \succ 0$


================================
Theorem: Criterion of positive semidefiniteness
一個對稱的 $n \times n$ 矩陣 $M$ 為 positive definite 若且為若 下列任一條件成立:
1. 所有 $M$ 的 eigenvalue $\lambda$ 都為 非負 ($\lambda \ge 0$)。
2. 所有 $M$ 的 leading principal minors 皆為非負。
3. 存在一個 $n \times n$ 的 singular 矩陣 $N$ 或者 $m \times n$ (n > m) 的矩陣 $N$使得 $M = N^TN$
================================
Proof: omitted.

1/01/2010

[控制理論] 淺談最佳化理論 - (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}\]

[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...