局所最適と大域最適・凸性の役割

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：最適化問題とは・最適化問題の分類　|　関連：凸集合と凸関数

要点（BLUF）

局所最適＝近くで一番良い点、大域最適＝全体で一番良い点。一般には一致しない。
凸問題では、局所最適は必ず大域最適。これが「凸だと嬉しい」の中身。
非凸問題では、勾配法の収束先が 初期点に依存する。だから「最適解が見つかった」と言うには大域性の根拠が要る。

概念 ── 2種類の「最適」

点 $x^\star$ が 局所最適とは、その近傍 $N(x^\star)$ の中で $x^\star$ が最良なこと。大域最適とは、実行可能領域 $\mathcal{F}$ 全体で最良なこと。

x^\star \text{ が局所最適} \iff \exists \varepsilon > 0,\ \forall x \in \mathcal{F} \cap N_\varepsilon(x^\star):\ f(x^\star) \le f(x)

x^\star \text{ が大域最適} \iff \forall x \in \mathcal{F}:\ f(x^\star) \le f(x)

要するに：局所最適は「足元の谷底」、大域最適は「世界一深い谷底」。非凸の地形では谷底がいくつもあり、足元の谷が世界一とは限らない。

凸性が一致を保証する

凸集合：任意の2点を結ぶ線分が集合内に収まる。凸関数：グラフが「下に凸（お椀型）」で、任意の2点を結ぶ弦が関数の上にある。

f\bigl(\lambda x + (1-\lambda) y\bigr) \le \lambda f(x) + (1-\lambda) f(y), \quad \forall \lambda \in [0,1]

定理（凸最適化の中心的事実）： $f$ が凸関数、 $\mathcal{F}$ が凸集合のとき、任意の局所最適は大域最適。

証明のスケッチ： $x^\star$ を局所最適とし、別の点 $y \in \mathcal{F}$ で $f(y) < f(x^\star)$ と仮定する。線分上の点 $z_\lambda = \lambda y + (1-\lambda)x^\star$ は凸性より $\mathcal{F}$ 内にあり、凸関数の不等式から

f(z_\lambda) \le \lambda f(y) + (1-\lambda) f(x^\star) < f(x^\star).

$\lambda$ を十分小さくすれば $z_\lambda$ は $x^\star$ のいくらでも近くに取れるので、 $x^\star$ の任意の近傍に「より良い点」が存在することになり、 $x^\star$ が局所最適であることに矛盾する。よって $f(y) < f(x^\star)$ なる $y$ は存在せず、 $x^\star$ は大域最適。∎

この一行が、凸最適化を「解いたら終わり」にしてくれる。詳しい凸性判定は凸集合と凸関数。

Pythonで実証 ── 初期点で収束先が変わるか

非凸関数 $f(x)=x^4-3x^2+x$ は局所最適が2つある。凸関数 $g(x)=(x-2)^2$ は1つだけ。同じ勾配ベースの最適化（BFGS）を異なる初期点から回すと、非凸では収束先が割れる。

import numpy as np
from scipy.optimize import minimize

# 非凸関数 f(x) = x^4 - 3x^2 + x : 局所最適が2つある
def f_nonconvex(x):
    return x[0]**4 - 3*x[0]**2 + x[0]

# 凸関数 g(x) = (x-2)^2 : 最小は1つ
def g_convex(x):
    return (x[0]-2)**2

starts = [-2.0, 2.0]  # 2つの初期点

print("=== 非凸 f(x)=x^4-3x^2+x ===")
for s in starts:
    res = minimize(f_nonconvex, x0=[s], method="BFGS")
    print(f"  初期点 x0={s:+.1f} -> 収束点 x={res.x[0]:+.4f}, f={res.fun:+.4f}")

print("=== 凸 g(x)=(x-2)^2 ===")
for s in starts:
    res = minimize(g_convex, x0=[s], method="BFGS")
    print(f"  初期点 x0={s:+.1f} -> 収束点 x={res.x[0]:+.4f}, g={res.fun:+.6f}")

実行結果：

=== 非凸 f(x)=x^4-3x^2+x ===
  初期点 x0=-2.0 -> 収束点 x=-1.3008, f=-3.5139
  初期点 x0=+2.0 -> 収束点 x=+1.1309, f=-1.0702
=== 凸 g(x)=(x-2)^2 ===
  初期点 x0=-2.0 -> 収束点 x=+2.0000, g=+0.000000
  初期点 x0=+2.0 -> 収束点 x=+2.0000, g=+0.000000

非凸では、初期点 $-2$ から始めると深い谷（ $f=-3.51$ 、こちらが大域最適）に、初期点 $+2$ から始めると浅い谷（ $f=-1.07$ 、これは大域最適ではない局所最適）に落ちる。勾配法は「足元の谷」に落ちるだけで、世界一深い谷を保証しない。凸の $g$ ではどこから始めても同じ $x=2$ に収束する。

数式の直観的意味

凸性の不等式「弦は関数の上にある」が、なぜ局所＝大域を生むのか。お椀型の関数には「下り坂を辿れば必ず一番下に着く」性質がある。途中に偽の谷底（下り坂が止まるのに最小でない点）が存在しない。非凸関数はこぶがあるので、下り坂が偽の谷底で止まる。つまり凸性とは 「下降方向を辿る素朴なアルゴリズムが大域最適に到達できる」幾何条件の言い換えである。これが第4章の勾配法・第5章の凸最適化すべての土台になる。

⚠️ よくある誤解・落とし穴

「勾配がゼロ＝最適」ではない。勾配ゼロは停留点（極小・極大・鞍点）の必要条件にすぎない（最適性条件の地図）。
「収束したから大域最適」ではない。非凸では初期点依存。複数初期点・大域最適化（焼きなまし等、第6章）が要る。
凸性は目的関数だけでなく実行可能領域にも要る。凸関数でも制約集合が非凸なら局所最適が複数あり得る。
「線形だから安心」ではなく「線形ゆえに凸だから安心」。難しさの根は非凸性（最適化問題の分類）。