跳到主要內容

發表文章

目前顯示的是 8月, 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

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

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$的凸性,我們

[最佳化理論] 有限維空間 無拘束最佳化問題 的二階充分必要條件

回顧先前我們討論過的一階必要條件,以下我們介紹有限維空間 無拘束最佳化問題的 二階必要與充分條件,首先是二階必要條件: ==================== Theorem: Second-Order Necessary Condition, SONC: 令 $S \subset \mathbb{R}^n$ 且令 $f \in C^2(S)$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 則 對 在點 ${\bf x}^*$的任意可行方向 ${\bf d} \in \mathbb{R}^n$,我們有 1. $\nabla f({\bf x}^*) \cdot {\bf d} \geq 0$ 2. 若 $\nabla f({\bf x}^*) \cdot {\bf d} =0$ 則 ${\bf d}^T \nabla^2 f({\bf x}^*) {\bf d} \geq 0$ ==================== Proof: 由於 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 對條件 1 自動成立。我們僅需證明條件2。令  ${\bf d} \in \mathbb{R}^n$ 為 在點 ${\bf x}^*$的任意可行方向,故存在 $\bar \alpha >0$ 使得 \[ {\bf x}(\alpha) := {\bf x}^* + \alpha {\bf d} \in S, \;\;\; \alpha \in [0, \bar \alpha] \] 利用 Taylor Theorem 對 ${\bf x}^*$ 展開到二階項,我們可得 \begin{align*}   f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) &= f\left( {{{\mathbf{x}}^*}} \right) + \nabla f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) \\ & \h

[最佳化理論] 有限維空間 無拘束最佳化問題 的一階必要條件

令 $f: \mathbb{R}^n \to \mathbb{R}$ 且 $S \subset \mathbb{R}^n$ 為 feasible set,現在我們考慮以下的 有限維度 (無拘束)最佳化問題 \[\begin{gathered}   \min f\left( {\mathbf{x}} \right) \hfill \\   s.t.{\mathbf{x}} \in S \subseteq {R^n} \hfill \\ \end{gathered} \] 我們想知道上述最佳化問題是否有解? 若有解則是哪一種解 e.g., 局部最佳解(local optimum)或者 全域最佳解(global optimum)?),以及上述的解是否能夠透過某種方法來將其描述。 對於上述有限維度最佳解的存在性問題一般可由 Weierstrass Extremum Theorem處理,在此不做贅述。以下我們討論 最佳解 存在的必要條件:更近一步地說是 最佳化理論中的求取 "局部最佳解" 的一階必要條件,在給出結果之前我們首先定義 可行方向 (Feasible Direction)如下: ====================== Definition: Feasible Direction 給定 ${\bf x} \in S \subset \mathbb{R}^n$,我們說向量 ${\bf d} \in \mathbb{R}^n$ 為 在 ${\bf x}$ 處的可行方向 (feasible direction) 若下列條件成立:存在常數 $ \bar \theta >0$ 使得對任意 $\theta \in [0, \bar\theta]$而言, \[ {\bf x} + \theta {\bf d} \in S \]====================== 有了以上的可行方向的想法,其局部最佳解的一階必要條件有如下陳述: ====================== Theorem: (First Order Necessary Condition, FONC):  令 $S \subset \mathbb{R}^n$ 且 $f \in C^1$ on $S$ ( $f$為一階可導且導數連續)