8/14/2016

[變分法] 離散泛函極值的必要條件

此文主要討論離散泛函的極值與其必要條件,也就是所謂的離散版本的 Euler-Lagrange Equation,推薦讀者可先複習先前介紹過的 連續泛函 的極值與必要條件的相關知識,整體推導而言可謂非常類似。

考慮離散泛函
\[\left\{ \begin{align*}
  &J\left( x \right): = \sum\limits_{k = 0}^{N - 1} {F\left( {x\left( k \right),x\left( {k + 1} \right),k} \right)} ; \hfill \\
  &x\left( {{0}} \right) = {x_0};x\left( {{N}} \right) = {x_1} \hfill \\
\end{align*}  \right.
\]其中 $F(x,y,t), \frac{{\partial F}}{{\partial x}}, \frac{{\partial F}}{{\partial y}}$ 在其定義域上連續函數。我們的目標是求序列 $x(0), x(1),...,x(N)$ 使得上述泛函 $J(x)$ 達到極值。

Comments:
前述設定中的離散狀態 $x(k) := x(t_k)$ 其中 $t_k = kT$ 且 $T$ 為取樣週期 (sampling period)

=====================================
Theorem: 離散版本的 Euler-Lagrange Equation
若 $x(1),...,x(N - 1) $ 使得上述泛函 $J(x)$ 達到極值,則對任意 $k=1,2,...,N-1$
\[\frac{{\partial F\left( {x(k),x(k + 1),k} \right)}}{{\partial x\left( k \right)}} + \frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}} =0\]=====================================

Proof: 令 $\delta x(k)$ 為 $x(k)$ 的變分,由於 $x(0) = x_0$ 與 $x(N)=x_1$,故 $\delta x(0) = \delta x(N) =0$ ,現在我們觀察 $J(x)$ ,由假設可知  $x(1),...,x(N - 1) $ 使得泛函 $J$ 達到極值,故
\[
J(x + \alpha \delta x) \geq J(x)
\]且此表明 $ J\left( {x + \alpha \delta x} \right)$ 在 $\alpha =0$ 處達到極值,由變分與泛函極值關係可知
\[
\delta J\left( {x\left( k \right)} \right) = {\left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( k \right) + \alpha \delta x\left( k \right)} \right)} \right|_{\alpha  = 0}} = 0
\]其中
\[J\left( {x(k) + \alpha \delta x(k)} \right) = \sum\limits_{k = 0}^{N - 1} {F\left( {x(k) + \alpha \delta x(k),x(k + 1) + \alpha \delta x(k + 1),k} \right)}
\]因此
\[
\delta J\left( {x\left( k \right)} \right) = {\left. {\frac{\partial }{{\partial \alpha }}\sum\limits_{k = 0}^{N - 1} {F\left( {x(k) + \alpha \delta x(k),x(k + 1) + \alpha \delta x(k + 1),k} \right)} } \right|_{\alpha  = 0}} = 0
\]故我們可推得
\[\begin{align*}
  &{\left. {\frac{\partial }{{\partial \alpha }}\sum\limits_{k = 0}^{N - 1} {F\left( {x(k) + \alpha \delta x(k),x(k + 1) + \alpha \delta x(k + 1),k} \right)} } \right|_{\alpha  = 0}} = 0 \hfill \\
 &  \Rightarrow {\left. {\sum\limits_{k = 0}^{N - 1} {\frac{\partial }{{\partial \alpha }}F\left( {x(k) + \alpha \delta x(k),x(k + 1) + \alpha \delta x(k + 1),k} \right)} } \right|_{\alpha  = 0}} \hfill \\
 &  \Rightarrow {\left. {\sum\limits_{k = 0}^{N - 1} {\frac{{\partial F}}{{\partial x\left( k \right)}}\delta x(k) + \frac{{\partial F}}{{\partial x(k + 1)}}\delta x(k + 1)} } \right|_{\alpha  = 0}} = 0  \;\;\;\; (*)
\end{align*}
\] 現在觀察上式的第二項,利用變數變換 定義 $k:=m-1$ 則我們可改寫為
\[\begin{gathered}
  \sum\limits_{k = 0}^{N - 1} {\frac{{\partial F\left( {x(k),x(k + 1),k} \right)}}{{\partial x(k + 1)}}\delta x(k + 1)}  = \sum\limits_{m = 1}^N {\frac{{\partial F\left( {x(m - 1),x(m),m - 1} \right)}}{{\partial x(m)}}\delta x(m)}  \hfill \\
   = \frac{{\partial F\left( {x(N - 1),x(N),N - 1} \right)}}{{\partial x(N)}}\delta x(N) + \sum\limits_{m = 1}^{N - 1} {\frac{{\partial F\left( {x(m - 1),x(m),m - 1} \right)}}{{\partial x(m)}}\delta x(m)}  \hfill \\
   = \frac{{\partial F\left( {x(N - 1),x(N),N - 1} \right)}}{{\partial x(N)}}\delta x(N) + \sum\limits_{k = 1}^{N - 1} {\frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}}\delta x(k)}  \hfill \\
