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

在凸優化問題中，僅管凸性保證了任意局部最優解 (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。