跳到主要內容

文章

[數學分析] 一類 max/min operator 作用在分式 的等式

令函數 $f: \mathbb{N} \to (0,\infty)$,則下列等式成立 $$ \min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)} $$ Proof:  令 $$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)} $$ 其中 $\ell_0\leq k_0$ 使得  $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。 另一方面,令 $$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)} $$ 且 $\ell_1\leq k_1$,則我們必定有 $$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$ 由上述結果,我們得到 $$ \frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)} $$ 亦即 $$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$
最近的文章

[隨筆] 博士之路的感謝

六十餘年妄學詩,功夫深處獨心知 夜來一笑寒燈下,始是金丹換骨時 陸游 --- 夜吟 --- 昨天 (12/17/2019) 我完成了我的博士論文答辯。我想趁著一切記憶還鮮明的時候 寫寫我的想法與心中的感謝。 心境 從 2013 到執筆寫下這篇文章的今天,六年多將近七年的留美歲月恍如昨日,當日少年轉眼變成大叔。我猶記剛剛踏上 Madison, Wisconsin 時候的大雪紛飛與零下 20 度的氣溫。我瑟瑟發抖,套上好友送的防寒手套,心中想著即將與剛新婚不久的 太太 順瑩 分離,經濟上與課業上的全新挑戰。這是個用英文點杯咖啡都顯得結巴困難的日子。 關於課業與研究 我是在 UW-Madison   電機與電腦工程系  攻讀博士,主修 控制系統 輔修 數學。我有幸師從 B. Ross Barmish 教授,他是 強健控制 與 控制工程 在財務應用 的幾位領頭人物之一。 我主要研究領域是落在 隨機系統 與 財務工程 的交集 1 。讀博期間我很慶幸有許多師長的幫助,順道取得同校的 數學與電機 雙碩士學位,加上我原本在台灣的機械碩士,僥倖集滿了三碩,多了幾根白髮,發了幾篇文章。最開心的大概是我終於可以厚顏自稱自己是 (應用) 數學家 。 彷彿又更接近了一點當年在大學時候的夢想:成為一位 控制理論 學者。 讀博過程,除了研究之外,更常時候是在等待論文審核的時光中度過。填補這個等待就是做新的研究。一個挖坑又自己填坑的過程。很多煎熬,很多難關。許許多多的人在這路上幫助過我,或先或後,或直接或間接,難以計數,我由衷謝謝他們。 關於經濟 除了幾個特定 超熱門領域 之外,做理論研究並沒有太多經費。所以我得在 興趣 與 麵包 之間做選擇。我選了前者,也因此開啟了長年教課的日子。我感謝 UW-Madison  數學系 與 電機系 願意給我機會擔任 助教 或者 講師 職位。我由衷謝謝他們。 關於博士答辯之後與博士頭銜 答辯之前與答辯之後並沒有不同,答辯之後並沒有讓我對研究領域的認識就瞬間有了質的飛躍,更多時候是細水長流的累積直到答辯的那一刻。論文答辯 本身 不過是給我一個機會 分享總結 自己過去這些年的一些些研究成果。若要說博士頭銜有什麼作用,大概就是讓我得到了一個奢侈的特權:得到申請 助理教授 職位被拒絕的特權。希望這個特權不

[分享] 板橋教會敬拜讚美團 『決定,回家』 20週年 紀念音樂專輯

板橋教會敬拜讚美團 『決定,回家』 20週年 紀念音樂專輯。 整張專輯: 謝謝你們。

[凸分析] 凸優化最佳解所成之集合為凸集

在凸優化問題中,僅管凸性保證了任意局部最優解 (local minimizer) 就是 全局最優解 (global minimizer),但凸性並沒有保證所考慮的凸優化問題 一定 存在 最優極小解。下面的結果刻劃了凸優化最佳解的性質,常被用來檢驗最佳解的存在性,是個十分有用的結果。 =========== Theorem: (凸優化最佳解的集合為凸集) 令 $S \subseteq \mathbb{R}^n$ 為 凸集合 且 $f: S\to \mathbb{R}$ 為 凸函數。令 $S^*$ 為所有極小點所成之集合亦即 \[ S^* := \{x\in S: f(x) \leq f(y), \forall \; y \in S\; \} \] 則 $S^*$ 為凸集。 =========== Proof : 若 $S^* = \emptyset$ 則上述定理陳述自動成立。若 $S^* \neq \emptyset$,則存在 $x_0 \in S^*$。考慮 level set \[ S_{\leq f(x_0)} := \{x\in S: f(x) \leq f(x_0)\} \] 則不難驗證 $S_{\leq f(x_0)} = S^*$。接著由下述 Lemma 可知 $S^*$ 為 convex。至此證明完畢。$\square$ =========== Lemma:  令 $S \subseteq \mathbb{R}^n$為凸集,且 $f:S \to \mathbb{R}$  為凸函數。則對任意 $\alpha \in \mathbb{R}$, (lower) level set $$ S_{\leq \alpha}:= \{x \in \mathbb{R}^n: f(x) \leq \alpha\} $$ 為 凸集。 =========== Proof:  若 level set $S_{\leq \alpha}$ 為空集合或者單點集,則陳述自動成立。若不然,取 $x_1,x_2 \in S_{\leq \alpha}$ ,則 $f(x_1) \leq \alpha$ 且 $f(x_2) \leq \alpha$。我們要證明 convex combination of $x_1$ 與 $x_2$ 仍落在 $

[機器學習] 主成分分析 (1)

以下我們介紹機器學習/統計學習理論 中把 高維度資料 降維 的一種常用工具,稱作 主成分分析 (Principal Component Analysis) 。假設我們有 $n$ 組 $m$ 維度 (去除平均) 資料點集,下圖 顯示 $n=100$ 組 $m=2$ 維 資料點集 注意到上述資料集已經先預先處理使其資料集 中心 在 $(0,0)$。任意(有限維度)資料集皆可預先做此處理將其資料點的平均值 預先 移除。此為主成分分析的首要步驟。 主成分分析(Principal Component Analysis): 我們的目標為 找到一個向量 ${\bf x} \neq {\bf 0}$ 使得 由此向量所 線性張成(span) 的子空間,記作 $X:=span\{{\bf x}\}$ ,能 最佳適配我們得資料集 (此 subspace $X$ 又稱作 "best line ") 使得\[ \min_{\bf x} \sum_{i=1}^n d_i^2 \]其中 $d_i$ 為第 $i$ 個 資料點 到此  best line (subspace) $X$ 的距離。 Comments: (1) 此處最佳 "best line" 意指我們要找 ${\bf x}$ 使得 資料點到此 best line 的距離平方最小,此想法可參閱下方示意圖,其中 ${\bf a}_i$ 為代表 第 $i$ 個資料點的向量,$proj_X{\bf a}_i$ 代表 ${\bf a}_i$ 投影到 我們的 subspace $X$ 的投影向量。 (2) 當然,距離平方最小並不是唯一的選擇,讀者可以考慮使用 $\sum_i |d_i|$ 當作 最佳化的目標函數或者其他種類的目標函數,但為求簡單起見,且符合經典 主成分分析的內容,在此我們僅考慮 距離平方誤差 作為我們的 目標函數。 (3) 由下圖,讀者不難發現對任意資料向量 ${\bf a}_i$ 而言,此向量 與 subspace $X$ 的 距離平方 $d_i^2$ 可表為 \[ d_i^2  = \| {\bf a}_i - proj_X {\bf a}_i \|_2^2 \]其中 $proj_X {\bf a}_i$ 表示 ${\bf a}_i$ 投影到 sub