\end{gathered} \]現在將上述結果代回 $(*)$,故可得
\[\small \begin{align*}
  \delta J\left( {x\left( k \right)} \right) &= \sum\limits_{k = 0}^{N - 1} {\frac{{\partial F}}{{\partial x\left( k \right)}}\delta x(k) + \frac{{\partial F}}{{\partial x(k + 1)}}\delta x(k + 1)}  \hfill \\
  & = \sum\limits_{k = 0}^{N - 1} {\frac{{\partial F}}{{\partial x\left( k \right)}}\delta x(k) + \frac{{\partial F\left( {x(N - 1),x(N),N - 1} \right)}}{{\partial x(N)}}\delta x(N) + \frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}}\delta x(k)}  \hfill \\
 &  = \frac{{\partial F\left( {x(N - 1),x(N),N - 1} \right)}}{{\partial x(N)}}\delta x(N) + \sum\limits_{k = 0}^{N - 1} {\left( {\frac{{\partial F}}{{\partial x\left( k \right)}} + \frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}}} \right)\delta x(k)}  \hfill \\
\end{align*}
\]注意到上式中 $\delta x(N) =0$ 且由於 $\delta x(k)$ 為任意變分,故由 $\delta J = 0$ 我們可知
\[\begin{align*}
 & \frac{{\partial F\left( {x(N - 1),x(N),N - 1} \right)}}{{\partial x(N)}}\delta x(N) +  \hfill \\
  \begin{array}{*{20}{c}}
  {}&{}
\end{array}&\;\;\;\; \sum\limits_{k = 0}^{N - 1} {\left( {\frac{{\partial F\left( {x(k),x(k + 1),k} \right)}}{{\partial x\left( k \right)}} + \frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}}} \right)\delta x(k)}  = 0
\end{align*} \]亦即對任意 $k=0,1,...,N-1$,
\[\frac{{\partial F\left( {x(k),x(k + 1),k} \right)}}{{\partial x\left( k \right)}} + \frac{{\partial F\left( {x(k - 1),x(k),k - 1} \right)}}{{\partial x(k)}} = 0\;\;\;\; \square
\]

8/11/2016

[變分法] 連續泛函極值的必要條件

這次要介紹最簡單形式的 泛函極值問題的 必要條件,此條件一般又稱之為 Euler-Largrange Eqution。此方程可謂泛函極值的房角石,亦為之後在最佳控制理論中的最大值原理扮演開路先鋒,是極為重要的角色。在介紹之前,我們先做一般性的用語與基本性質介紹。


======================
Definition: 泛函
令 $\Omega$ 為 賦範函數空間 (normed function space),若 對任意函數 $x(t) \in \Omega$ 都存在一個實數與之對應,則我們稱 $J$ 是定義在 $\Omega$ 上的 泛函 (functional),記作 $J(x(t))$
======================

Comment:
1. 簡而言之,泛函 一詞即表示為由 函數空間 映射到 實數軸 上的函數 $J: \Omega \to \mathbb{R}$ 。
2. 再以下的討論中,集合 $\Omega$ 又稱為 泛函 $J$ 的 容許集 (admissible set)


