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

在凸優化問題中，僅管凸性保證了任意局部最優解 (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$ 仍落在 $S_{\leq \alpha}$ 之中，亦即我們要證明 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$。為此，我們利用 $f$ 的凸性，對任意 $\lambda \in (0,1)$，
\[
f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) \leq \alpha
\]故 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$，至此得證。$\square$


Remark:
對於 concave 函數我們仍有類似的結果記錄如下：

令 $S \subseteq \mathbb{R}^n$ 為凸集，且 $f: S \to \mathbb{R}$ 為 concave 函數，則所有極大點所成的集合 $S^*$ 為 convex set。

[凸分析] 凸性 與 齊次性 的關聯 (2)：一些常見的結果

此文接續前篇對於凸函數 與 齊次函數的討論，主要是給出一些常見的結果。閱讀此文之前，建議讀者先回憶 凸性 與 齊次函數的定義，關於齊次函數以及一些相關例子，讀者可參閱 [凸分析] 凸性 與 齊次性 的關聯 (1)：一些常見例子。

以下我們首先給出 一組齊次函數的 連乘  或 連加 仍保持為 齊次函數 的條件：

================================
Theorem: Homogeneous Functions Algebra
1. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions，且對於 $i=1,...,m$ 而言， $f_i$ 具有 homogeneous of degree $\alpha_i$。則
\[
z(x) :=  \prod_{i=1}^m f_i(x) = f_1(x) \cdot f_2(x) \cdots f_m(x)
\]為 homogenous of degree $(\alpha_1 + ... +\alpha_m)$

