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)
\]

8/03/2017

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

回顧先前我們討論過的一階必要條件,以下我們介紹有限維空間 無拘束最佳化問題的 二階必要與充分條件,首先是二階必要條件:

====================
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) \\
& \hspace{10mm}+ \frac{1}{2}{\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right)^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
 &  = f\left( {{{\mathbf{x}}^*}} \right) + \alpha \nabla f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
\end{align*} 若 $\nabla f({\bf x}^*) \cdot {\bf d} =0$,則上式變成
\[\begin{gathered}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) = f\left( {{{\mathbf{x}}^*}} \right) + \alpha \underbrace {\nabla f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ = 0} + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
   = f\left( {{{\mathbf{x}}^*}} \right) + \frac{1}{2}{\alpha ^2}{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}} + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
\end{gathered} \]注意到若 ${{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}<0$ 對在 ${\bf x}^*$任意足夠小的鄰域成立,則我們得到
\[f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) \leqslant f\left( {{{\mathbf{x}}^*}} \right) \]此與 ${\bf x}^*$是 local minimum 矛盾,故
\[{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}\geq 0\;\;\;\;\; \square\]

Comments:
讀者大概不難發現不論是一階 或者 二階 條件都是依賴 Taylor 定理展開式,依此來進行估計。


====================
Theorem: Second-Order Sufficient Condition, SOSC: 
令 $S \subset \mathbb{R}^n$ 且令 $f \in C^2(S)$。若 ${\bf x}^* \in S$ 為interior point 且$f$ 在該點有定義。若
1. $\nabla f({\bf x}^*) = {\bf 0}$
2. 對任意 ${\bf d} \in \mathbb{R}^n$,${\bf d}^T \nabla^2 f({\bf x}^*) {\bf d} >0$ (亦即 $\nabla^2 f({\bf x}^*)$ 為 positive definite),則 ${\bf x}^*$ 為 strict local minimum of $f$。
====================

Proof: 要證明 ${\bf x}^*$ 為 strict local minimum of $f$,我們僅需證明
\[
f({\bf x}) > f({\bf x^*}),\;\;\; {\bf x} \in \mathcal{N}({\bf x}^*)
\]其中 $\mathcal{N}({\bf x}^*)$為以 ${\bf x}^*$為中心所成之鄰域。故令  ${\bf d} \in \mathbb{R}^n$ 為 在點 ${\bf x}^*$的任意可行方向,故存在 $\bar \alpha >0$ 使得
\[
{\bf x}(\alpha) := {\bf x}^* + \alpha {\bf d} \in \mathcal{N}({\bf x}^*), \;\;\; \alpha \in [0, \bar \alpha]
\] 利用 $\nabla f({\bf x}^*) = {\bf 0}$ 與 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) \\
& \hspace{10mm}+ \frac{1}{2}{\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right)^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right)\left( {{\mathbf{x}}\left( \alpha  \right) - {{\mathbf{x}}^*}} \right) + o\left( {{{\left\| \alpha  \right\|}^2}} \right) \hfill \\
 &  =f\left( {{{\mathbf{x}}^*}} \right) + \frac{1}{2}{\alpha ^2}\underbrace {{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ > 0} + o\left( {{{\left\| \alpha  \right\|}^2}} \right)\\
\end{align*}
在 ${\bf x}^*$ 附近鄰域而言,我們可推知
\[\begin{gathered}
  f\left( {{\mathbf{x}}\left( \alpha  \right)} \right) - f\left( {{{\mathbf{x}}^*}} \right) = \frac{1}{2}{\alpha ^2}\underbrace {{{\mathbf{d}}^T}\nabla^2 f\left( {{{\mathbf{x}}^*}} \right){\mathbf{d}}}_{ > 0} > 0 \hfill \\
\end{gathered} \]則 ${\bf x}^*$ 為 strict local minimum of $f$ 。$\square$

8/02/2017

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

令 $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$為一階可導且導數連續)。若 ${\bf x}^*$ 為 局部極小解 (local minimum point) of $f$ over $S$ 則 對任意在 ${\bf x}^*$點上的可行方向 ${\bf d} \in \mathbb{R}^n$,我們有
\[
\nabla f({\bf x}^*) \cdot {\bf d} \geq 0
\]======================

