MathLabs
定理已证明

凸函数的局部极小值即全局极小值

命题陈述

设 f:C→Rf : C \to \mathbb{R} 是凸集 C⊆RnC \subseteq \mathbb{R}^n 上的凸函数。若 x∗∈Cx^* \in C 是 ff 的局部极小点，则 x∗x^* 也是 ff 在 CC 上的全局极小点。若 ff 是严格凸函数，则全局极小点（若存在）是唯一的。

为什么成立?

凸函数的图像永远不会落在其上任意两点连线的下方，因此不存在独立的『山谷』——整张图像像一个碗一样向上弯曲。如果你站在一个小凹陷的底部，凸性迫使离开该点的每个方向都是向上的，而这沿着通往 CC 中任何其他点的整条直线段都成立，因此远处的点也不可能更低。

证明思路

假设 x∗x^* 是局部极小点但不是全局极小点：存在 y∈Cy \in C 使得 f(y)<f(x∗)f(y) < f(x^*)。对充分小的 t∈(0,1)t \in (0,1)，由凸性得 f((1−t)x∗+ty)≤(1−t)f(x∗)+tf(y)<f(x∗)f((1-t)x^* + ty) \le (1-t)f(x^*) + t f(y) < f(x^*)。但点 (1−t)x∗+ty(1-t)x^* + ty 可以任意接近 x∗x^*（只要 tt 充分小），这与 x∗x^* 是局部极小点矛盾。故不存在这样的 yy。

用到此定理的主题

凸优化

相关定理

卡罗需–库恩–塔克条件线性规划的强对偶定理

分步证明

该定理暂无分步证明。

参考文献

  1. Stephen Boyd, Lieven Vandenberghe (2004). Convex Optimization
  2. R. Tyrrell Rockafellar (1970). Convex Analysis