現取 $x_1, x \in \Omega$ 且 $\delta x := x_1 - x$ ,我們定義 關於 $\delta x$ 的 泛函增量 (increment) 如下
\[
\Delta J(\delta x)  := J(x_1) - J(x) =  J( x + \delta x) - J(x)
\]則由此 泛函增量,我們可以定義何謂泛函的變分。

======================
Definition: 泛函的變分
給定泛函 $J : \Omega \to \mathbb{R}$,若存在 一線性泛函 $L(x, \delta x)$ 使得泛函增量可被表為
\[
\Delta J(\delta x) = L(x, \delta x) + r(x, \delta x) \cdot | |\delta x||
\]其中 $r(x, \delta x)$ 為 其他高階剩餘項(remainder) 滿足 當 $| |\delta x|| \to 0 \Rightarrow r(x, \delta x) \to 0$,則我們稱上式中的 $L(x, \delta x)$ 為 $J(x)$ 的 變分 (variation),記作 $\delta J := L(x, \delta x)$
======================

Comment:
1. 上述定義中的 線性泛函項 $L$ 與 其他高階剩餘項 $r$,可視為透過 Taylor 級數展開而得。
2. 變分 (variation) 一詞在文獻中又稱 differential
3. 若泛函變分存在,則該 變分 為唯一,在此不證明,有興趣讀者可參閱 [1]。
4. 關於線性泛函及其相關定義請讀者可參閱 [變分法] 淺論 線性泛函 
5. 有些文獻定義的泛函是透過所謂 Gateaux differentials 與 Freshet differential,但為求論述簡潔,在此不多作介紹,有興趣的讀者可以參閱 [2]


======================
Theorem: 泛函極值與變分關係
給定泛函 $J : \Omega \to \mathbb{R}$,若其變分存在,則 其變分可表為參數 $\alpha$ 的方向導數,亦即 變分滿足下式
\[\delta J(x(t)) = {\left. {\frac{\partial }{{\partial \alpha }}J(x(t) + \alpha \delta x(t))} \right|_{\alpha  = 0}}\]======================

Proof: 給定泛函 $J : \Omega \to \mathbb{R}$ 且假設其變分存在,我們要證明
\[\delta J(x(t)) = {\left. {\frac{\partial }{{\partial \alpha }}J(x(t) + \alpha \delta x(t))} \right|_{\alpha  = 0}}
\]首先由 $\delta J$ 存在可知:存在一線性泛函 $L$ 始得 泛函增量 $\Delta J$滿足
\[\begin{align*}
  \Delta J &= J\left( {x + \alpha \delta x} \right) - J\left( x \right) \hfill \\
   &= L(x,\alpha \delta x) + r(x,\alpha \delta x) \cdot || \alpha \delta x || \hfill \\
\end{align*}
\]由於 $L$ 為線性泛函,故 $L(x,\alpha \delta x) = \alpha L(x,\delta x)$,現在觀察
\[\begin{align*}
  {\left. {\frac{\partial }{{\partial \alpha }}J(x(t) + \alpha \delta x(t))} \right|_{\alpha  = 0}} &= \mathop {\lim }\limits_{\alpha  \to 0} \frac{{J(x + \alpha \delta x) - J\left( x \right)}}{\alpha }\\
   &= \mathop {\lim }\limits_{\alpha  \to 0} \frac{{L(x,\alpha \delta x) + r(x,\alpha \delta x)||\alpha \delta x||}}{\alpha } \hfill \\
   &= \mathop {\lim }\limits_{\alpha  \to 0} \frac{{L(x,\alpha \delta x)}}{\alpha }  + \underbrace {\mathop {\lim }\limits_{\alpha  \to 0} \frac{{r(x,\alpha \delta x) ||\alpha \delta x||}}{\alpha }}_{ = 0}  \hfill \\
   &= \mathop {\lim }\limits_{\alpha  \to 0} \frac{{\alpha L(x,\delta x)}}{\alpha }  \hfill \\
   &= L(x,\delta x) = \delta J(x) \;\;\;\;\; \square
\end{align*}
\]


======================
Theorem:
令 $J$ 為泛函且其變分存在,若 $J(x)$ 在 $x_0 \in \Omega$ 有(局部)極值,則其在 $x_0$ 之變分
\[
\delta J(x_0) =0
\] ======================
Comment: 上述定理中的 $x_0$ 又稱為 泛函 $J$ 的臨界點(critical point) 或者稱 不動點 (stationary point)。

