跳到主要內容

發表文章

目前顯示的是 2017的文章

[凸分析] 任意遞增函數為 quasiconcave 與 quasiconvex

============= Theorem: 令 $f : \mathbb{R} \to \mathbb{R}$ 為遞增函數,則 $f$ 同時為 quasiconcave 與 quasiconvex。 ============= Proof: 考慮 $x,y \in \mathbb{R}$ 且 $\lambda \in (0,1)$,在不失一般性情況我們假設 $x>y$,則 \[ x > \lambda x + (1-\lambda)y > y \]因為 $f$ 遞增,我們有 \[ f(x) > f( \lambda x + (1-\lambda)y) > f(y) \;\;\;\; (**) \]由上述不等式,我們可寫  $$ f(x) = \max\{f(x),f(y)\} $$故由第一部分的不等式,我們有 \[  \max\{f(x),f(y)\} > f( \lambda x + (1-\lambda)y) \]此表明 $f$ 為 quasiconvex。 同理,由 $(**)$ 我們亦可寫下 \[ f(y) := \min\{f(x),f(y)\} \]故由第二部分的不等式,我們有 \[  f( \lambda x + (1-\lambda)y) >\min\{f(x),f(y)\} \]此表明 $f$ 為 quasiconcave 至此證明完畢。$\square$

[凸分析] 凸性 與 齊次性 的關聯 (2):一些常見的結果

