凸集合と凸関数｜数理最適化

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

📎 前提：局所最適と大域最適・凸性の役割　|　関連：凸最適化問題と双対理論

要点（BLUF）

凸集合＝任意の2点を結ぶ線分が集合内に収まる。凸関数＝グラフが下に凸（弦が関数の上）。
判定法：1次条件（接線が関数を下から支える）、2次条件（ヘッセ行列が半正定値）。
凸性が「局所最適＝大域最適」（局所最適と大域最適・凸性の役割）を保証する数学的な核。

凸集合

集合 $C \subseteq \mathbb{R}^n$ が凸とは、任意の $x,y \in C$ と $\lambda \in [0,1]$ について

\lambda x + (1-\lambda) y \in C

つまり「2点を結ぶ線分がはみ出さない」。半空間・超平面・球・凸多面体（線形計画の標準形と幾何）は凸。凸集合の 共通部分は凸（だから線形制約の交わりは凸）。和集合は一般に凸でない。

凸関数

関数 $f$ が凸とは、定義域が凸集合で、任意の $x,y$ と $\lambda\in[0,1]$ について

f\bigl(\lambda x + (1-\lambda) y\bigr) \le \lambda f(x) + (1-\lambda) f(y)

左辺は「2点の中間での関数値」、右辺は「2点を結ぶ弦の高さ」。弦が関数の上にあるのが凸（お椀型）。この不等式が Jensen の不等式。狭義凸は $<$ （弦が真に上）。

判定法

1次条件（微分可能なとき）

f(y) \ge f(x) + \nabla f(x)^\top (y - x) \quad \forall x, y

接線（接平面）が関数を下から支える。凸関数のグラフは、どの点の接線より常に上にある。これが「停留点が大域最小」を生む： $\nabla f(x)=0$ なら $f(y)\ge f(x)$ が全 $y$ で成り立つ。

2次条件（2回微分可能なとき）

\nabla^2 f(x) \succeq 0 \quad (\text{ヘッセ行列が半正定値}) \quad \forall x

1変数なら $f''(x)\ge0$ （下に凸）。多変数ならヘッセの固有値がすべて非負。曲率がどこでも非負＝へこまない。狭義凸は $\succ 0$ （正定値）。

graph TD
  A["凸関数か?"] --> B["定義: 弦が関数の上 (Jensen)"]
  A --> C["1次条件: 接線が下から支える"]
  A --> D["2次条件: ヘッセ半正定値 (どこでも凸)"]
  B --> E["局所最適 = 大域最適 を保証"]
  C --> E
  D --> E

凸性を保つ演算

複雑な関数の凸性は、組み立てで判定できる：

非負結合： $f,g$ 凸 $\Rightarrow$ $\alpha f + \beta g$ 凸（ $\alpha,\beta\ge0$ ）。
最大値： $f,g$ 凸 $\Rightarrow$ $\max(f,g)$ 凸（区分線形の最大も凸）。
アフィン合成： $f$ 凸 $\Rightarrow$ $f(Ax+b)$ 凸。
ノルム $\|x\|$ はすべて凸。 $-\ln x$ 、 $e^x$ 、 $x^2$ は凸。

これらの規則を組み合わせるのが cvxpy の DCP（実装：cvxpyで凸問題を解く）の土台。

Pythonで Jensen を確認

$f(x)=x^2$ が凸かを、いくつかの内分点で「中間の値 ≤ 弦」を確認する。

a, b = -1.0, 3.0     # 2点
for lam in [0.25, 0.5, 0.75]:
    z = lam*a + (1-lam)*b               # 内分点
    f_mid = z**2                        # 関数の値
    chord = lam*a**2 + (1-lam)*b**2     # 弦の高さ
    print(f"lam={lam}: f(中間)={f_mid:.4f} <= 弦={chord:.4f} ? {f_mid <= chord}")

実行結果：

lam=0.25: f(中間)=4.0000 <= 弦=7.0000 ? True
lam=0.5: f(中間)=1.0000 <= 弦=5.0000 ? True
lam=0.75: f(中間)=0.0000 <= 弦=3.0000 ? True

どの内分点でも「関数の値 ≤ 弦」が成り立つ ── $f(x)=x^2$ は凸。 $f''(x)=2>0$ （2次条件）とも整合。差「弦 − 関数」が凸性の余裕で、最適化ではこれが下界の精度（双対ギャップ、凸最適化問題と双対理論）に効く。

数式の直観的意味

凸関数の3つの見方（Jensen・接線・ヘッセ）は同値だが、効く場面が違う。Jensenは定義そのもので、確率の期待値（ $E[f(X)]\ge f(E[X])$ ）に直結。1次条件は「接線が大域的下界」を与え、勾配法の収束証明や双対の下界に使う。2次条件は計算的に最も実用的で、ヘッセの固有値を見るだけで判定できる。本質は「曲率が一方向（上）にしか曲がらない」こと ── だから一度下り始めれば偽の谷に捕まらず、局所最適が大域最適になる（局所最適と大域最適・凸性の役割）。凹関数は $-f$ が凸で、最大化が凸最小化に対応する。

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

凸関数と凸集合は別概念：凸関数の「下位集合」 $\{x: f(x)\le t\}$ は凸だが、関数自体と集合を混同しない。
2次条件は半正定値（ $\succeq0$ ）で凸、正定値（ $\succ0$ ）で狭義凸。半正定値だと平らな部分（複数最適）があり得る。
線形関数は凸かつ凹（ヘッセ=0）。だから LP は凸（最適化問題の分類）。
凸性は定義域込み。 $\ln x$ は凹だが定義域 $x>0$ を忘れると判定を誤る。