Proof: 由於變分存在,我們可將變分用 以單變數參數 $\alpha$ 的方向導數表示
\[{\left. {\delta J\left( x \right) = \frac{\partial }{{\partial \alpha }}J(x + \alpha \delta x)} \right|_{\alpha  = 0}}\]由於 $J(x)$ 在 $x_0 \in \Omega$ 有局部極值,故我們可知 $\alpha =0$ 為$J(x_0 + \alpha \delta x)$ 的局部極值 (以極小值為例,可知對任意 $\alpha \in \mathbb{R}$, $J(x_0) \leq J(x_0 + \alpha \delta x)$,且極小值發生在 $\alpha = 0$),故
\[{\left. {\delta J\left( {{x_0}} \right) = \frac{\partial }{{\partial \alpha }}J({x_0} + \alpha \delta x)} \right|_{\alpha  = 0}} = 0\;\;\;\; \square
\]


在討論一般設定之後,以下我們開始針對特殊形式的泛函來建構必要條件:考慮泛函
\[
J(x(t)) := \int_{t_0}^{t_1} F(t,x,\dot{x}) dt; \;\;\; x(t_0) :=x_0; \;\;\; x(t_1) \doteq x_1
\]且令其  admissible set 為
\[
\Omega := \{x(t) : x(t) \in C^2[t_0, t_1], \; x(t_0) = x_0, x(t_1) = x_1\}
\]且 $F(t, x, \dot{x})$ 為 $C^2$  (二階可導且連續),我們欲求上述泛函極值的必要條件,此結果極為鼎鼎大名的 Euler-Largrange 方程,但在我們證明主要定理之前,底下我們先給個前置定理,此定理又稱為變分基本定理。


======================
Lemma: 變分基本引理
設函數 $F(t)$ 在區間 $[t_0, t_1]$ 上連續,若對於任意滿足 $\eta(t_0) = \eta(t_1) =0$ 的充分光滑函數 $\eta(t)$ 我們都有
\[
\int_{t_0}^{t_1} F(t) \eta(t) dt =0
\]則 $F(t) = 0$ 對 $t \in [t_0,t_1]$
======================