此文接續前篇對於凸函數 與 齊次函數的討論,主要是給出一些常見的結果。閱讀此文之前,建議讀者先回憶 凸性 與 齊次函數的定義,關於齊次函數以及一些相關例子,讀者可參閱 [凸分析] 凸性 與 齊次性 的關聯 (1):一些常見例子 。 以下我們首先給出 一組齊次函數的 連乘  或 連加 仍保持為 齊次函數 的條件: ================================ Theorem: Homogeneous Functions Algebra 1. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions,且對於 $i=1,...,m$ 而言, $f_i$ 具有 homogeneous of degree $\alpha_i$。則 \[ z(x) :=  \prod_{i=1}^m f_i(x) = f_1(x) \cdot f_2(x) \cdots f_m(x) \]為 homogenous of degree $(\alpha_1 + ... +\alpha_m)$ 2. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions,且對於 $i=1,...,m$ 而言, $f_i$ 具有相同 homogeneous of degree $\alpha$。則 \[z(x): = {\left( {\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta }\]為 homogenous of degree $(\alpha \beta)$ ================================ Proof 1:  令 $x \in C$ 觀察 \[ z(tx) = \prod_{i=1}^m f_i(tx) \]由於 $f_i$ 為 homogeneous of degree $\alpha_i$,我們有 $$f_i(tx) = t^{\alpha_i} f(x)$$ 且 $\forall t>0, i=1,2,...,m$,因此 \b

[凸分析] 凸性 與 齊次性 的關聯 (1):定義 與 一些常見例子

Definition:  Homogenous Function of Degree Alpha 令 $C \subset \mathbb{R}^n$ 為 convex cone。我們說函數 $f: C \to \mathbb{R}$ 為  $\alpha$ 次齊次函數 (homogeneous of degree $\alpha \in \mathbb{R}$) 若下列條件成立: 對任意 $x \in C$, \[ f(t x) = t^\alpha f(x),\;\;\; \forall t >0 \] Comments: 1.上述 齊次函數 定義可以推廣到不是在 convex cone上而是任意向量空間,但一般做 convex cone的假設是為了 其他在凸分析上的 用途。在比較深入的凸分析教材中,可能會探討所謂 廣義凸性(generalized convexity)比如 quasi-convexity, quasi-concavity, semi-strictly quasi-convexity 等等,則此時函數定義域 需要是凸集。 2. 注意到 degree of homogeneity $\alpha \in \mathbb{R}$,意指 此 $\alpha$ 為任意實數,正數,負數,零 或者其他都可以。 3. 我們說 $f$ 為 homogenous of degree $0$ 若對任意 $x \in C$, \[ f(tx) = f(x), \forall t>0 \]若 $f$ 為 homogenous of degree $1$ 一般稱之為 linearly homogeneous ,亦即 對任意 $x \in C$ \[ f(tx) = t f(x), \forall t>0 \] 以下我們看幾個例子: Example 1 考慮 需求函數 (Demand Function) \[ D(p,R) := \frac{R}{p} \]其中 $p > 0$ 為 price of a good 且 $R>0$ 為 income,試證此函數為 homogeneous of degree 0 Proof:  令 $C :=\{(p,r): p>0, R>0\}$

[訊號處理] 離散時間 的 Parserval's Theorem

Discrete-Time Parserval's Theorem: 令 $x[n]$ 為 取實數值的離散時間訊號; i.e., 對任意整數 $n$ 而言,  $x[n] \in \mathbb{R}$ 且令 $X(\omega) := DTFT(x[n])$,則下列等式成立  \[\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\left[ n \right]} \right|}^2} = \frac{1}{{2\pi }}\int_0^{2\pi } {{{\left| {X\left( \omega  \right)} \right|}^2}d\omega } } \]其中 $DTFT(x[n])$ 表示 對 $x[n] $ 取 離散時間傅立葉轉換 (Discrete Time Fourier Transform, DTFT),亦即 \[ X(\omega) := \sum_{n = -\infty}^\infty x[n] e^{-j \omega n} \] Comments: 1. 在訊號處理或者訊號分析的領域,上述定理有可被賦予的物理意義:一般我們把 Parserval's theorem 等式左方 稱為 訊號 $x[n]$ 的 總能量 (total energy) ,現在觀察右式表示對 $|X(\omega)|$ 做 $2 \pi$ 週期積分,因為 DTFT 為 $2\pi$ 週期,故右式 事實上是對所有的頻率積分等於 總能量,那麼被積分項 $|X(\omega)|$ 很自然的被稱作 頻譜密度 spectral (power) density 。 2. 考慮 $x(t)$ 為訊號,則 $\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\left[ n \right]} \right|}^2}} $ 稱作此訊號的 total energy 3. 數學上的觀點,上述提及的 總能量  = 自己與自己在 函數空間做 內積 。 4. 另一種數學上的觀點:若 $x[n]$ 想成向量空間的一個向量,則總能量 $$\sum\limits_{n =  - \infty }^\infty  {{{\left| {x\lef

[機率論] 關於含有 Factorial 函數的求導的注意事項 - Erlang 分佈為例

在某些情況,我們可能會希望對含有 Factorial (比如說 $k!$, $k \in \mathbb{N}$) 的函數 取導數,但在求導 的過程中有些細微的部分需要多加留意。以下我們用一個例子來體現。 令 $m \in \mathbb{N}$,考慮隨機變數 $X$ 配備 Erlang 分佈 $$ F_X(x) := 1 - \sum_{k=0}^{m-1} \frac{(\lambda x)^k}{k!} e^{-\lambda x}, x>0 $$ 試證 其 機率密度函數 (Probability Density Function, pdf) $f_X$ 滿足 \[{f_X}\left( x \right) = \frac{{{{(\lambda x)}^{\left( {m - 1} \right)}}}}{{\left( {m - 1} \right)!}}\lambda {e^{ - \lambda x}}\] (FALSE) Proof: 首先注意到分佈函數可導,故我們可利用 分佈函數的導數 為 密度函數 的性質 ($F'(x) = f(x)$),來求得 $f_X$。現在對 $F_X$ 求導 \[\frac{d}{{dx}}{F_X}(x) =  - \sum\limits_{k = 0}^{m - 1} {\left( {\underbrace {\frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k!}}{e^{ - \lambda x}}}_{**} + \frac{{{{(\lambda x)}^k}}}{{k!}}\left( { - \lambda } \right){e^{ - \lambda x}}} \right)} \]注意到summation的第一項 $(**)$,讀者可能會很自然地認為 $**$ 可寫成 \[\frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k!}}{e^{ - \lambda x}} = \frac{{k{{(\lambda x)}^{k - 1}}\lambda }}{{k\left( {k - 1} \right)!}}{e^{ - \lambda x}}\] 然後試圖對 分子分母的 $k$對消。但注

[機率論] 一類條件機率取極限的問題

Theorem: 令 $X,Y$ 為 jointly continuous, \[ \lim_{h \to 0} P((X,Y) \in A| x < X \leq x +h) = \int_{-\infty}^\infty 1_A(x,y) f_{Y|X}(y|x)dy \]其中 $1_A(\cdot)$ 為 indicator function Proof : 首先觀察 \begin{align*}   P((X,Y) \in A|x < X \leqslant x + h) &= \frac{{P(\left\{ {(X,Y) \in A} \right\},\left\{ {x < X \leqslant x + h} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\    &= \frac{{P(\left\{ {\left( {X,Y} \right) \in A} \right\} \cap \left\{ {X \in \left( {x,x + h} \right]} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\    &= \frac{{P(\left\{ {\left( {X,Y} \right) \in A} \right\} \cap \left\{ {\left( {X,Y} \right) \in \left( {x,x + h} \right] \times \mathbb{R}} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\    &= \frac{{P(\left( {X,Y} \right) \in A \cap \left\{ {\left( {x,x + h} \right] \times \mathbb{R}} \right\})}}{{P(x < X \leqslant x + h)}} \hfill \\    &= \frac{{\iint\limits_{A \cap \left\{ {\left( {x,x + h} \right] \times \ma

[機率論] 連續隨機變數條件機率的定義

若 $X$ 是連續隨機變數,則其累積機率分配(cumulative distribution function, cdf) \[ F_X(x) := P(X \leq x) = \int_{-\infty}^x f_X(t) dt \]為 (對 $x$ ) 連續函數,故單點機率測度 $P(X=x) =0$。但若我們考慮條件機率的情況事情會變得稍微有點棘手,因為假設我們引入第二個連續隨機變數 $Y$且假設 $X,Y$ 為 jointly continuous,現在我們想計算 $P(Y \in C| X=x)$,由條件機率定義可知 \[ P(Y \in C| X=x) = \frac{P(X=x,Y=c)}{P(X=x)} \]但此時我們發現因為 $P(X=x) =0$,分母是$ 0$。對於這種情況我們該怎麼對 連續隨機機變數定義其條件機率?或者更簡單的說,該怎麼計算(或者定義)$P(Y \in C| X=x)$? 要計算 $P(Y \in C| X=x)$,我們首先考慮 \[ \lim_{h \to 0} P(Y \in C| x<X\leq x + h) \]對任意 $h>0$而言,上述條件機率可寫成 \[P(Y \in C|x < X \leqslant x + h) = \frac{{P(Y \in C,x < X \leqslant x + h)}}{{P(x < X \leqslant x + h)}}\]注意到分子部分等價為 \[P(Y \in C,x < X \leqslant x + h) = P\left( {\left( {X,Y} \right) \in \left( {x,x + h} \right] \times C} \right)\]若 $X,Y$ 為 jointly continuous,則 \begin{align*}   P(Y \in C|x < X \leqslant x + h) &= \frac{{P(Y \in C,x < X \leqslant x + h)}}{{P(x < X \leqslant x + h)}} \hfill \\    &= \frac{{\int_x^{x + h} {\int_C^{} {{

[數理統計] 對平均值的信賴區間

考慮一組 i.i.d. random samples $X_1,X_2,...,$ 配備 期望平均 $m$ 與 變異數 (variance) $\sigma^2$,假設變異已知,但期望平均 $m$ 為未知。我們想對 $m$ 進行估計。一般的做法是採用 sample mean 估計量 \[ M_n := \frac{1}{n}\sum_{i = 1}^n X_i \] 則我們知道 sample mean $M_n \to m$ 當 $n \to \infty$ in probability,此性質稱作 (weak) consistency estimator,但實際上,大多情況之下我們僅僅只能量測有限 $n$ (比如只能做有限次實驗),則我們想問該如何描述紹述 $M_n$ 有多接近 $m$ 呢?此想法為建構 信賴區間的動機:對某些 $\delta >0$ 而言,我們定義 \[ P(m \in [M_n -\delta, M_n + \delta] ) = 1-\alpha \]其中 $[M_n -\delta, M_n + \delta] $ 稱作信賴區間(Confidence interval) 且 $1-\alpha$ 稱作 信心水準 (Confidence level),因此 Confidence interval 是一個隨機集合 而信心水準是 此隨機集合包含未知參數 $m$ 的機率。一般而言,在實務上多使用 $1-\alpha \in [0.9, 0.99]$。 Comments: 1. 上述 $M_n$ 不但為為 真實平均 (或者期望值) $m$  的 consistent estimator 且 亦為不偏 (unbiased)估計量。 問題: 給定 $\alpha$,我們想問該如何選取參數 $\delta$ 使得 \[ P(m \in [M_n -\delta, M_n + \delta] ) = 1-\alpha \]成立? 要回答此問題,我們首先觀察 \[m \in [{M_n} - \delta ,{M_n} + \delta ] \Leftrightarrow {M_n} - \delta  \leqslant m \leqslant {M_n} + \delta \]亦即 $- \delta  \leqsl

[機率論] 一些常用的機率上界估計-以 exponential 隨機變數為例

令 $X$ 為 exponential 隨機變數配備參數 $\lambda =1$,亦即 $X \sim exp(1)$。試求 $P(X\geq a)$ 並分別利用 Markov inequality, Chebyshev inequalty 與 Chernoff bound 估計此機率的上界。 Proof:  首先回憶 $X \sim exp(\lambda)$ 具有 機率密度 \[f_X\left( x \right): = \left\{ \begin{gathered}   \lambda {e^{ - \lambda x}}\begin{array}{*{20}{c}}   {}&{x \geqslant 0} \end{array} \hfill \\   0\begin{array}{*{20}{c}}   {}&{x < 0} \end{array} \hfill \\ \end{gathered}  \right.\]故 $\lambda =1$ 我們有 \[f_X\left( x \right): = \left\{ \begin{gathered}   {e^{ - x}}\begin{array}{*{20}{c}}   {}&{x \geqslant 0} \end{array} \hfill \\   0\begin{array}{*{20}{c}}   {}&{x < 0} \end{array} \hfill \\ \end{gathered}  \right.\] 現在我們計算 \[ P\left( {X \geqslant a} \right) = \int_a^\infty  {{e^{ - x}}dx}  =  - \left( {0 - {e^{ - a}}} \right) = {e^{ - a}} \] 接著我們用 Markov inequality 估計:令 $a>0$則 \begin{align*}   P\left( {X \geqslant a} \right) &\leqslant \frac{{E\left[ X \right]}}{a} \hfill \\    &= \frac{1}{a

[機率論] 關於配備 Pareto Density 隨機變數 的一個簡單例子

令 $X$ 為隨機變數配備標準 Pareto density,亦即其機率密度函數 $f_X$ 滿足 \[f_X\left( x \right): = \left\{ \begin{gathered}   \frac{2}{{{x^3}}}\begin{array}{*{20}{c}}   {}&{x \geqslant 1} \end{array} \hfill \\   0\begin{array}{*{20}{c}}   {}&{o.w.} \end{array} \hfill \\ \end{gathered}  \right.\] (a) 對任意 $a \geq 1$ 試求 $P(X \geq a)$ (b) 延續 (a),利用 Markov inequality 求其上界。 Proof (a) \begin{align*}   P(X \geqslant a) &= 1 - P\left( {X < a} \right) \hfill \\    &= 1 - \int_1^a {\frac{2}{{{x^3}}}dx}  \hfill \\    &= 1 - 2\left( {\left. {\frac{{{x^{ - 2}}}}{{ - 2}}} \right|_1^a} \right) \hfill \\    &= \frac{1}{{{a^2}}} \hfill \\ \end{align*} Comments: 讀者可注意到上述結果亦可 透過直接計算 \[P\left( {X \geqslant a} \right) = \int_a^\infty  {\frac{2}{{{x^3}}}dx}  = 2\left( {\frac{1}{{ - 2}}\left. {{x^{ - 2}}} \right|_a^\infty } \right) = {a^{ - 2}}\] Proof (b): 注意到 $X$ 為取值非負隨機變數,故對任意 $a \geq 1$,利用 Markov inequality, 我們有 \begin{align*}   P(X \geqslant a) &\leqslant \frac{{E\left[

[數學分析] 一類 分式與極小值 的不等式

Theorem 對任意 $i=1,...,m$,若 $a_i \geq 0$ 且 $b_i \geq 0$ 則下列不等式成立 \[ \frac{\sum_{i=1}^m a_i }{\sum_{i=1}^m b_i } \geq \min_i \frac{a_i}{b_i} \] Proof: 令 $i^*$ 為 某 index $i$ 使得 $\min_i \frac{a_i}{b_i}$ 成立,亦即 $i^*$ 滿足 \[\frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}} = \mathop {\min }\limits_i \frac{{{a_i}}}{{{b_i}}}\]我們要證明定理中的不等式成立。以下以各個擊破的方法來求證: CASE 1: 首先注意到若 $a_{i^*} = 0$ 則我們欲證明的不等式自動成立。 CASE 2:  故 假設 $a_{i^*} >0$,注意到若 $b_{i^*} =0$ 則我們得到兩邊不等式為無窮,故不等式仍然成立,故我們不妨假設  $a_{i^*} >0$ 且 $b_{i^*} > 0$ (*),現在觀察 \[ \frac{{\sum\limits_{i = 1}^m {{a_i}} }}{{\sum\limits_{i = 1}^m {{b_i}} }} = \frac{{{a_{{i^*}}} + \sum\limits_{i = 1}^{m - 1} {{a_i}} }}{{{b_{{i^*}}} + \sum\limits_{i = 1}^{m - 1} {{b_i}} }} = \frac{{{a_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{a_i}}}{{{a_{{i^*}}}}}} } \right)}}{{{b_{{i^*}}}\left( {1 + \sum\limits_{i = 1}^{m - 1} {\frac{{{b_i}}}{{{b_{{i^*}}}}}} } \right)}}\;\;\;\; (**) \]注意到對任意 $i$ 而言,我們有 \[\frac{{{a_{{i^*}}}}}{{{b_{{i^*}}}}} \leqslant \frac{{{

[訊號與系統] Frequency Modulation 淺嚐:Chirp Signal

回憶一般 弦波訊號 \[ z(t) = A \cos(2 \pi f_0 t + \phi) = Re\{A e^{j (2 \pi f_0 t + \phi)}\} \]其中 $A$ 為振幅 ,$f_0$ 為頻率,$\phi$ 為相位。由上式,我們可以定義 $z(t)$ 的 "角度" 記作 \[ \psi(t) := 2 \pi f_0 t + \phi \]由於上式為 linear in $t$ ,我們可觀察 \[ \frac{d}{dt} \psi(t) = 2 \pi f_0 := \omega_i(t) \] 故 $z(t)$ 的角度 隨時間的瞬時變化率 為 $2 \pi f_0$  其單位為 (rad/s) ,若我們將其除掉 $2\pi$ 即可得到 (瞬時)頻率 $f_0$ (單位為 Hz)。 上述想法可以被進一步推廣如下: Frequency Modulation (FM) Signal 現在我們將上述 $z(t)$ 做進一步簡單的推廣:假設 \[ x(t) := A \cos(\psi (t)) = Re\{e^{j \psi(t)}\} \]則我們可仿造前述的方法來定義 瞬時頻率 (instantaneous frequency),亦即我們先對 $\psi(t)$ 對 $t$ 微分,可得瞬時角頻率 (instantaneous angular frequency) \[ \omega_i(t) :=  \frac{d}{dt} \psi(t) \]若對上式兩邊同除以 $2 \pi$ ,可得瞬時頻率 (instantaneous frequency), 記作 $f_i(t)$, 如下 \[ f_i(t) :=\frac{1}{2\pi}\omega_i(t) =  \frac{1}{2 \pi} \frac{d}{dt} \psi(t) \]單位為 Hz。 以下我們看個 FM 調頻中的一類特殊例子,假設我們想要創造一組 弦波訊號 使其 頻率可以包含一段我們感興趣頻段,比如說我們想創造一組聲音其頻率 從 300 Hz 並且一路往上到 800 Hz,一種常見的做法是採用 chirp signal 來達成,其特性如下:給定初始頻率 $f_{int}$ 與 終點頻率 $f_{end}$,

[訊號與系統] Amplitude Modulation 淺嚐:Beat Signal

回憶一般 弦波訊號 \[ x(t) := A \cos(2 \pi f_c t + \phi) \] 其中 $A$ 為振幅,$f_c$ 為 (載波) 頻率,$\phi$ 為相位。現在我們考慮將上述弦波做進一步簡單的推廣如下:假設 振幅 $A$ 不再是常數,而是隨時間變化的函數 比如 $A:=a(t)$ ,則我們得到\[ x(t) = a(t) \cos(2\pi f_c t +\phi) \] 上述稱為 振幅調變 (Amplitude Modulation) 的一般形式,其中 $a(t)$ 為 依時間變化的函數 且一般而言,假設 $a(t)$ 的最高頻率 $f_a << f_c$。 Comments: 1. 震幅 $a(t)$ 隨時間變化,可看成 振幅 被 "調變"(modulation) 2. 一般實際應用上, $a(t)$ 為多半為實際帶有信息的訊號 (比如 聲音,歌聲,影像...) 且其最高頻率會遠遠低於 載子頻率 $f_c$ ,使得我們在做 AM 處理之後,$a(t)$ 訊號可被方便傳送。 3. 當然,對於 $z(t)$ 的推廣不僅僅限於頻率,我們也可以對其頻率推廣,比如說將固定 $f_c$ 改成 $f_c:=\psi(t)$ 使其成為與時間有關的函數,此法會得到所謂的 頻率調變(Frequency Modulation, FM) 我們會另外再開一篇文章描述之,在此不做贅述。 以下我們看個經典的AM例子: AM Example: Beat Signal or Sinusoidal AM 以下我們看個特例:假設 $a(t) := A \cos(2 \pi f_a t)$ 則我們得到 AM 訊號如下 \[ x(t) = A \cos(2 \pi f_a t)  \cos(2\pi f_c t +\phi) \]上述訊號可以透過 Inverse Euler formula 將其改寫為 \begin{align*}   x(t) &= A\cos (2\pi {f_a}t)\cos (2\pi {f_c}t) \hfill \\    &= A \left( \frac{{{e^{j2\pi {f_a}t}} + {e^{ - j2\pi {f_a}t}}}}{2} \rig

[凸分析] 定義在凸集上的凸函數其相對極小即為全域極小

這次要介紹凸分析 或者 凸優化 中可以說是最重要的結果: ===================== Theorem: 令 $f$ 為 convex on convex set $\Omega$。則 1. $f$ 的任意 相對極小點 $x^*$ (local minimum of $f$ on $\Omega$) 必為 全域極小點 (global minimum of $f$ on $\Omega$) 2. 上述 凸函數的極小點所成之集合為凸集,亦即 \[ S:= \{x \in \Omega: f(x) = f(x^*)\} \]為凸集。 ===================== Proof (1): 利用反證法:令  $y \in  \Omega$ 為 $f$在 $\Omega$ 上的相對極小點,亦即存在 $\delta>0$ 使得鄰域 $$N_\delta(y):=\{z: ||z-y|| < \delta\} \subset \Omega$$ 且 \[ f(y) \leq f(x), \;\;\; \forall x \in N_\delta(y) \] 但 $y$ 不為 global minimum :亦即 存在 $x^* \in \Omega$ 使得 \[ f(x^*) < f(y) \]我們要證明此假設矛盾。 首先注意到 $x^* \notin N_\delta(y)$ 因為若不然,則 $f(y) \leq f(x^*)$ 此與假設不符。 現在,我們利用 $x^*$ 與 $y$ 來定義一個 新的點 \[ z(\alpha):= (1-\alpha)y +   \alpha x^*, \;\;\; \alpha := \frac{\delta}{2||y-x^*||} \in (0,1) \]注意到 $z(\alpha) \in \Omega$ (因為 $\Omega$ 為凸集) 且我們觀察 \begin{align*}   |z\left( \alpha  \right) - y|| &= \left\| {  (1 - \alpha ) y + \alpha x^* - y} \right\| \hfill \\    &= \left\| {\alpha

[凸分析] 一階可導凸函數利用單點近似必定低估

Theorem:  令 $f \in C^1$ 且 $f$ 為 convex on convex set $\Omega \subset \mathbb{R}^n$ 若且唯若 對任意 $x,y \in \Omega$ 而言, \[ f(y) \geq f(x) + \nabla f(x) \cdot (y-x) \]其中 $\nabla f(x) \cdot (y-x) := \nabla f(x)^T (y-x)$ 給出證明之前我們先給一些直觀上的看法: Comments: 1. 上述定理算是相當直覺,簡而言之就是說 affine (in $y$) function: $ f(x) + \nabla f(x) (y-x)$ 可以做為 凸函數 $f$ 在 $x$ 點附近的 1 階 Taylor 近似,如下圖所示: 2. 注意到上述定理闡述的不等式對於所有 $x,y \in \Omega$ 都成立,也就是說透過 對$x$ 一階 Taylor 近似必定低估,一般 $f(x) + \nabla f(x) (y-x)$ 又稱作 global underestimaotr  of $f$。 3. 上述結果指出利用局部資訊 (一階導數) 可以得到 全域資訊 (global understametor )。 4. 若 $\nabla f(x) = 0$ 則對任意 $y \in \Omega$,我們有 \[ f(y) \geq f(x) \]亦即 $x$ 為 全域及小點 (global minimizer) of $f$ 以下我們給出證明 Proof: 先證明   $(\Rightarrow)$ 令 $f \in C^1$ 且 $f$ 為 convex on convex set $\Omega \subset \mathbb{R}^n$,給定任意 $x,y \in \Omega$ ,我們要證 \[ f(y) \geq f(x) + \nabla f(x) (y-x) \] 由於  $f$ 為 convex,令 $\alpha \in (0,1)$ 且定義 $$ z(\alpha) := \alpha x + (1-\alpha) y $$則 $z(\alpha) \in \Omega$ 且由 $f$的凸性,我們

[最佳化理論] 有限維空間 無拘束最佳化問題 的二階充分必要條件

回顧先前我們討論過的一階必要條件,以下我們介紹有限維空間 無拘束最佳化問題的 二階必要與充分條件,首先是二階必要條件: ==================== Theorem: Second-Order Necessary Condition, SONC: 令 $S \subset \mathbb{R}^n$ 且令 $f \in C^2(S)$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 則 對 在點 ${\bf x}^*$的任意可行方向 ${\bf d} \in \mathbb{R}^n$,我們有 1. $\nabla f({\bf x}^*) \cdot {\bf d} \geq 0$ 2. 若 $\nabla f({\bf x}^*) \cdot {\bf d} =0$ 則 ${\bf d}^T \nabla^2 f({\bf x}^*) {\bf d} \geq 0$ ==================== Proof: 由於 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 對條件 1 自動成立。我們僅需證明條件2。令  ${\bf d} \in \mathbb{R}^n$ 為 在點 ${\bf x}^*$的任意可行方向,故存在 $\bar \alpha >0$ 使得 \[ {\bf x}(\alpha) := {\bf x}^* + \alpha {\bf d} \in S, \;\;\; \alpha \in [0, \bar \alpha] \] 利用 Taylor Theorem 對 ${\bf x}^*$ 展開到二階項,我們可得 \begin{align*}   f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) &= f\left( {{{\mathbf{x}}^*}} \right) + \nabla f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) \\ & \h

[最佳化理論] 有限維空間 無拘束最佳化問題 的一階必要條件

令 $f: \mathbb{R}^n \to \mathbb{R}$ 且 $S \subset \mathbb{R}^n$ 為 feasible set,現在我們考慮以下的 有限維度 (無拘束)最佳化問題 \[\begin{gathered}   \min f\left( {\mathbf{x}} \right) \hfill \\   s.t.{\mathbf{x}} \in S \subseteq {R^n} \hfill \\ \end{gathered} \] 我們想知道上述最佳化問題是否有解? 若有解則是哪一種解 e.g., 局部最佳解(local optimum)或者 全域最佳解(global optimum)?),以及上述的解是否能夠透過某種方法來將其描述。 對於上述有限維度最佳解的存在性問題一般可由 Weierstrass Extremum Theorem處理,在此不做贅述。以下我們討論 最佳解 存在的必要條件:更近一步地說是 最佳化理論中的求取 "局部最佳解" 的一階必要條件,在給出結果之前我們首先定義 可行方向 (Feasible Direction)如下: ====================== Definition: Feasible Direction 給定 ${\bf x} \in S \subset \mathbb{R}^n$,我們說向量 ${\bf d} \in \mathbb{R}^n$ 為 在 ${\bf x}$ 處的可行方向 (feasible direction) 若下列條件成立:存在常數 $ \bar \theta >0$ 使得對任意 $\theta \in [0, \bar\theta]$而言, \[ {\bf x} + \theta {\bf d} \in S \]====================== 有了以上的可行方向的想法,其局部最佳解的一階必要條件有如下陳述: ====================== Theorem: (First Order Necessary Condition, FONC):  令 $S \subset \mathbb{R}^n$ 且 $f \in C^1$ on $S$ ( $f$為一階可導且導數連續)

[控制理論] 非線性模型預測控制 (0) - 引論

此文我們針對 非線性模型預測控制 (Nonlinear Model Predictive Control, NMPC) 做簡單的介紹: 是一套針對受控廠為 非線性系統 所發展的 回授控制理論,其控制律透過不斷求解最佳化問題而得。以下我們將其簡稱 NMPC。 基本想法: 假設你是一個圍棋高手正在與旗鼓相當的對手對弈,那麼你可能在心中盤算好幾步可能的走法 並同時 試圖來 "預測" 對手的路數,但輪到自己下子的時候,我們只能選取剛才在心中盤算出的所有走法中 " 最佳" 的那一步,並且只動那一步旗,動了之後都必須重新盤算上述過程。這個精神大概與 模型預測控制 本質幾乎相同。就是逐步最佳化,慢慢朝向目標前進。以下我們會逐步將此概念規範化,讀者可以讀完之後再回頭瞧瞧這個基本想法,也許會發現異曲同工之妙。 對 $n=0,1,2,...$,令 $x(n)$ 為當前系統狀態 且 $x^{ref}(n)$ 為 給定的參考目標軌跡。 模型預測控制 的 主要目的: 與一般控制問題相仿,模型預測控制的主要目的不外乎以下兩大類問題: 1. 鎮定(stabilizing)問題。使預測的狀態軌跡 盡可能趨近 零點。 2. 追蹤(tracking)問題。使 預測的狀態軌跡 盡可能跟隨給定的 參考目標軌跡 。 Comments: 1. 若稍有控制背景的讀者不難發現鎮定問題其實是追蹤問題的特例,更進一步地說,所謂追蹤控制問題是指:決定一組控制輸入 $u(n)$ 使得 $x(n)$ 能盡可能緊跟給定的參考狀態軌跡 $x^{ref}(n)$。換而言之,若當前狀態 $x(n)$ 與 $x^{ref}(n)$ 所差甚遠,則我們將盡可能控制此系統軌跡趨近 $x^{ref}(n)$:若當前狀態 $x(n) = x^{ref}(n)$ 則我們將盡可能控制此系統"維 持"在該狀態。 2. 關於鎮定問題提及的對零點追蹤 或者 追蹤問題的參考目標軌跡,都必須滿足隱藏的前提: 零點 或者 參考目標軌跡 必須是系統的 平衡點 (equilibrium point)。否則該系統無法進行鎮定 or 追蹤。 以下我們將介紹一類簡化的 NMPC 問題,並藉此展示此控制方法的一些基本精神。 一類簡化的非線性模型預測控制問題: 令

[最佳化] 無窮維 Weierstrass 極值定理

=================== Infinite Dimensional Weierstrass Extreme Theorem: 令 $X$ 為 normed vector space 且 $K \subset X$ 為 compact set 。若 $f$ 為 upper semicontinuous on $K$ 則 $f$ 在 $K$上可達到最大值,亦即 存在 $x \in K$ 使得 \[ f(x) = \sup_{z \in K} f(z) \]================= Proof: 要證明   $f$ 在 $K$上可達到最大值,亦即 存在 $x \in K$ 使得 \[ f(x) = \sup_{z \in K} f(z) \]上式等價為 \[ f(x) \geq \sup_{z \in K} f(z) \;\;\; \text{and } \; f(x) \leq \sup_{z \in K} f(z) \] 注意到 $f(x) \leq \sup_{z\in K} f(z)$ 為顯然,故以下僅需證明\[ f(x) \geq \sup_{z \in K} f(z) \] 令 $M:= \sup_{z \in K} f(z)$ 則由 supremum 性質可知存在數列 $\{x_n\} \subset K$ 使得 \[ f(x_n) \to M \;\;\;\; (*) \] 由於 $K$ 為 compact 故必定存在 $\{x_n\} $ 的子數列 記作 $\{x_{n_k}\} \subset K$  使得其收斂在  $x \in K$ ,另外由於 式子 $(*)$ ,我們可推知子數列亦滿足 \[ f( x_{n_k} ) \to M \;\;\;\; \text{ as $k \to \infty$}  \]由於 $f$ 為 upper semicontinuous on $K$,可知 \[ \limsup_{z \to x} f(z) \leq f(x) \]由 $\limsup$ 的 數列與函數數列性質 ,我們有 \[ \limsup_{k \to \infty} f(x_{n_k}) \leq \limsup_{z \to x} f(z)  \;\;\;\; (\st

[泛函分析] Bessel's Inequality

下列 Bessel's inequality 在 泛函分析 與 Fourier 分析中扮演重要角色,此不等式表示給定任意在 Hilbert Space 中的點 $x$ (e.g., $L^2$ 空間上 封閉子集的函數), 且給定一組 Hilbert Space 上的正交基底函數 (e.g., complex exponential function, $\{e_i\}$) 則 任意點 $x$ 透過 $\{e_i\}$ 作為基底展開的係數平方和 有上界 且此上界剛好為 $||x||^2$。此不等式的證明要求對內積的性質有進一步掌握,個人認為是很好的練習。 ====================== Theorem: Bessel's Inequality 令 $H$ 為 Hilbert Space 且 $x \in H$。若 $\{e_i\} \subset H $ 為一組 orthonormal sequence 則 \[ \sum_{i=1}^\infty | \langle x,e_i \rangle |^2 \leq ||x||^2 \]其中 $\langle \cdot, \cdot \rangle$ 為 $H$ 上的內積運算。 ====================== Proof: 令 $\{e_i\} \subset H $ 為一組 orthonormal sequence 且 $x \in H$,現在觀察 $x$ 與 部分和$\sum_{i=1}^n \langle x, e_i \rangle$ 的差異 (透過內積): \begin{align*}   0 \leqslant {\left\| {x - \sum\limits_{i = 1}^n {\langle x,{e_i}\rangle {e_i}} } \right\|^2} &= \left\langle {x - \sum\limits_{i = 1}^n {\langle x,{e_i}\rangle } {e_i},x - \sum\limits_{i = 1}^n {\langle x,{e_i}\rangle {e_i}} } \right\rangle  \hfill \\    &= \left\langl

[數理統計] 一致性估計 與 弱大數法則

以下討論 點估計理論 中一些比較重要的性質與應用。 令 $\Theta$ 為某參數空間。 =================== Definition: (Point) Estimator and Estimate 給定 $X_1,...,X_n$ 為 i.i.d. 隨機試驗 來自 pdf $f(x;\theta)$ 其中 $\theta \in \Theta$ 為未知參數,現在定義新的隨機變數 $\widehat \theta$ 為  $X_1,...,X_n$ 的函數,寫為 \[ \widehat \theta := \widehat \theta(X_1,...,X_n) \]則我們稱此 $\widehat \theta$ 為用以估計參數  $\theta$ 的估計量 (estimator of $\theta$),且若我們能取得隨機樣本的觀察值,比如 $X_1 = x_1,X_2=x_2,...,X_n = x_n$ 則我們稱 \[ \widehat \theta := \widehat \theta(x_1,...,x_n) \]為參數 $\theta$ 的估計值(estimate) =================== Comments: 1. 參數 $\theta$ 為分配中的未知常數,但估計量 $\widehat \theta$ 為隨機變數 2. 在數理統計中的 隨機取樣 與 機率論中 iid 隨機變數 視為等價敘述。 3. $\widehat \theta$為  $X_1,...,X_n$ 的函數,但與 $\theta$ 無關!在數理統計中稱此與待估計參數無關的性質為 統計量 ( statistic )。 那麼怎樣的估計量才算是 "好" 的估計量?以下給出一些常見的 "好" 估計量定義。 =================== Definition: What "Good" Properties Should an Estimator Hold?  令 \[ \widehat \theta := \widehat \theta(X_1,...,X_n) \] 為某未知參數 $\theta$ 的估計量,則 我們稱 $\wideh

[機率論] Chebyshev's Inequality 的推廣型

以下介紹一個在機率論中 相當有用的 一條不等式,稱為 Chebyshev inequality,此不等式將 期望值 與 機率測度 做出一定程度的連結 來用以估計 期望值的下界 (或者說 求某機率測度的上界)。以下我們給出此不等式之陳述與證明:讀者可注意要求的假設條件並不多,證明也稍具巧思。 ================ Theorem: Generalized Chebyshev's Inequality  令 $X$ 為 任意 連續型 隨機變數 配備 機率密度函數 $f_X$ ,現在定義 $g(X)$ 為任意非負函數,若 $E[g(X)]$ 存在,則 對任意常數 $c>0$,我們有 \[ P(g(X) \geq c) \leq \frac{E[g(X)]}{c} \]================ Proof:  假設 $X$ 為連續型隨機變數且 $E[g(X)]$ 存在,令 $c >0$ 為任意正值常數。由於期望值 $E[g(X)]$ 存在,由定義可知我們有 \[ E\left[ {g\left( X \right)} \right] = \int_{ - \infty }^\infty  {g\left( x \right){f_X}\left( x \right)dx} \]其中 $f_X(x)$ 為 $X$ 的 機率密度函數 (Probability Density Function, pdf)。現在觀察上述右式積分,我們可將其等價寫為 \begin{align*}   \int_{ - \infty }^\infty  {g\left( x \right){f_X}\left( x \right)dx}  &= \int_{\left\{ {x:g\left( x \right) \geqslant c} \right\}}^{} {g\left( x \right){f_X}\left( x \right)dx}  + \int_{\left\{ {x:g\left( x \right) < c} \right\}}^{} {g\left( x \right){f_X}\left( x \right)dx}  \hfill \\  &  \geq \int_{\left\

[機率論] 動差生成函數 的 常見應用 (1)

令 $\Omega$ 為 樣本空間,定義 $X : \Omega \to \mathbb{R}$ 為配備 機率分配函數 $f_X$ 的 隨機變數。 ================== Definition: k-th Moment 隨機變數 $X : \Omega \to \mathbb{R}$  的 k階 動差 (k-th moment) 定為 $E[X^k]$ ================== ================== Definition: Moment Generating Function 令 $X$ 為隨機變數,若存在 $\delta >0$ 使得對 $t \in (-\delta,\delta )$ 而言,期望值 $E[e^{tX}]$ 存在,則 $X$ 的 動差生成函數 (Moment Generating Function, mgf) 存在,且定義為 \[ M_X(t) := E[e^{tX}], \;\;\; t \in (-\delta,\delta ) \]除此之外,若上述條件成立則 \[ D_t^k E[e^{tX}] = E[D_t^k e^{tX}] \]其中 $D_t^k $ 表示為對 $t$ 微分 $k$次 微分算子。 ================== Comments: 1. 動差生成函數 $M_X(t)$ 是一個以 $t$ 為變數 的函數,目的在於 "產生動差",至於如何產生我們會在下面進行討論。 2. 上述定義僅僅要求 mgf 在 $t = 0$ 附近開區間 $t \in (-\delta, \delta)$ 期望值存在,此條件也保證積分與微分互換性。 3. 若在開區間 $ t \in (-\delta, \delta)$ 期望值存在,立刻可得知 $M_X(0) = E[e^{0}] = 1$ FACT:  上述動差生成函數算是非常便利的工具,我們可以透過其產生各種具有常見分配的隨機變數之一,二階動差。假定某隨機變數之 mgf 存在,則此隨機變數的 k-th 動差表為 \[ D_t^k M_X (0) = E[X^k], \;\; k=1,2,... \] Comment: 由上述討論可知,若我們想求期望值則

[訊號處理] 2d Convolution & 簡單的影像處理 (利用 MATLAB )

一般在處理影像的時候我們會把 影像(image) 視為 二維離散訊號, 更一般的說法是將其視為矩陣,亦即給定任一張 (灰階) 影像 我們可以將其分割成 $M \times N$ 矩陣 (像素 pixel),並且將其記作 $x[m,n]$,其中 $m=0,...,M-1$ 與 $n = 0,...,N-1$ 。 Comments: 如果要處理的影像是彩色的,一個常用的做法是把該影像以 $R,G,B$ 三色分別存成 三個矩陣,最後在做疊合。在此不做贅述。 以下我們利用 MATLAB 來執行 (灰階)影像處理,我們使用的圖檔是 MATLAB內建的圖檔 cameraman.tif ,當然讀者可自行讀入任何自己想要的圖檔。在MATLAB 輸入 MATLAB Code For Loading the Image x = imread( 'cameraman.tif' ) imagesc(x) 則會顯示 圖1a: cameraman.tif 原圖 ($256 \times 256$) Comments: 1. 上述影像訊號 $x[m,n]$ 為 $M \times N = 256 \times 256 $ 矩陣。 2. 一般而言在影像處理領域,我們將圖片最左上角點視為座標原點,對應的影像訊號為 $x[0,0]$ 。 3. 上述影像透過 MATLAB 2017a 讀圖會顯示有一些藍綠等顏色,若要使此圖顯示為灰階(gray scale) 讀者可鍵入 colormap(gray) 來使其變成灰階影像,亦即 MATLAB Code For Gray Scale Colormap x = imread( 'cameraman.tif'  ) imagesc(x) colormap(gray) 則我們會得到如下圖 圖1b: 灰階影像 現在我們可對上述影像進行一些常見的基本處理。令 $x[m,n]$ 為輸入影像訊號,且假設 影像 濾波器 為 線性非時變 (Linear Time Invariant, LTI) 故其對應的 impulse response $h[m,n]$ 可以用來完全描述我們的影像濾波器,最後 我們令 影像處理過後的輸出訊號 $y[m,n]$ 可表為 $x[m,n]$