凸函数（补）

贡献者：吴鑫

定义 1　凸集

　　对于一个集合 $C \subseteq R^{n}, \forall x_{1}, \cdot, x_{n}, θ_{k} \in [0, 1], \sum_{k = 1}^{n} θ_{k} = 1$ 满足

\begin{matrix} (1) & θ_{1} x_{1} + \dots + θ_{n} x_{n} \in C \end{matrix}

称

C

是凸集.

定义 2　凸集

　　对于一个集合 $C \subseteq R^{n},$ 存在映射 $p : R^{n} \to R, p (x), \int_{C} p (x) d x = 1, \forall x \in C,$ 满足

\begin{matrix} (2) & \int_{C} x p (x) d x \in C \end{matrix}

称

C

是凸集.

定义 3　凸函数

　　存在映射 $f : R^{n} \to R, dom f$ 是凸集合，如果 $\forall x_{1}, x_{2} \in dom f, θ \in [0, 1],$ 满足

\begin{matrix} (3) & f (θ x_{1} + (1 - θ) x_{2}) ⩽ θ f (x_{1}) + (1 - θ) f (x_{2}) \end{matrix}

　　称映射 $f$ 是定义在 $dom f$ 上的凸函数.如果满足

\begin{matrix} (4) & f (θ x_{1} + (1 - θ) x_{2}) < θ f (x_{1}) + (1 - θ) f (x_{2}) \end{matrix}

称映射

f

是定义在

dom f

上的强凸函数.

定义 4　凹函数

　　存在映射 $f : R^{n} \to R, dom f$ 是凸集合，如果 $\forall x_{1}, x_{2} \in dom f, θ \in [0, 1],$ 满足

\begin{matrix} (5) & f (θ x_{1} + (1 - θ) x_{2}) ⩾ θ f (x_{1}) + (1 - θ) f (x_{2}) \end{matrix}

　　称映射 $f$ 是定义在 $dom f$ 上的凹函数.如果满足

\begin{matrix} (6) & f (θ x_{1} + (1 - θ) x_{2}) > θ f (x_{1}) + (1 - θ) f (x_{2}) \end{matrix}

称映射

f

是定义在

dom f

上的强凹函数.

定理 1　凸函数判定

　　 $f : R^{n} \to R$ 是凸函数，当且仅当 $g : R \to R, g (t) = f (x + t v), t = {t | x + t v \in dom f, v \in R^{n}}$ 是凸函数.

　　证明:(1)必要性

　　 $f (x)$ 是凸函数，令 $g (t) = f (x + t v),$ 那么对 $\forall t_{1}, t_{2},$ 有以下关系: $\begin{aligned} g (θ t_{1} + (1 - θ) t_{2}) & = f (x + (θ t_{1} + (1 - θ) t_{2}) v) \\ = f (x + θ t_{1} v + (1 - θ) t_{2} v) \\ = f (θ (x + t_{1} v) + (1 - θ) (x + t_{2} v)) \\ ⩽ θ f (x + t_{1} v) + (1 - θ) f (x + t_{2} v) = θ g (t_{1}) + (1 - θ) g (t_{2}) \end{aligned}$ 由此可知， $g (t)$ 是凸函数.

　　 (2)充分性

　　 $g (t) = f (x + t v)$ 是凸函数，因此，\forall \theta \in \left[ 0,1 \right] $\begin{aligned} g (θ t_{1} + (1 - θ) t_{2}) & = f (x + (θ t_{1} + (1 - θ) t_{2}) v) \\ = f (x + θ t_{1} v + (1 - θ) t_{2} v) = f (θ (x + t_{1} v) + (1 - θ) (x + t_{2} v)) \\ ⩽ θ g (t_{1}) + (1 - θ) g (t_{2}) \\ = θ f (x + t_{1} v) + (1 - θ) f (x + t_{2} v) \end{aligned}$ 令 $z_{1} = x + t_{1} v, z_{2} = x + t_{2} v,$ 上述不等式等价为 $f (θ z_{1} + (1 - θ) z_{2}) ⩽ θ f (z_{1}) + (1 - θ) f (z_{2})$ 由此可知， $f (x)$ 是凸函数.

定理 2　一阶条件

　　假设 $f : R^{n} \to R$ 一阶可微， $f : R^{n} \to R$ 是凸函数，当且仅当

\begin{matrix} (7) & f (y) ⩾ f (x) + \nabla^{⊤} f (x) (y - x) \end{matrix}

对

\forall x, y \in dom f

成立.

　　证明:(1)必要性

　　令 $z = θ y + (1 - θ) x = x + θ (y - x),$ 由凸函数定位可知， $f (θ y + (1 - θ) x) = f (x + θ (y - x)) ⩽ θ f (y) + (1 - θ) f (x)$ 整理得， $f (y) ⩾ \frac{f (x + θ (y - x)) - (1 - θ) f (x)}{θ} = f (x) + \frac{f (x + θ (y - x)) - f (x)}{θ}$ 让 $θ \to 0$ 可得 $f (y) ⩾ f (x) + lim_{θ \to 0} \frac{f (x + θ (y - x)) - f (x)}{θ} = f (x) + \nabla^{⊤} f (x) (y - x)$