Proof: 利用反證法,假設 存在 $\xi \in (t_0,t_1)$ 使得 $F(\xi) \neq 0$,欲證明矛盾。不失一般性情況下我們假設 $F(\xi) >0$ 則由於 $F$的連續性,可知必存在 以 $\xi$ 為中心的鄰域 $N_\xi :=(\xi_1,\xi_2) \subset (t_0, t_1)$ 使得 對任意 $t \in N_\xi$,我們有 $F(t) > 0$。現在我們構造 $\eta(t)$ 函數如下
\[\eta \left( t \right): = \left\{ \begin{gathered}
  0,\begin{array}{*{20}{c}}
  {}&{}&{}&{}
\end{array}t \in \left[ {{t_0},{\xi _1}} \right) \hfill \\
  {\left[ {\left( {t - {\xi _1}} \right)\left( {t - {\xi _2}} \right)} \right]^2},\begin{array}{*{20}{c}}
  {}&{}
\end{array}t \in \left[ {{\xi _1},{\xi _2}} \right] \hfill \\
  0,\begin{array}{*{20}{c}}
  {}&{}&{}&{}
\end{array}t \in \left( {{\xi _2},{t_1}} \right] \hfill \\
\end{gathered}  \right.\]且注意到上述 $\eta(t)$ 函數滿足 $\eta(t_0) = \eta(t_1) = 0$ 且為連續函數,然而若我們觀察
\[
\int_{t_0}^{t_1} F(t) \eta(t) dt = \int_{\xi_1}^{\xi_2} F(t) \eta(t) dt > 0
\]此結果與我們的假設矛盾。$\square$



======================
Theorem: 泛函極值的必要條件 Euler-Lagrange Equation
設函數 $F(t, x, \dot{x})$ 具有連續二階偏導數,且設泛函\[
J(x(t)) := \int_{t_0}^{t_1} F(t,x,\dot{x}) dt; \;\;\; x(t_0) :=x_0; \;\;\; x(t_1) \doteq x_1
\]在 $x(t) \in \Omega$ 達到極值,則 $x(t)$ 滿足下列方程
\[\frac{\partial }{{\partial x}}F\left( {t,x,\dot x} \right) - \frac{d}{{dt}}\left( {\frac{\partial }{{\partial \dot x}}F\left( {t,x,\dot x} \right)} \right) = 0\]
======================

Proof: 首先令 $\phi(t) := \delta x(t)$,則由於 $x(t_0)=x_0$與 $x(t_1) = x_1$ 可知,$\phi(t)$ 滿足 $\phi(t_0) = \phi(t_1)=0$,現在由泛函極值與變分的關係可知下式必定成立:
\[\delta J\left( {x\left( t \right)} \right) = \left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right)} \right|_{\alpha = 0} = 0 \;\;\;(\star)
\]現在觀察
\[
J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right) = \int_{{t_0}}^{{t_1}} F (t,x + \alpha \phi ,\dot x + \alpha \dot \phi )dt
\]故我們可先行計算
\[{\left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right)} \right|_{\alpha  = 0}} = {\left. {\frac{\partial }{{\partial \alpha }}\int_{{t_0}}^{{t_1}} F (t,x + \alpha \phi ,\dot x + \alpha \dot \phi )dt} \right|_{\alpha  = 0}}
\]由 Libneiz Rule 可得
\[\begin{align*}
  {\left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right)} \right|_{\alpha  = 0}} &= {\left. {\frac{\partial }{{\partial \alpha }}\int_{{t_0}}^{{t_1}} F (t,x + \alpha \phi ,\dot x + \alpha \dot \phi )dt} \right|_{\alpha  = 0}} \hfill \\
   &= {\left. {\int_{{t_0}}^{{t_1}} {\frac{\partial }{{\partial \alpha }}F} (t,x + \alpha \phi ,\dot x + \alpha \dot \phi )dt} \right|_{\alpha  = 0}} \hfill \\
   &=  {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}}\phi  + \frac{{\partial F}}{{\partial \dot x}}\dot \phi } \right]} dt} \right|_{\alpha  = 0}}\;\;\;\; (*)
\end{align*}
\]注意到上述積分第二項可透過 integration by part 求得
\[\int_{{t_0}}^{{t_1}} {\frac{{\partial F}}{{\partial \dot x}}\dot \phi dt}  = \left. {\frac{{\partial F}}{{\partial \dot x}}\phi } \right|_{{t_0}}^{{t_1}} - \int_{{t_0}}^{{t_1}} {\phi \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} dt\]由於 $\phi(t_0) = \phi(t_1) = 0$,故我們得
\[\begin{gathered}
  \int_{{t_0}}^{{t_1}} {\frac{{\partial F}}{{\partial \dot x}}\dot \phi dt}  = \underbrace {\left. {\frac{{\partial F}}{{\partial \dot x}}\phi } \right|_{{t_0}}^{{t_1}}}_{ = 0} - \int_{{t_0}}^{{t_1}} {\phi \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} dt \hfill \\
   \Rightarrow \int_{{t_0}}^{{t_1}} {\frac{{\partial F}}{{\partial \dot x}}\dot \phi dt}  =  - \int_{{t_0}}^{{t_1}} {\phi \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} dt \hfill \\
\end{gathered}
\]現在將其帶回 $(*)$ 我們得到
\[\begin{align*}
  {\left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right)} \right|_{\alpha  = 0}}
   &= {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}}\phi  - \phi \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} \right]} dt} \right|_{\alpha  = 0}} \hfill \\
   &= {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}} - \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} \right]} \phi dt} \right|_{\alpha  = 0}} \hfill \\
\end{align*}
\]由於 $(\star)$ 可知,
\[\begin{align*}
  {\left. {\frac{\partial }{{\partial \alpha }}J\left( {x\left( t \right) + \alpha \phi \left( t \right)} \right)} \right|_{\alpha  = 0}}
&= {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}}\phi  + \frac{{\partial F}}{{\partial \dot x}}\dot \phi } \right]} dt} \right|_{\alpha  = 0}} \hfill \\
   &= {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}}\phi  - \phi \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} \right]} dt} \right|_{\alpha  = 0}} \hfill \\
   &= {\left. {\int_{{t_0}}^{{t_1}} {\left[ {\frac{{\partial F}}{{\partial x}} - \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} \right]} \phi dt} \right|_{\alpha  = 0}} = 0 \hfill \\
