2/24/2017

[凸分析] 常見的凸集性質(1) - 線性矩陣不等式之解 所成的集合 為 凸集

給定 $a \in \mathbb{R}^n$ ,我們定義 線性函數 $f : \mathbb{R}^n \to \mathbb{R}$ 滿足
\[
f(x) := a^T x = a_1 x_1 + ... + a_n x_n
\]
現在我們進一步推廣上述結果:亦即上述的向量 $a = (a_1,...,a_n)$ 可以用 對稱矩陣 $(A_1,...,A_n)$ 替換,且 $ A_i \in S^m$ 為 $\mathbb{R}^{m \times m}$ 對稱矩陣,現在我們模仿上述線性函數 $f$ 定義一個新的函數如下:定義  $F: \mathbb{R}^n \to S^m$ 滿足
\[
F(x) := x_1 A_1 + ... + x_n A_n
\]

Comments:
1. $ F(x) $ 仍為 $\mathbb{R}^{m \times m}$ 的對稱矩陣。
2. 上述提及的 線性函數 $f(x)$  (或者又說標準內積 或者 hyperplane) 可用以形成所謂 convex polyhedra 的集合,在此不贅述。


接著我們想問 對於上述 矩陣等式 $g(x)$ 而言,是否可以定義不等式? 一般而言在線性代數中我們定義 $F(x) \succ 0$ 表示 $F(x)$ 為正定矩陣,亦即 對任意 $z \in \mathbb{R}^n$ 且 $z \neq 0$ 我們有
\[
z^T F(x) z > 0
\] 我們說 $F(x) \succeq 0$ 表示 $F(x)$ 為半正定矩陣,亦即 對任意 $z \in \mathbb{R}^n$
\[
z^T F(x) z \geq 0
\]

FACT:
令 $A,B$ 為 兩實係數 對稱矩陣,若 $A \succeq 0$ 且 $B \succeq 0$ 則
\[
A+B \succeq 0
\]
Proof: omitted (此證明相對容易,在此略過)

========================
Definition: Linear Matrix Inequality (LMI)
我們稱一不等式 為對 $x$ 而言的線性矩陣不等式 (Linear Matrix Inequality in $x$, LMI) 若 前述的矩陣 $F(x)$ 具有下列形式:
\[
F(x) := x_1 A_1 + ... + x_n A_n \preceq B
\] 其中 $x_i \in \mathbb{R}^1$ 且 $B, A_i $ 為 $m \times m$ 對稱矩陣,$i=1,2,...,n$。
========================

Comments:
1. 上述 LMI 要求 $F(x) \preceq B $ 亦即 $B - F(x) \succeq 0$ ,也就是說 $B - F(x) $ 為正定對稱矩陣,由前述定義可知我們要求:對任意 $z \in \mathbb{R}^n$,
\[
z^T (B-F(x))z \geq 0
\]
2. LMI 為 "線性" in $x$
3. LMI 在 強健控制理論中扮演重要的角色,在此不贅述。


以下我們給出主要結果:
========================
FACT:
上述 LMI 之解所成之集合 \[
L:=\{x \in \mathbb{R}^n : F(x) \preceq B\}
\]為凸集。
========================

Proof:
令 $x,y \in L$ 且 $\theta \in [0,1]$ 我們要證明 $ \theta x + (1-\theta)y \in L $ 此等價於證明
\[
F(\theta x + (1-\theta)y) \preceq B
\] 現在觀察
\begin{align*}
  F(\theta x + (1 - \theta )y) &= (\theta {x_1} + (1 - \theta ){y_1}){A_1} + ... + (\theta {x_n} + (1 - \theta ){y_n}){A_n} \hfill \\
   &= \sum\limits_{i = 1}^n {(\theta {x_i} + (1 - \theta ){y_i}){A_i}}  \hfill \\
   &= \theta \sum\limits_{i = 1}^n {{x_i}{A_i}}  + (1 - \theta )\sum\limits_{i = 1}^n {{y_i}{A_i}}  \;\;\;\;\; (*) \hfill \\
\end{align*}
由於  $x,y \in L$ ,故我們有
\begin{align*}
F(x) &:= \sum_{i=1}^n x_i A_i  \preceq B; \\
F(y) &:= \sum_{i=1}^n  y_i A_i \preceq B
\end{align*}故將上述結果帶入 $(*)$ ,由於 $\theta \in [0,1]$ 利用前述 FACT 可得
\[
F(\theta x + (1-\theta)y) \preceq B
\]至此得證。$\square$

沒有留言:

張貼留言

[隨筆] A+焦慮的世代

接住A+世代學生 當了老師之後發現要"接住"學生確實不容易,撇開老師自身可能也有需要被接住的問題不談。我這幾年常常感受到這世代的學生們有著很大的徬徨,不太清楚未來的方向,但是卻有著非得要拿到A/A+不可的糾結,於是課優先選甜涼課,實習競賽投好投滿。好像看著同學...