定理証明済み

凸関数の局所最小値は大域最小値である

内容

$f : C \to \mathbb{R}$ を凸集合 $C \subseteq \mathbb{R}^n$ 上の凸関数とする。 $x^* \in C$ が $f$ の局所最小点であれば、 $x^*$ は $f$ が $C$ 上でとる大域最小点でもある。 $f$ が狭義凸であれば、大域最小点は存在すれば一意である。

なぜ正しいのか?

凸関数のグラフは、その上の任意の2点を結ぶ直線より下に落ち込むことがないため、独立した『谷』を持たない——グラフ全体が一つの椀のように上に反っている。小さなくぼみの底に立っているとすると、凸性によりそこから離れるあらゆる方向は上りとなる。これは $C$ 内の他のどの点への直線経路に沿っても成り立つため、遠くの点がより低くなることはあり得ない。

証明の概略

$x^*$ が局所最小だが大域的でないと仮定する： $y \in C$ で $f(y) < f(x^*)$ を満たすものが存在する。小さな $t \in (0,1)$ に対し、凸性より $f((1-t)x^* + ty) \le (1-t)f(x^*) + t f(y) < f(x^*)$ が成り立つ。しかし点 $(1-t)x^* + ty$ は $x^*$ に、 $t$ を小さくとればいくらでも近づくため、 $x^*$ が局所最小であることに矛盾する。よってそのような $y$ は存在しない。

この定理を使うトピック

凸最適化

参考文献

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