2. 令 $f_1,...,f_m$ 為一組 定義在 convex cone $C \subset \mathbb{R}^n$ 上的 homogeneous functions，且對於 $i=1,...,m$ 而言， $f_i$ 具有相同 homogeneous of degree $\alpha$。則
\[z(x): = {\left( {\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta }\]為 homogenous of degree $(\alpha \beta)$
================================

Proof 1: 令 $x \in C$ 觀察
\[
z(tx) = \prod_{i=1}^m f_i(tx)
\]由於 $f_i$ 為 homogeneous of degree $\alpha_i$，我們有 $$f_i(tx) = t^{\alpha_i} f(x)$$ 且 $\forall t>0, i=1,2,...,m$，因此

\begin{align*}
  z(tx) &= \prod\limits_{i = 1}^m {{f_i}} (tx) \hfill \\
   &= \prod\limits_{i = 1}^m {{t^{{\alpha _i}}}{f_i}(x)}  \hfill \\
   &= {t^{{\alpha _1}}}{f_1}(x){t^{{\alpha _2}}}{f_2}(x)...{t^{{\alpha _m}}}{f_m}(x) \hfill \\
   &= {t^{\sum\limits_{i = 1}^m {{\alpha _i}} }}\left( {{f_1}(x){f_2}(x)...{f_m}(x)} \right) \hfill \\
   &= {t^{\sum\limits_{i = 1}^m {{\alpha _i}} }}z\left( x \right)
\end{align*}
上式對任意 $t>0$ 成立，此表明 $z(x)$ 為 homogeneous of degree $(\alpha_1 + ... +\alpha_m)$，至此證畢。$\square$


Proof 2: 令 $x \in C$ 觀察
\[z(tx): = {\left( {\sum\limits_{i = 1}^m {{f_i}(tx)} } \right)^\beta }\]由於 $f_i$ 為 homogeneous of degree $\alpha$，我們有 $$f_i(tx) = t^{\alpha} f(x)$$ 且 $\forall t>0, i=1,2,...,m$，因此

\begin{align*}
  z(tx)&: = {\left( {\sum\limits_{i = 1}^m {{f_i}(tx)} } \right)^\beta } \hfill \\
   &= {\left( {\sum\limits_{i = 1}^m {{t^\alpha }{f_i}(x)} } \right)^\beta } \hfill \\
   &= {\left( {{t^\alpha }\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta } \hfill \\
   &= \left( {{t^{\alpha \beta }}} \right){\left( {\sum\limits_{i = 1}^m {{f_i}(x)} } \right)^\beta } \hfill \\
  & = \left( {{t^{\alpha \beta }}} \right)z\left( x \right) \hfill \\
\end{align*}
上式對任意 $t>0$ 成立，此表明 $z(x)$ 為 homogeneous of degree $(\alpha \beta)$，至此證畢。$\square$



下面這個結果表明 一次齊次函數 如果具有 次可加性(subadditivity) 則 此函數必定為 convex。

================================
Theorem: Linear Homogeneity With Subadditivity Produces Convexity
令 $f: C \subset \mathbb{R}^n \to \mathbb{R}$ 為 linearly homogeneous function; i.e., $(f(tx) = t f(x), \; \forall t>0)$ 則 $f$ 為 convex 若且唯若 $f$ 滿足 subadditivity，亦即，對任意 $x,y \in C$，$$
f(x+y) \leq f(x) + f(y)
$$================================

Proof: $(\Rightarrow)$ 給定 $f$ 為 convex 且 linearly homogeneous 要證明對任意 $x,y \in C$，$$
f(x+y) \leq f(x) + f(y)
$$故給定 $x,y \in C$ 並且觀察
\begin{align*}
  f\left( {x + y} \right) &= f\left( {2\left( {\frac{{x + y}}{2}} \right)} \right) \hfill \\
   &= 2f\left( {\frac{{x + y}}{2}} \right)\;\;\;\; (*) \hfill \\
\end{align*} 上述最後一條等式成立因為我們使用了 $f$ 為 linearly homogeneous。接著由於 $f$ 為 convex 且 $1/2 \in (0,1)$ 故我們有
\[f\left( {\frac{{x + y}}{2}} \right) \leqslant \frac{1}{2}f\left( x \right) + \frac{1}{2}f\left( y \right)\]故
\[2f\left( {\frac{{x + y}}{2}} \right) \leqslant 2\left( {\frac{1}{2}f\left( x \right) + \frac{1}{2}f\left( y \right)} \right) = f\left( x \right) + f\left( y \right) \;\;\; (**)\]由 $(*)$ 與 $(**)$ 我們有
\[f\left( {x + y} \right) \leqslant f\left( x \right) + f\left( y \right)\]

$(\Leftarrow)$ 接著我們令 $x,y \in C$ 滿足 subadditivity: $f(x+y) \leq f(x) + f(y)$，我們要證明 $f$ 是 convex。現在給定 $\lambda \in (0,1)$ ，注意到由於 $x,y \in C$ 且 $C$ 為 convex cone，故對任意 $\lambda \in (0,1)$，我們有 $\lambda x \in C$ 與 $(1-\lambda y) \in C$。現在利用 已知的 subadditivity，我們 觀察
\[
f(\lambda x + (1- \lambda) y)  \leq f(\lambda x) + f( (1-\lambda)y) \;\;\; (\star)
\]利用 $f$ 為 linearly homogeneous，$f(\lambda x)=\lambda f( x)$ 且 $f( (1-\lambda)y) = (1-\lambda)f( y)$亦即，
\[f(\lambda x) + f((1 - \lambda )y) = \lambda f\left( x \right) + \left( {1 - \lambda } \right)f\left( y \right) \;\;\;\; (\star \star)\]由 $(\star)$ 與 $(\star \star)$ 式，我們可得
\[f(\lambda x + (1 - \lambda )y) \leqslant \lambda f\left( x \right) + \left( {1 - \lambda } \right)f\left( y \right)\]此表明 $f$ 為 convex in $C$。$\square$

[凸分析] 凸性 與 齊次性 的關聯 (1)：定義 與 一些常見例子

Definition:  Homogenous Function of Degree Alpha
令 $C \subset \mathbb{R}^n$ 為 convex cone。我們說函數 $f: C \to \mathbb{R}$ 為  $\alpha$ 次齊次函數 (homogeneous of degree $\alpha \in \mathbb{R}$) 若下列條件成立：
對任意 $x \in C$，
\[
f(t x) = t^\alpha f(x),\;\;\; \forall t >0
\]

Comments:
1.上述 齊次函數 定義可以推廣到不是在 convex cone上而是任意向量空間，但一般做 convex cone的假設是為了 其他在凸分析上的 用途。在比較深入的凸分析教材中，可能會探討所謂 廣義凸性(generalized convexity)比如 quasi-convexity, quasi-concavity, semi-strictly quasi-convexity 等等，則此時函數定義域 需要是凸集。

2. 注意到 degree of homogeneity $\alpha \in \mathbb{R}$，意指 此 $\alpha$ 為任意實數，正數，負數，零 或者其他都可以。

3. 我們說 $f$ 為 homogenous of degree $0$ 若對任意 $x \in C$,
\[
f(tx) = f(x), \forall t>0
\]若 $f$ 為 homogenous of degree $1$ 一般稱之為 linearly homogeneous ，亦即 對任意 $x \in C$
\[
f(tx) = t f(x), \forall t>0
\] 以下我們看幾個例子：

Example 1
考慮 需求函數 (Demand Function)
\[
D(p,R) := \frac{R}{p}
\]其中 $p > 0$ 為 price of a good 且 $R>0$ 為 income，試證此函數為 homogeneous of degree 0

Proof: 令 $C :=\{(p,r): p>0, R>0\}$，則此集合為一個 convex cone，現在觀察對任意 $(p,r) \in C$，
\[
D(tp, tR) = \frac{tR}{tp} = \frac{R}{p} = t^0 D(p,r)
\]上式對任意 $t>0$ 成立，故由定義可知 $D(p,r)$ 為 homogenous of degree zero，至此證畢。$\square$


Example 2:
考慮 生產函數 (Production Function)
\[
f(L,K) := L^{1/3} K^{2/3}
\]其中 $L>0$ 為投入的勞力 (labour) 且 $K>0$ 為 投入資本 capital，試證生產函數 $f$ 為 homogenous of degree $1$

Proof: 令 $C:= \{(L,K): L>0, K>0\}$ ，則可知 $C$ 為一個 convex cone。現在取任意 $(L,K) \in C$，我們有
\[f(tL,tK): = {\left( {tL} \right)^{1/3}}{\left( {tK} \right)^{2/3}} = t{\left( L \right)^{1/3}}{\left( K \right)^{2/3}} = t f(L,K)
\]上式對任意 $t>0$ 成立，故由定義可知 $D(p,r)$ 為 homogenous of degree zero，至此證畢。$\square$

Comments:
上述的生產函數 在經濟學中被稱為 Cobb-Douglas Function，在一般 計量經濟 中通常記作
\[
f(K,L) := A K^\alpha L^{1- \alpha}
\]此式子命名來自 兩位美國學者 C. W. Cobb 與 P. H. Douglas 於 1927 提出，此函數用以估計生產量，但事實上此式早在 1900之前就由 瑞士經濟學家 Knut Wicksell 已率先提出。此為軼事與本文無關只是單純提及。


接著我們看個上述生產函數的推廣，在(個體)經濟學中常見的 Cobb-Douglas Function：

===============
Theorem: Generalized Cobb-Douglas Function is Homogenous of Degree Alpha
令 $A>0, x_i>0, \alpha_i>0, i =1,2,...,n$，定義 Cobb-Douglas 函數
\[
f(x): = Ax_1^{{\alpha _1}}x_2^{{\alpha _2}} \cdots x_n^{{\alpha _n}}
\]則 $f$ 為 Homogeneous of degree $\alpha := \sum_{i=1}^n \alpha_i$
===============

Proof: 令 $C:=\{x=(x_1,x_2,...,x_n): x_i >0\}$ ，則不難發現 $C$ 為  convex cone，現在取任意 $x = (x_1,...,x_n) \in C$，我們觀察
\begin{align*}
  f(tx) &: = A\left( {t{x_1}} \right)_{}^{{\alpha _1}}\left( {t{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {t{x_n}} \right)_{}^{{\alpha _n}} \hfill \\
   &= A{t^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\left( {{x_1}} \right)_{}^{{\alpha _1}}\left( {{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {{x_n}} \right)_{}^{{\alpha _n}} \hfill \\
   &= {t^{\sum\limits_{i = 1}^n {{\alpha _i}} }}\underbrace {A\left( {{x_1}} \right)_{}^{{\alpha _1}}\left( {{x_2}} \right)_{}^{{\alpha _2}} \cdots \left( {{x_n}} \right)_{}^{{\alpha _n}}}_{ = f\left( x \right)} \\
&= {t^\alpha }f\left( x \right)
\end{align*} 其中 $\alpha:= \sum_{i=1}^n \alpha_i$，上述等式對任意 $t>0$ 成立，故 $f$ 為 Homogeneous of degree $\alpha := \sum_{i=1}^n \alpha_i$，至此證畢。$\square$


Comments:
上述 Cobb-Douglas function $f$ 亦俱備 log-linear 性質，亦即對 $f$ 取 $\log (.)$ 之後為線性函數：觀察
\begin{align*}
 \log \left( {f\left( x \right)} \right) &= \log \left( {Ax_1^{{\alpha _1}}x_2^{{\alpha _2}} \cdots x_n^{{\alpha _n}}} \right) \hfill \\
   &= \log \left( A \right) + {\alpha _1}\log \left( {x_1^{}} \right) + {\alpha _2}\log \left( {x_2^{}} \right) + ... + {\alpha _n}\log \left( {x_n^{}} \right) \hfill \\
\end{align*} 由上述結果不難看出 $\log(f)$ 為 linear functions of $\log(x_1), \log(x_2),...,\log(x_n)$

[凸分析] 定義在凸集上的凸函數其相對極小即為全域極小

這次要介紹凸分析 或者 凸優化 中可以說是最重要的結果：

=====================
Theorem:
令 $f$ 為 convex on convex set $\Omega$。則
1. $f$ 的任意 相對極小點 $x^*$ (local minimum of $f$ on $\Omega$) 必為 全域極小點 (global minimum of $f$ on $\Omega$)
2. 上述 凸函數的極小點所成之集合為凸集，亦即
\[
S:= \{x \in \Omega: f(x) = f(x^*)\}
\]為凸集。
=====================

Proof (1):
利用反證法：令  $y \in  \Omega$ 為 $f$在 $\Omega$ 上的相對極小點，亦即存在 $\delta>0$ 使得鄰域 $$N_\delta(y):=\{z: ||z-y|| < \delta\} \subset \Omega$$ 且
\[
f(y) \leq f(x), \;\;\; \forall x \in N_\delta(y)
\] 但 $y$ 不為 global minimum ：亦即 存在 $x^* \in \Omega$ 使得 \[
f(x^*) < f(y)
\]我們要證明此假設矛盾。

首先注意到 $x^* \notin N_\delta(y)$ 因為若不然，則 $f(y) \leq f(x^*)$ 此與假設不符。

現在，我們利用 $x^*$ 與 $y$ 來定義一個 新的點
\[
z(\alpha):= (1-\alpha)y +   \alpha x^*, \;\;\; \alpha := \frac{\delta}{2||y-x^*||} \in (0,1)
\]注意到 $z(\alpha) \in \Omega$ (因為 $\Omega$ 為凸集) 且我們觀察
\begin{align*}
  |z\left( \alpha  \right) - y|| &= \left\| {  (1 - \alpha ) y + \alpha x^* - y} \right\| \hfill \\
   &= \left\| {\alpha \left( {y - {x^*}} \right)} \right\| \hfill \\
   &\leqslant \frac{\delta }{{2\left\| {y - {x^*}} \right\|}}\left\| {y - {x^*}} \right\| < \delta  \hfill \\
\end{align*} 此結果表明
\[
z(\alpha) \in N_\delta(y)
\]
現在利用 $f$ 為凸函數性質，我們可知
\begin{align*}
  f(z(\alpha )) &= f\left( {\left( {1 - \alpha } \right) y + \alpha  x^*} \right) \hfill \\
   &\leqslant \alpha f\left( y \right) + \left( {1 - \alpha } \right)\underbrace {f\left( {{x^*}} \right)}_{f\left( y \right)} < f\left( y \right) \hfill \\
\end{align*} 上述不等式表明我們找到一個新的點 $z(\alpha) \neq y$  且 $z(\alpha) \in N_\delta(y)$ 使得
\[
f(z(\alpha)) < f(y)
\]此違反了 $y$ 在 $\Omega$ 上為相對極小的假設，得到矛盾。 故 $y$ 必為 global minimum。

Proof:(2)
接著我們證明上述 全域極小點 所成的集合為凸集，亦即
\[
S:= \{x \in \Omega: f(x) = f(x^*)\}
\]
首先觀察凸函數 $f$ 的 $c$-level set
\[
S_c:= \{x \in \Omega: f(x) \leq c\}
\]由下方的 FACT 可知 凸函數的 level set 為凸集。但因為 $x^*$ 為全域極小，故若取 $c:=f(x^*)$ 則
\[
S_c|_{c=f(x^*)}  =  \{x \in \Omega: f(x) \leq f(x^*)\} = \{x \in \Omega: f(x) = f(x^*)\} =S
\]由於為等式左方 $S_c$ 為凸集，故 $S$ 亦為凸集。 $\square$


=====================
FACT: 凸函數的 Sublevel Set 為凸集
令 $f: \Omega \subset \mathbb{R}^n \to \mathbb{R}$ 為凸函數，則對任意 $c \in \mathbb{R}$ ，其 $c$-level set
\[
S_c:=\{x: f(x) \leq c\}
\]為凸集
=====================

Proof: 利用凸函數定義，取 $x,y \in S_c$ 且 $\alpha \in [0,1]$ ，觀察
\[
f(\alpha x + (1-\alpha) y) \leq \alpha f(x) + (1-\alpha) f(y) \leq c 
\]故 $\alpha x + (1-\alpha) y\in S_c$，此表明 $S_c$ 為凸集。$\square$