這次要介紹凸分析 或者 凸優化 中可以說是最重要的結果: ===================== 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
If you can’t solve a problem, then there is an easier problem you can solve: find it. -George Polya