顯示具有 Convex Functions 標籤的文章。 顯示所有文章
顯示具有 Convex Functions 標籤的文章。 顯示所有文章

12/19/2017

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

8/12/2017

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

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

=====================
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$

8/11/2017

[凸分析] 一階可導凸函數利用單點近似必定低估


Theorem: 
令 $f \in C^1$ 且 $f$ 為 convex on convex set $\Omega \subset \mathbb{R}^n$ 若且唯若 對任意 $x,y \in \Omega$ 而言,
\[
f(y) \geq f(x) + \nabla f(x) \cdot (y-x)
\]其中 $\nabla f(x) \cdot (y-x) := \nabla f(x)^T (y-x)$

給出證明之前我們先給一些直觀上的看法:

Comments:
1. 上述定理算是相當直覺,簡而言之就是說 affine (in $y$) function:
$ f(x) + \nabla f(x) (y-x)$ 可以做為 凸函數 $f$ 在 $x$ 點附近的 1 階 Taylor 近似,如下圖所示:



2. 注意到上述定理闡述的不等式對於所有 $x,y \in \Omega$ 都成立,也就是說透過 對$x$ 一階 Taylor 近似必定低估,一般 $f(x) + \nabla f(x) (y-x)$ 又稱作 global underestimaotr  of $f$。
3. 上述結果指出利用局部資訊 (一階導數) 可以得到 全域資訊 (global understametor )。
4. 若 $\nabla f(x) = 0$ 則對任意 $y \in \Omega$,我們有
\[
f(y) \geq f(x)
\]亦即 $x$ 為 全域及小點 (global minimizer) of $f$


以下我們給出證明

Proof: 先證明 $(\Rightarrow)$
令 $f \in C^1$ 且 $f$ 為 convex on convex set $\Omega \subset \mathbb{R}^n$,給定任意 $x,y \in \Omega$ ,我們要證
\[
f(y) \geq f(x) + \nabla f(x) (y-x)
\]
由於  $f$ 為 convex,令 $\alpha \in (0,1)$ 且定義
$$
z(\alpha) := \alpha x + (1-\alpha) y
$$則 $z(\alpha) \in \Omega$ 且由 $f$的凸性,我們有
\begin{align*}
  f\left( {z(\alpha )} \right) &= f\left( {\alpha x + \left( {1 - \alpha } \right)y} \right) \hfill \\
   &\leqslant \alpha f\left( x \right) + \left( {1 - \alpha } \right)f\left( y \right) \hfill \\
\end{align*} 由於 $\alpha \neq 0$ 我們可整理上式得到
\[\frac{{f\left( {\alpha x + \left( {1 - \alpha } \right)y} \right) - f\left( y \right)}}{\alpha } \leqslant f\left( x \right) - f\left( y \right)\]或者
\[\frac{{f\left( {y - \alpha \left( {y - x} \right)} \right) - f\left( y \right)}}{\alpha } \leqslant f\left( x \right) - f\left( y \right)\]取 $\alpha \to 0$,由於 $f\in C^1$ 我們不難看出上述不等式左方 為沿著 $y-x$ 的方向導數,故我們有
\[
\nabla f(y) \cdot (y-x) \leq f(x) -f(y)
\]或者
\[
f(x) \geq f(y) + \nabla f(y) \cdot (y-x)
\]上述結果對 任意 $x,y \in \Omega$ 成立,故我們將 $x,y$ 角色對換即得到定理要求的陳述。

接著我們證明$(\Leftarrow)$:
假設  對任意 $x,y \in \Omega$ 而言,
\[
f(y) \geq f(x) + \nabla f(x) (y-x) \;\;\;\;\; (**)
\]我們要證明 $f$ 為 convex。故令 $x_1, x_2 \in \Omega$ 與 $\alpha \in [0,1]$ ,並且我們額外定義
\[
\bar{x} := \alpha x_1 + (1- \alpha) x_2
'\]
則由假設可知 $x_1, x_2, \bar{x}$ 必定滿足 $(**)$,我們可寫下
\[\begin{gathered}
  f({x_1}) \geqslant f(\bar x) + \nabla f(\bar x)({x_1} - \bar x) \hfill \\
  f({x_2}) \geqslant f(\bar x) + \nabla f(\bar x)({x_2} - \bar x) \hfill \\
\end{gathered} \]現在對上述 第一條不等式 兩邊同乘上 $\alpha$ ,對 第二條不等式 兩邊乘上 $1- \alpha$ ,亦即
\begin{align*}
 & \alpha f({x_1}) \geqslant \alpha f(\bar x) + \alpha \nabla f(\bar x)({x_1} - \bar x) \hfill \\
  &\left( {1 - \alpha } \right)f({x_2}) \geqslant \left( {1 - \alpha } \right)f(\bar x) + \left( {1 - \alpha } \right)\nabla f(\bar x)({x_2} - \bar x) \hfill \\
\end{align*}
現在觀察
\begin{align*}
  \alpha f({x_1}) + \left( {1 - \alpha } \right)f({x_2}) &\geqslant \alpha f(\bar x) + \alpha \nabla f(\bar x)({x_1} - \bar x) \hfill \\
   & \hspace{10mm}+ \left( {1 - \alpha } \right)f(\bar x) + \left( {1 - \alpha } \right)\nabla f(\bar x)({x_2} - \bar x)
\end{align*}
將上式稍微做一下整理可得
\begin{align*}
  &\alpha f({x_1}) + \left( {1 - \alpha } \right)f({x_2}) \geqslant f(\bar x) + \nabla f(\bar x)\left( {\alpha ({x_1} - \bar x) + \left( {1 - \alpha } \right)({x_2} - \bar x)} \right) \hfill \\
   &\Rightarrow \alpha f({x_1}) + \left( {1 - \alpha } \right)f({x_2}) \geqslant f(\bar x) + \nabla f(\bar x)\underbrace {\left( {\alpha {x_1} + \left( {1 - \alpha } \right){x_2} - \bar x} \right)}_{ = 0} \hfill \\
   &\Rightarrow \alpha f({x_1}) + \left( {1 - \alpha } \right)f({x_2}) \geqslant f(\bar x) \hfill \\
\end{align*} 上述不等式表明 $f$ 為凸函數。$\square$


Comments:
1. 若 $f$ 為 $C^1$ strict convex 函數 on $\Omega$,則對任意 $x,y \in \Omega$ 而言,
\[
f(y) >f(x) + \nabla f(x) (y-x)
\]
2. 若 $f$ 為 concave 則利用 $-f$ 為 convex 特性可知 對於 concave 函數而言,定理的不等式變成: 對任意 $x,y \in \Omega$ 而言,
\[
f(y) \leq f(x) + \nabla f(x) (y-x)
\]

[Call for Papers] IEEE TCST Special Issue: Advanced Control Technologies for Financial Systems

Submission deadline: February 1, 2027 https://ieeecss.org/publication/transactions-control-systems-technology/special-issues