2016年8月7日 星期日

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

回憶在 凸分析 中,兩凸函數 $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.