Proof: 用反證法:假設存在 對 ${\bf x}^*$點上的可行方向 ${\bf d} \in \mathbb{R}^n$ 使得
\[
\nabla f({\bf x}^*) \cdot {\bf d} <0
\]我們要證明矛盾。由 ${\bf d}$為可行方向之定義可知: 存在 $\bar \theta>0$ 使得 對任意 $\theta \in [0, \bar\theta]$而言,
\[
{\bf x}(\theta) = {\bf x}^* + \theta {\bf d} \in S
\]現在利用 Taylor 定理對 ${\bf x}^*$ 展開 且利用已知假設 $\nabla f({\bf x}^*) \cdot {\bf d} <0$ 可得
\begin{align*}
  f({\bf x}(\theta )) &= f({{\bf x}^*}) + \nabla f({{\bf x}^*})({\bf x}(\theta ) - {{\bf x}^*}) + o(||{\theta}||) \hfill \\
   &= f({{\bf x}^*}) + \nabla f({ {\bf x}^*})\theta {\bf d} + o(||{\theta}||) \hfill \\
  &= f({{\mathbf{x}}^*}) + \theta \underbrace {\nabla f({{\mathbf{x}}^*}) \cdot {\mathbf{d}}}_{ < 0} + o(||\theta ||)\\
   &< f({{\bf x}^*}) \hfill \\
\end{align*} 上述最後一條不等式當 $\theta$ 足夠小的時候成立。此與我們假設 $ f({ {\bf x}^*})$最小 矛盾。$\square$


Comments:
1. 上述一階必要條件說明了若我們已經處在局部最佳解的位置 ${\bf x}^*$ 則 沿著任何其他可行方向移動都會增加 目標函數值,亦即 \[
\nabla f({\bf x}^*) \cdot {\bf d} \geq  0
\]
2. 關於上述使用的 Taylor Theorem 與 little-oh 符號可以參考下方補充說明或者BLOG其餘相關文章。
3. 上述 一階必要條件 使用到了 Taylor Theorem 的一階項,一般而言可視為對 ${\bf x}^*$ 的 一階近似估計。


若為無拘束情況,則我們有以下的衍生結果:

=======================
Corollary: 令 $S \subset \mathbb{R}^n$ 且 $f \in C^1$ on $S$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 且若 ${\bf x}^*$ 為 $S$ 的 interior point 則
\[
\nabla f({\bf x}^*) = {\bf 0}
\]=======================

Proof Sketch: 設 ${\bf x}^*$ 為 local minimum point of $f$ over $S$ 則由 FONC可知 對任意 ${\bf d} \in \mathbb{R}^n$ 為在 ${\bf x}^*$點上的可行方向,我們有
\[
\nabla f({\bf x}^*) \cdot {\bf d} \geq 0
\]但因為 若 ${\bf x}^*$ 為 $S$ 的 interior point 故在該點${\bf x}^*$ 之可行方向 ${\bf d}$ 可在足夠小的區域選為任意方向來移動, 若 ${\bf d} \neq {\bf 0}$ 則 為了使 $\nabla f({\bf x}^*) \cdot {\bf d} = 0$ 成立,我們必定要求
\[
\nabla f({\bf x}^*)  = {\bf 0} \;\;\;\; \square
\]

Comments:
1. 上述 FONC 無拘束情況的 FONC 將原本最佳問題轉成求解有 $n$ 未知數的 $n$ 個系統方程問題。

2. 上述結果只保證 局部最佳解 的必要條件,如果想要得到充分條件,通常需要 $f$ 的二階導數的資訊也就是 需要 Hessian matrix,一般稱作 Second-Order Sufficient Condition我們在以後的文章會在提及。

3. 局部最佳解落在集合 $S$ 上,若此集合為 convex 集合且 $f$ 為凸函數,則局部最佳解 為 全域最佳解,相關結果可翻閱本 BLOG關於最佳化與凸分析的文章。

4. 上述最佳化問題可以與 變分不等式問題 (Variational Inequality Problem)等價,以下給出此結果:

=======================
Corollary 2: Relationship Between Optimization and Variational Inequality
令 $S \subset \mathbb{R}^n$ 為 convex 且 $f : \mathbb{R}^n \to \mathbb{R}$ 且 $f \in C^1(S)$。若 ${\bf x}^*$ 為 local minimum point of $f$ over $S$,則 ${\bf x}^*$ 為下列變分不等式問題的解:求 ${\bf x} \in S$ 使得 對任意 ${\bf x}' \in S$ 而言,
\[
\langle {\bf x}' - {\bf x}, \nabla f({\bf x}) \rangle \geq 0
\]=======================
Proof:
取 ${\bf d} := {\bf x}' - {\bf x}$ 即可。



補充定理
==================
Taylor Theorem with Little-oh Notation:
假設 $X \subset \mathbb{R}^n$ 為 open,且 ${\bf x} \in X$ 與 $f: X \to \mathbb{R}$ 為 $C^1$。則
\[
f({\bf x}+{\bf h}) = f({\bf x}) + Df({\bf x}) {\bf h} + o(||{\bf h}||),\;\;\; ||h|| \to 0
\]==================










[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...