\end{align*}
\]由於 ${\frac{{\partial F}}{{\partial x}} - \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}}$ 在區間 $[t_0,t_1]$ 連續,且 $\phi$ 滿足 $\phi(t_0) = \phi(t_1) =0$ 且 $\phi \in C^2$,利用前述引理可知在 $[t_0,t_1]$ 上,
\[{\frac{{\partial F}}{{\partial x}} - \frac{d}{{dt}}\frac{{\partial F}}{{\partial \dot x}}} = 0\;\;\;\; \square\]


[1] I. M. Gelfand and S. V. Fomin, Calculus of Variations, 2000
[2] David G. Luenberger, Optimization By Vector Space Methods, 1997

8/07/2016

[凸分析] 擬凸函數 取積分後不保證其 擬凸性

回憶在 凸分析 中,兩凸函數 $f_1, f_2$ 之合仍為 convex,且此特性可進一步推廣至有限函數和,無窮組函數和,甚至積分都對,此篇文章中,我們將針對 擬凸函數(quasiconvex function) 來檢驗上述性質。令 $X$ 為隨機變數,現令 函數 $f(X,K)$ 為 quasiconvex in $K$ almost surely,則我們想問對其取積分之後是否仍為 quasiconvex in $K$?,亦即 $E[ f(X, K) ]$ 是否仍為 quasiconvex in $K$?

再構造反例之前,我們先給出 quasiconvex 函數的定義:

=================
Definition: 我們稱 $f: dom(f) \subset \mathbb{R}^n \to \mathbb{R}$ 為 擬凸函數 (quasiconvex function) 若下列條件成立:
對任意 $ \alpha \in \mathbb{R}$,集合
\[
S_{\alpha} := \{x \in dom(f) : f(x) \leq \alpha \}
\] 為 convex 集。
=================


Comments:
1. Quasiconvex 在有些文獻中又稱為 unimodal。
2. 所謂的擬凸性質 (Quasiconvexity) 可視為是 凸性 (Convexity) 的推廣,關於 quasiconvex 函數更詳細的介紹,建議讀者參考 [1],在此我們不做贅述。


現在我們可以著手回答一開始本篇文章所關心的問題:若 $f(X,K)$ 為 quasiconvex in $K$,是否取期望值 (積分)之後 $E[f(X,K)]$ 亦為 quasiconvex in $K$? 此答案是否定的,以下我們構造反例:

Counter Example: 令 $K \in [0,1]$ 且 $X$ 為隨機變數滿足 $X = 0 $ with probability $1/2$ 且 $X=1$ with probability $1/2$,取 $$
f(X,K) := (1 - X) K  - X K^2
$$ 則可知此函數 $f$ 為 quasiconvex in $K$ almost surely (WHY?),在此我們繪製所有可能的 $X$ 及其對應的函數圖形如下


可看出給定 $\alpha \in \mathbb{R}$,不論在 $X=0$ 或者 $X=1$ 均可得知對應的集合 $S_\alpha$ 為 convex,故可推知 $f(X,K)$ 為 quasiconvex with probability one。

然後,現在我們檢驗其期望值
\[\begin{align*}
  E[f(X,K)] = \frac{{ - {K^2}}}{2} + \frac{K}{2}
\end{align*} \]不再是 quasiconvex。讀者可自行繪製上述函數對應的集合 $S_\alpha$ 即可立刻發現不為 convex; 舉例而言,取 $\alpha := 0.05$,且繪製 $E[f(X,K)]$ 如下圖


可發現 $S_{\alpha=0.05} =\{K \in [0,1]: E[f(X,K)] \leq 0.05 \}$ 的集合大約可表為
 $$
\{K: K \in [0,0.15] \bigcup [0.85,1]\}
$$故可立刻判斷 $S_{\alpha = 0.05}$ 不是 convex 集,由此可知 $E[f(X,K)]$ 非 quasiconvex 。


[1] S. P. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...