サンプル平均近似（SAA）

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

📎 前提：確率計画法　|　関連：焼きなまし法

要点（BLUF）

SAA は確率計画の 期待値 $\mathbb{E}[f(x,\xi)]$ を、標本平均 $\frac1N\sum f(x,\xi_i)$ で置き換える手法。
期待値の積分が解けなくても、シナリオを モンテカルロでサンプリングして有限の最適化問題にできる。
標本数 $N$ を増やすと、SAA の最適解は 真の最適解に収束（大数の法則・一様収束）。

概念 ── 期待値を標本で近似する

確率計画（確率計画法）の目的 $\mathbb{E}_\xi[f(x,\xi)]$ は、分布が複雑だと積分できない。SAA は発想を変え、分布から $N$ 個のシナリオ $\xi_1,\dots,\xi_N$ をサンプリングし、期待値を標本平均で近似する：

\min_x\ \mathbb{E}_\xi[f(x,\xi)] \quad\approx\quad \min_x\ \frac{1}{N}\sum_{i=1}^N f(x,\xi_i)

右辺は 有限個のシナリオ上の決定論的最適化になり、これまでの章の手法（LP・凸最適化）で解ける。分布が「サンプリングできさえすれば」適用できるのが強み ── シミュレーション（モンテカルロ）と最適化の橋。

graph LR
  A["真の問題 min E[f(x,ξ)] (積分は解けない)"] --> B["分布から N シナリオをサンプリング"]
  B --> C["標本平均 (1/N)Σ f(x,ξ_i) を最小化"]
  C --> D["有限の決定論的最適化として求解"]
  D --> E["N を増やすと真の最適へ収束"]

収束の保証

SAA の最適値 $\hat z_N$ と最適解 $\hat x_N$ について：

大数の法則：各固定 $x$ で標本平均 $\to$ 真の期待値（ $N\to\infty$ ）。
一様収束（適切な条件下）：最適値 $\hat z_N \to z^\star$ 、最適解 $\hat x_N \to x^\star$ 。
収束の速さはおよそ $O(1/\sqrt{N})$ （モンテカルロの標準誤差）。精度を10倍上げるには標本100倍。

つまり「標本を増やせば真の最適に近づく」が理論的に保証される。実務では複数の独立な SAA を解いて、最適値の信頼区間（統計的下界・上界）を作る。

Pythonで収束を確認

新聞売り子問題（確率計画法、最適発注量は真には100）を、標本数 $N$ を変えて SAA で解く。 $N$ が増えると SAA 最適発注量が 100 に近づく。

import numpy as np

p, c, s = 10.0, 6.0, 2.0          # 売価・仕入・残価

def saa_optimal_order(N, seed=0):
    rng = np.random.default_rng(seed)
    demands = rng.normal(100, 20, N)        # N個のシナリオを生成
    # 標本平均利益を最大にする発注量をグリッド探索
    grid = np.arange(60, 141, 1.0)
    def sample_avg_profit(x):
        sales = np.minimum(x, demands)
        leftover = np.maximum(0, x - demands)
        return np.mean(p*sales + s*leftover - c*x)
    return grid[int(np.argmax([sample_avg_profit(x) for x in grid]))]

print("真の最適発注量 = 100 (臨界比0.5の中央値)")
for N in [10, 100, 1000, 10000]:
    print(f"  N={N:>5}: SAA最適発注 = {saa_optimal_order(N):.0f}")

実行結果：

真の最適発注量 = 100 (臨界比0.5の中央値)
  N=   10: SAA最適発注 = 102
  N=  100: SAA最適発注 = 101
  N= 1000: SAA最適発注 = 99
  N=10000: SAA最適発注 = 100

標本 $N=10$ では 102 とぶれるが、 $N$ を増やすと $101\to99\to100$ と 真の最適 100 へ収束。少ない標本では偶然のシナリオに振り回されるが、標本を増やせば標本平均が真の期待値に一致し、最適解も一致する。これが SAA の働き。

数式の直観的意味

SAA は「最適化と統計推定の融合」。標本平均 $\frac1N\sum f(x,\xi_i)$ は真の期待値の 不偏推定量で、 $x$ を固定すれば標準誤差 $O(1/\sqrt N)$ で真値に収束する（中心極限定理）。難しいのは「すべての $x$ について同時に（一様に）収束するか」で、これが保証されれば最適解も収束する ── 凸性（凸集合と凸関数）や有界性があると一様収束が言える。重要な性質として、SAA の最適値は真の最適値を 平均的に過小評価する（ $\mathbb{E}[\hat z_N]\le z^\star$ 、最小化の場合）── 同じ標本で「最適化」と「評価」を同時に行うと楽観バイアスが乗る。だから別標本で解を評価して上界を取り、楽観バイアスを補正する。SAA は焼きなまし（焼きなまし法）のようなシミュレーションベース最適化や、機械学習の経験損失最小化（期待損失を訓練標本平均で近似）とも同じ思想を共有する。

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

同じ標本で解いて評価すると楽観バイアス：最適値を過小評価（最小化）。評価は別標本で。
収束は $O(1/\sqrt N)$ と遅い：精度を上げるには大量の標本。分散減少法（重点サンプリング・準モンテカルロ）が効く。
標本数 $N$ が小さいと解がぶれる：複数の独立 SAA を解いて信頼区間を作る。
まれな重要事象（テールリスク）は素朴なサンプリングで捉えにくい。リスク尺度なら CVaR（リスクを織り込む最適化（CVaR最小化））と重点サンプリング。