[最佳化] 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(x,y ):= T_y(x) - f(x)$$

現在定義單變數輔助函數 $g: [0,1] \to \mathbb{R}$ 滿足 $$g(t) : = f(y + t(x - y))$$現在觀察 $g(0) = f(y)$ 且 $g(1) = f(x)$。我們可以計算 $g(t)$ 導數透過多變數鏈鎖律：

$$g'(t) = \nabla f(y + t(x - y))^\top (x-y)$$且

$$g''(t) = (x-y)^\top \nabla^2 f(y + t(x-y)) (x-y)$$ 其中 $\nabla^2 f$ 為 $f$ 的 Hessian matrix。那麼由 Lemma 1可知單變數Taylor Theorem 對 $g(t)$ 在 $t=0$處展開有

$$g(1) = g(0) + g'(0)(1-0) + \int_0^1 g''(t) (1-t) dt \qquad (*)$$

現在代入 $g(1) = f(x), g(0)=f(y)$ 與 $g'(0) = \nabla f(y)^\top (x-y)$，上述 式$(*)$ 可改寫為

$$f(x) = \underbrace{ f(y) + \nabla f(y)^\top (x-y) }_{T_y(x)}+ \int_0^1  (1-t) (x-y)^\top \nabla^2 f(y + t(x-y)) (x-y) dt $$

因此，我們得到

$$f(x) - T_y(x) =  \int_0^1  (1-t) (x-y)^\top \nabla^2 f(y + t(x-y)) (x-y) dt $$

回憶餘項定法為 $R(x,y ):= T_y(x) - f(x)$，故我們有 

$$R(x,y) = -\int_0^1  (1-t) (x-y)^\top \nabla^2 f(y + t(x-y)) (x-y) dt$$

Lemma 1:

令 $g \in C^2([0,1])$，則單變數Taylor Theorem 對 $g(t)$ 在 $t=0$處展開有

$$g(1) = g(0) + g'(0) + \int_0^1 g''(t) (1-t) dt$$

Proof:

給定$g \in C^2$，回憶微積分基本定理對 $g$ 函數而言，

$$g(1) - g(0) = \int_0^1 g'(t) dt \qquad (**)$$

對於 $g'(t)$ 而言，我們亦可在次使用微積分基本定理：

$$g'(1) - g'(0) = \int_0^1 g''(s) ds$$

故對任意 $t \in [0,1]$ 我們有

$$g'(t) = g'(0) + \int_0^t g''(s) ds \qquad (@)$$

將 $(@)$ 代入 $(**)$ 得到

\begin{align*}g(1) - g(0) &= \int_0^1 [g'(0) + \int_0^t g''(s) ds] dt \\ &= \int_0^1 g'(0) dt + \int_0^1 \left( \int_0^t g''(s) \right) ds dt \qquad (@@)\end{align*}

其中

$$ \int_0^1 g'(0) dt = g'(0) \cdot t|_0^1 = g'(0)$$

且

\begin{align*} \int_0^1 \left( \int_0^t g''(s) \right) ds dt &= \int_0^1 \left( \int_0^t g''(s) \right) ds dt \\ &= \int_0^1 \int_0^1 1_{\{s < t\}} g''(s) ds dt \\ &= \int_0^1 \int_0^1 1_{\{s < t\}} g''(s) dt ds \\ &= \int_0^1 g''(s) \int_s^1 dt ds \\ &= \int_0^1 g''(s) (1-s) ds \\ \end{align*}

也就是說，$(@@)$ 可改寫為

$$g(1) - g(0)  =  g'(0) + \int_0^1 g''(s) (1-s) ds $$至此得證

[凸分析] 凸優化最佳解所成之集合為凸集

在凸優化問題中，僅管凸性保證了任意局部最優解 (local minimizer) 就是 全局最優解 (global minimizer)，但凸性並沒有保證所考慮的凸優化問題 一定 存在 最優極小解。下面的結果刻劃了凸優化最佳解的性質，常被用來檢驗最佳解的存在性，是個十分有用的結果。

===========
Theorem: (凸優化最佳解的集合為凸集)
令 $S \subseteq \mathbb{R}^n$ 為 凸集合 且 $f: S\to \mathbb{R}$ 為 凸函數。令 $S^*$ 為所有極小點所成之集合亦即
\[
S^* := \{x\in S: f(x) \leq f(y), \forall \; y \in S\; \}
\] 則 $S^*$ 為凸集。
===========

Proof: 若 $S^* = \emptyset$ 則上述定理陳述自動成立。若 $S^* \neq \emptyset$，則存在 $x_0 \in S^*$。考慮 level set
\[
S_{\leq f(x_0)} := \{x\in S: f(x) \leq f(x_0)\}
\] 則不難驗證 $S_{\leq f(x_0)} = S^*$。接著由下述 Lemma 可知 $S^*$ 為 convex。至此證明完畢。$\square$


===========
Lemma: 令 $S \subseteq \mathbb{R}^n$為凸集，且 $f:S \to \mathbb{R}$  為凸函數。則對任意 $\alpha \in \mathbb{R}$， (lower) level set
$$
S_{\leq \alpha}:= \{x \in \mathbb{R}^n: f(x) \leq \alpha\}
$$ 為 凸集。
===========

Proof: 若 level set $S_{\leq \alpha}$ 為空集合或者單點集，則陳述自動成立。若不然，取 $x_1,x_2 \in S_{\leq \alpha}$ ，則 $f(x_1) \leq \alpha$ 且 $f(x_2) \leq \alpha$。我們要證明 convex combination of $x_1$ 與 $x_2$ 仍落在 $S_{\leq \alpha}$ 之中，亦即我們要證明 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$。為此，我們利用 $f$ 的凸性，對任意 $\lambda \in (0,1)$，
\[
f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) \leq \alpha
\]故 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$，至此得證。$\square$


Remark:
對於 concave 函數我們仍有類似的結果記錄如下：

令 $S \subseteq \mathbb{R}^n$ 為凸集，且 $f: S \to \mathbb{R}$ 為 concave 函數，則所有極大點所成的集合 $S^*$ 為 convex set。

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

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

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

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

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