2017年12月19日 星期二

[凸分析] 凸性 與 齊次性 的關聯 (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$