謝宗翰的隨筆

這次要介紹機率論中一個重要的概念：期望值 (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: 非負隨機變數 的期望值：

對任意 非負隨機變數 $Y$ $(Y : \O…

這次要跟大家介紹離散時間的動態規劃 (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. 關於 Performance Index
\[
J(u) := \d…

延續上篇文章 [最佳化] 淺談 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)||})$ 求得)

對於Steepest Descent Algorithm而言，我們有 現在的跌代…

這次要介紹的是最陡坡度法(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 \frac{v}{{\left\| v \right\|}}} \rig…