跳到主要內容

發表文章

目前顯示的是 4月, 2009的文章

[機率論] 期望值 與 Lebesgue 積分

這次要介紹機率論中一個重要的概念:期望值 (Expectation),本質上期望值被視為一個 Lebesgue 積分。更進一步地說就是在較抽象的高等機率論中, 期望值被定義為對某機率測度 (Probability measure, $P$ ) 的 Lebesgue 積分 。亦即 考慮機率空間為 $(\Omega, \mathcal{F}, P)$,則 $E[X]$ 具有如下形式: \[ E[X] := \int_{\Omega} X d P  = \int_\Omega X(\omega) P(d\omega) \] 我們由 Simple Function 出發 逐步建構 Lebesgue integral: Step 1: Simple function 的期望值: 首先,我們定義 $X$ 為一個 simple function。亦即此函數可由 可測集合 (measurable sets $A_i$ ) 的 Indicator function 所組成。我們將其寫作是 Finite sum 如下: \[ X = \displaystyle \sum_{i=1}^{n} c_i 1_{A_i} \]其中 $c_i \in \mathbb{R}$, $A_i \in \mathcal{F}$ 且 \[{1_A}\left( x \right): = \left\{ \begin{array}{l} 1,\begin{array}{*{20}{c}} {} \end{array}if\begin{array}{*{20}{c}} {} \end{array}x \in A\\ 0,\begin{array}{*{20}{c}} {} \end{array}if\begin{array}{*{20}{c}} {} \end{array}x \notin A \end{array} \right.\]則我們定義 對此 Simple function $X$ 的期望值 (或稱對此 Simple function 的 Integral)為 \[ E[X] := \int X dP := \sum_{i=1}^n c_i P( \{A_i\} ) \]接著,我們定義對 非負隨機變數 的期望值: Step 2:  非負隨

[動態規劃] 淺談 離散時間動態規劃 (0) - Principle of Optimality & Bellman equation in Finite Horzion

這次要跟大家介紹離散時間的動態規劃 (Dynamic Programming, D.P.) 問題: 此為最佳化理論中的一種方法,由 Professor Bellman 的 Principle of Optimality 所奠基。 基本想法如下: 從最佳解往回推 (backward),逐步求解最佳值。再從初始位置沿著以求得的最佳路徑前進到最佳解。 我們現在把動態規劃問題寫下: (有限時間) 動態規劃問題 (Dynamic Programming Problem in Finite Horizon): 考慮 Performance index (cost function) \[ J(u) := \displaystyle \sum_{k=0}^{N-1} J(x(k), u(k)) + \Phi(x(N)) \]與離散時間的狀態方程( state equation) \[ x(k+1) = f(x(k), u(k)), \ x(0) \ \text{is given} \\ \]其中 $x(k) \in \mathbb{R}^n$ 為系統在第 $k$ 時刻的 狀態,$u(k) \in \mathbb{R}^m$ 為控制力,函數 $f:\mathbb{R}^n \times \mathbb{R}^m \rightarrow \mathbb{R}^n$, 另外我們仍需考慮控制力拘束條件 \[ u(k) \in \Omega_k(x(k)) \]其中 $\Omega_k$ 為第 $k$ 時刻的拘束條件 Comment: 1. 關於狀態方程:上式中的 $f(x(k),u(k))$ 稱作 autonomous state equation 但事實上DP問題亦可直接考慮 Non-autonomous state equation,(亦即函數中考慮時間 $k$) \[ f((x(k), u(k), k)) \] Example: Autonomous and Non-autonomous system Autonomous state equation:  $x(k+1) = x(k) + u(k)$ Non-autonomous state equation: $x(k+1) = k \cdot x(k)$ 2. 關於

[最佳化] 淺談 Steepest Descent Method (1) - Optimal step size

延續上篇文章 [最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !? ,這次我們要介紹 Steepest Descent Method with Optimal Step size 修訂後的Steepest Descent Algorithm 需要甚麼呢? 初始條件 $u^0$ 最大 跌代步長上限(Maximum fixed step size): $H$ Steepest Descent with Optimal Step size的跌代架構(iterative scheme) \[u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*)\] 演算法停止判別機制(stopping criterion) : EX: \[ ||\nabla J(u^k)|| < \varepsilon\] 那麼問題變成 $h_k$ 該怎麼求? 首先我們考慮第 $k$次 跌代,手上有 $u^k$,則我們可以定義 \[ \tilde J(h) := J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}) \]接著我們做 Line search 找出一個最佳的 $h \in [0,H] $ ( 亦即 $\min \tilde J(h)$) 把此 $h$ 稱做 $h_k $,也就是說 \[ \tilde J(h_k) = \displaystyle \min_{h \in [0, H]} \tilde J(h) \]做Line search之後得到的 $h_k$ 再把他放回 $(*)$ 即可!! \[ u^{k+1} = u^k - h_k \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||} \ \ \ \ (*) \]上式即稱為 Steepest Descent with Optimal Step size (此Optimal step 由Line search 對 $ \min J(u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||})$ 求得) 對於Stee

[最佳化] 淺談 Steepest Descent Method (0) -Why Steepest !?

這次要介紹的是最陡坡度法(Steepest Descent Method),又稱 Gradient descent method: 想法: 透過負梯度 (negative gradient) 作為最陡坡度,逐步找到 (局部) 最小值 (最佳解 $u^*$) 這個演算法需要甚麼呢? 初始條件 $u^0$ 固定的 跌代步長(fixed step size): $h$ Steepest Descent 的跌代架構(iterative scheme) \[u^{k+1} = u^k - h \frac{ \nabla J(u^k)}{|| \nabla J(u^k)||}\] 演算法停止判別機制(stopping criterion) : EX: 給定誤差 $\varepsilon>0$,檢驗 \[ ||\nabla J(u^k)|| < \varepsilon\] 那麼現在我們來解決一個問題: 為什麼此法被稱作 "最陡" 坡度?  也就是說 為什麼Iterative scheme 中的方向 $ \nabla J(u^k)$ 被稱做是最陡(Steepest)方向?? 考慮目標函數 $J: \mathbb{R}^n \rightarrow \mathbb{R}$,其在某點 $u^0 \in \mathbb{R}$ 與方向$v$ 的方向導數(Directional derivative at point $u^0$ in direction $v$)定義如下: \[ {\left. {\frac{{\partial J\left( u \right)}}{{\partial v}}} \right|_{u = {u^0}}}: = {\left[ {\nabla J({u^0})} \right]^T} \cdot \frac{v}{{\left\| v \right\|}} \]由Cauchy-Schwarz inequality $\left| {{x^T}y} \right| \le \left\| x \right\|\left\| y \right\|$,可推得上式如下: \[ \left| {{{\left[ {\nabla J({u^0})} \right]}^T} \cdot \