　　 (2)充分性

　　令 $z = θ x + (1 - θ) y,$ 于是可以得到 $f (x) ⩾ f (z) + \nabla^{⊤} f (z) (x - z)$ $f (y) ⩾ f (z) + \nabla^{⊤} f (z) (y - z)$ 也即是 $θ f (x) + (1 - θ) f (y) ⩾ θ (f (z) + \nabla^{⊤} f (z) (x - z)) + (1 - θ) (f (z) + \nabla^{⊤} f (z) (y - z))$ 展开得 $θ f (x) + (1 - θ) f (y) ⩾ θ f (z) + θ \nabla^{⊤} f (z) (x - z) + (1 - θ) f (z) + (1 - θ) \nabla^{⊤} f (z) (y - z)$ 进一步得到 $θ f (x) + (1 - θ) f (y) ⩾ \nabla^{⊤} f (z) [θ (x - z) + (1 - θ) (y - z)] + f (z)$ 也即是 $f (z) ⩽ θ f (x) + (1 - θ) f (y)$ 即 $f (θ x + (1 - θ) y) ⩽ θ f (x) + (1 - θ) f (y)$ 因此， $f (x)$ 是凸函数.

定理 3　二阶条件

　　假设 $f : R^{n} \to R$ 二阶可微， $f : R^{n} \to R$ 是凸函数，当且仅当

\begin{matrix} (8) & \nabla^{2} f (x) ⪰ 0 \end{matrix}

对

\forall x \in dom f

成立.

　　证明:(1)必要性

　　由函数的泰勒展开, $f (y) = f (x) + \nabla^{⊤} f (x) (y - x) + \frac{1}{2} {(y - x)}^{⊤} \nabla^{2} f (x) (y - x) + o ({‖ y - x ‖}^{2})$ 再由定理 2 可知, $f (y) ⩾ f (x) + \nabla^{⊤} f (x) (y - x)$ 于是可得, $f (x) + \nabla^{⊤} f (x) (y - x) + \frac{1}{2} {(y - x)}^{⊤} \nabla^{2} f (x) (y - x) + o ({‖ y - x ‖}^{2}) ⩾ f (x) + \nabla^{⊤} f (x) (y - x)$ 因此, $\frac{1}{2} {(y - x)}^{⊤} \nabla^{2} f (x) (y - x) + o ({‖ y - x ‖}^{2}) ⩾ 0$ 也即 ${(y - x)}^{⊤} \nabla^{2} f (x) (y - x) ⩾ 0$ 由此可知 $\nabla^{2} f (x) ⪰ 0$

　　 (2)充分性

　　由函数的泰勒展开, $f (y) = f (x) + \nabla^{⊤} f (x) (y - x) + \frac{1}{2} {(y - x)}^{⊤} \nabla^{2} f (x) (y - x) + o ({‖ y - x ‖}^{2})$ 由 $\nabla^{2} f (x) ⪰$ ,因此 ${(y - x)}^{⊤} \nabla^{2} f (x) (y - x) ⩾ 0$ 也即 $f (y) = f (x) + \nabla^{⊤} f (x) (y - x) + \frac{1}{2} {(y - x)}^{⊤} \nabla^{2} f (x) (y - x) + o ({‖ y - x ‖}^{2}) ⩾ f (x) + \nabla^{⊤} f (x) (y - x)$ 由定理 2 可知， $f (x)$ 是凸函数.

习题 1　判断下列函数的凹凸性

$f (x) = max {x_{1}, \dots, x_{n}}$
$f (x) = min {x_{1}, \dots, x_{n}}$
$f (x) = \frac{1}{2} x^{⊤} P x + q^{⊤} x + r, P ⪰ 0$
$f (x) = {‖ A x - b ‖}_{2}^{2}, A \in R^{m \times n}$
$f (x) = \log \sum_{k = 1}^{n} \exp x_{k}$
$f (x) = \prod_{k = 1}^{n} {(x_{k})}^{\frac{1}{n}}$

习题 2　

　　存在映射 $f : R^{n} \to R$ ,另有映射 $g : R^{m} \to R$ ,且 $g (x) = f (A x + b)$ ,其中 $A \in R^{n \times m}, b \in R^{m}$ ,证明 $f$ 和 $g$ 的凸凹性一致.

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。

凸函数（补）

定义 1 凸集

定义 2 凸集

定义 3 凸函数

定义 4 凹函数

定理 1 凸函数判定

定理 2 一阶条件

定理 3 二阶条件

习题 1 判断下列函数的凹凸性

习题 2

定义 1　凸集

定义 2　凸集

定义 3　凸函数

定义 4　凹函数

定理 1　凸函数判定

定理 2　一阶条件

定理 3　二阶条件

习题 1　判断下列函数的凹凸性

习题 2　