第7章確率的最適化と離散最適化（最適化）

この章の目標

確率的勾配降下法の誤差の期待値が $O(1/\sqrt{k})$ になることを、期待値の評価の仕方まで含めて証明できる

ミニバッチ・モメンタム・Adam の考え方と保証の有無、非凸最適化の難しさを説明できる

整数計画を定式化し、LP 緩和・全単模性・分枝限定法・切除平面を説明できる

ダイクストラ法とクラスカル法の正しさを証明し、仮定が外れたときの反例を示せる

動的計画法・擬多項式時間・NP 困難・近似アルゴリズムの意味を正確に述べられる

前提：第2章、第3章、第5章、22-statistics 第1章（期待値と独立性）。7.3 節では第1章の局所最小点と鞍点を、7.4 節では 02-linear-algebra 第4章のクラメルの公式を、7.9 節では 25-cryptography-coding 第1章の多項式時間の考え方を使う。

第5章・第6章の方法は、勾配を正確に計算できる、なめらかで凸な問題で威力を発揮した。実務ではこの前提が崩れる場面が二つある。一つはデータが多すぎる場面で、少数のデータで勾配を見積もって進む確率的勾配降下法が使われる（7.1〜7.3 節）。もう一つは、倉庫を建てるか、誰をどの勤務に割り当てるか、のように決定が離散的な場面で、実行可能領域は凸でなくなる（7.4〜7.9 節）。最後に NP 困難の正確な意味を述べる。

7.1 確率的勾配降下法

データ $(a_i, y_i)$ （ $i = 1, \dots, m$ ）の損失の平均 $f(x) = \frac{1}{m}\sum_{i=1}^{m} f_i(x)$ を最小にする経験リスク最小化では（ロジスティック回帰なら $f_i(x) = \log(1 + e^{a_i^{\top}x}) - y_ia_i^{\top}x$ 。第1章例 1.6）、添字 $i$ を等確率で選べば $E[\nabla f_i(x)] = \nabla f(x)$ で、1 件分の計算で「平均すれば正しい」方向が得られる。反復点は確率変数になるので、収束は期待値で評価する。測度論を避けるため、乱数は有限個の値をとるとする（一般の場合は注意 7.5 の (3)）。

定義 7.1（確率的勾配降下法, stochastic gradient descent） $C \subset \mathbb{R}^n$ を空でない閉凸集合、 $f\colon C \to \mathbb{R}$ を凸関数とし、 $f$ は $C$ 上で最小点 $x^{\ast}$ をもつとする。有限集合 $\Xi$ に値をとる確率変数 $\xi$ と写像 $g\colon C \times \Xi \to \mathbb{R}^n$ が、ある $G > 0$ について次を満たすとする。

（不偏性）すべての $x \in C$ で、 $\bar{g}(x) := E[g(x, \xi)]$ は $f$ の $x$ における劣勾配である（第2章定義 2.26）。

（2 次モーメントの有界性）すべての $x \in C$ で $E[\lVert g(x, \xi) \rVert^2] \leq G^2$ 。

$g(x, \xi)$ を確率的勾配 (stochastic gradient) という。 $\xi$ と同じ分布に従う独立な確率変数の列 $\xi_0, \xi_1, \dots$ 、初期点 $x_0 \in C$ 、ステップ幅（学習率） $\eta_t > 0$ に対し
$x_{t+1} = P_C\bigl(x_t - \eta_t\,g(x_t, \xi_t)\bigr) \qquad (t = 0, 1, 2, \dots)$
で点列を作る方法を確率的勾配降下法（SGD）という。 $P_C$ は第2章定理 2.4 の射影である（ $C = \mathbb{R}^n$ なら恒等写像）。

例 7.2 $\Xi = \lbrace 1, \dots, m \rbrace$ 上の一様分布と $g(x, i) = \nabla f_i(x)$ （ $f_i$ は微分可能な凸関数）をとれば条件 1 が成り立つ。ロジスティック回帰では $\nabla f_i(x) = (\sigma(a_i^{\top}x) - y_i)a_i$ （ $\sigma$ はシグモイド関数）と $0 < \sigma < 1$ , $y_i \in \lbrace 0, 1 \rbrace$ より $\lVert \nabla f_i(x) \rVert \leq \lVert a_i \rVert$ なので、条件 2 は $G^2 = \frac{1}{m}\sum_i \lVert a_i \rVert^2$ で成り立つ。

収束の証明では、「 $x_t$ を固定して $\xi_t$ についてだけ平均してよい」という次の補題が要になる。

補題 7.3 $X$ を有限個の値をとる確率ベクトル、 $\xi$ を $X$ と独立で $\Xi$ に値をとる確率変数、 $h$ を実数値関数とし、 $\varphi(x) = E[h(x, \xi)]$ とおく。このとき $E[h(X, \xi)] = E[\varphi(X)]$ である。

証明. 独立性より $P(X = x, \xi = z) = P(X = x)P(\xi = z)$ （22-statistics 第1章命題 1.4 の 1）なので、 $X$ のとる値 $x$ について和をとると

E[h(X, \xi)] = \sum_{x}\sum_{z \in \Xi} h(x, z)P(X = x)P(\xi = z) = \sum_{x} P(X = x)\varphi(x) = E[\varphi(X)]

である。 $\square$

定理 7.4（確率的勾配降下法の収束）定義 7.1 の設定で $\lVert x_0 - x^{\ast} \rVert \leq R$ とし、ステップ幅を一定値 $\eta_t = \eta$ として $k$ 回反復する。平均反復点 $\bar{x}_k = \frac{1}{k}\sum_{t=0}^{k-1} x_t$ について
$E[f(\bar{x}_k)] - f(x^{\ast}) \leq \frac{R^2}{2\eta k} + \frac{\eta G^2}{2}$
が成り立つ（期待値は $\xi_0, \dots, \xi_{k-1}$ についてとる）。特に $\eta = R/(G\sqrt{k})$ とすると $E[f(\bar{x}_k)] - f(x^{\ast}) \leq RG/\sqrt{k}$ である。

証明. $g_t = g(x_t, \xi_t)$ , $D_t = \lVert x_t - x^{\ast} \rVert^2$ とおく。 $x_t$ は $\xi_0, \dots, \xi_{t-1}$ の関数なので有限個の値しかとらず、 $\xi_t$ と独立である（22-statistics 第1章命題 1.4 の 3）。(a) は乱数のどの実現値でも成り立つ不等式で、(b)・(c) が期待値の評価である。

(a) $x^{\ast} = P_C(x^{\ast})$ と射影の非拡大性（定理 2.4）より

D_{t+1} \leq \lVert x_t - \eta g_t - x^{\ast} \rVert^2 = D_t - 2\eta\langle g_t, x_t - x^{\ast} \rangle + \eta^2\lVert g_t \rVert^2 \tag{7.1}

(b) 補題 7.3 を $X = x_t$ , $\xi = \xi_t$ , $h(x, z) = \langle g(x, z), x - x^{\ast} \rangle$ に使う。 $\varphi(x) = \langle \bar{g}(x), x - x^{\ast} \rangle$ で、 $\bar{g}(x)$ は劣勾配だから定義 2.26 の不等式で $y = x^{\ast}$ とすると $\varphi(x) \geq f(x) - f(x^{\ast})$ 。よって $E[\langle g_t, x_t - x^{\ast} \rangle] = E[\varphi(x_t)] \geq E[f(x_t)] - f(x^{\ast})$ 。

(c) $h(x, z) = \lVert g(x, z) \rVert^2$ とすると $\varphi(x) = E[\lVert g(x, \xi) \rVert^2] \leq G^2$ なので、 $E[\lVert g_t \rVert^2] \leq G^2$ 。

(7.1) の期待値をとり（期待値の線形性と単調性。22-statistics 第1章命題 1.6）、(b)・(c) を使うと

E[D_{t+1}] \leq E[D_t] - 2\eta\bigl(E[f(x_t)] - f(x^{\ast})\bigr) + \eta^2G^2

$t = 0, \dots, k - 1$ について足すと $E[D_t]$ の項が打ち消し合い、 $E[D_k] \geq 0$ と $D_0 \leq R^2$ より

2\eta\sum_{t=0}^{k-1}\bigl(E[f(x_t)] - f(x^{\ast})\bigr) \leq D_0 - E[D_k] + k\eta^2G^2 \leq R^2 + k\eta^2G^2

$C$ は凸なので $\bar{x}_k \in C$ で、イェンセンの不等式（第2章命題 2.13 の 4）より実現値ごとに $f(\bar{x}_k) \leq \frac{1}{k}\sum_{t=0}^{k-1} f(x_t)$ 。期待値をとって上の不等式と合わせ、 $2\eta k$ で割れば主張を得る。右辺 $\frac{R^2}{2\eta k} + \frac{\eta G^2}{2}$ は相加相乗平均の不等式より $\eta = R/(G\sqrt{k})$ で最小値 $RG/\sqrt{k}$ をとる。 $\square$

注意 7.5 (1) 必要な反復回数 $(RG/\varepsilon)^2$ はデータ数 $m$ によらない。全データの勾配を使う勾配法は、 $L$ -平滑な凸関数なら誤差 $O(1/k)$ と速い（第5章定理 5.7）が、1 回に $m$ 件分の計算が要る。(2) $\Xi$ が 1 点なら劣勾配法 (subgradient method) で、 $L$ -平滑でない凸関数にも同じ保証が得られる。(3) $\xi$ が連続分布に従っても、 $h(X, \xi)$ が可積分なら補題 7.3 は成り立ち（同時分布が直積測度であること（11-probability 第1章定理 1.25）とフビニの定理（06-measure-integration 第5章定理 5.7）による）、証明はそのまま通用する。最後の点 $x_k$ のほとんど確実な収束などには、マルチンゲール（11-probability 第5章）を使う。

定理 7.4 はすべての凸問題に対する保証なので、上界は控えめである。乱数で作ったロジスティック回帰の問題（データ 1000 件、特徴量 1 個と切片、 $x_0 = 0$ 、 $G$ は例 7.2 の値）で $\eta = R/(G\sqrt{k})$ とすると、平均反復点の誤差の期待値（独立な 100 回の実行の平均）は $k = 10, 10^3, 10^5$ で約 $0.14, 0.0070, 0.000062$ と、上界 $RG/\sqrt{k} \approx 0.99, 0.099, 0.0099$ の 6 分の 1 以下だった（計算機で確かめた）。強凸性があれば収束は速くなる。

定理 7.6（強凸な場合）定義 7.1 の設定で、さらに $f$ は $C$ を含む開凸集合上で微分可能かつ $\mu$ -強凸（第2章定義 2.21）で、 $\bar{g}(x) = \nabla f(x)$ とする。添字を $1$ から始めて $x_1 \in C$ とし、 $\eta_t = \frac{2}{\mu(t + 1)}$ （ $t = 1, \dots, k$ ）で反復して、重み $t$ の平均 $\tilde{x}_k = \frac{2}{k(k + 1)}\sum_{t=1}^{k} tx_t$ をとると
$E[f(\tilde{x}_k)] - f(x^{\ast}) \leq \frac{2G^2}{\mu(k + 1)}$

証明は問題 7.2 とする。誤差は $O(1/k)$ に改善し、初期点にもよらない。ただし $C = \mathbb{R}^n$ では $\lVert \nabla f(x) \rVert \geq \mu\lVert x - x^{\ast} \rVert$ で勾配が有界でなく、 $\lVert \bar{g}(x) \rVert^2 \leq E[\lVert g(x, \xi) \rVert^2]$ （命題 7.7）より条件 2 が成り立たない。有界な $C$ への射影とともに使う定理である。

7.2 ミニバッチ・モメンタム・適応的な学習率

実際には、1 回に $b$ 件のデータ（ミニバッチ, mini-batch）の勾配の平均を使うことが多い。

命題 7.7（ミニバッチによる分散の減少） $x \in C$ を固定し、 $\xi^{(1)}, \dots, \xi^{(b)}$ を $\xi$ と同じ分布に従う独立な確率変数、 $g_B = \frac{1}{b}\sum_{j=1}^{b} g(x, \xi^{(j)})$ とする。 $\sigma^2(x) = E[\lVert g(x, \xi) - \bar{g}(x) \rVert^2]$ とおくと
$E[g_B] = \bar{g}(x), \qquad E[\lVert g_B - \bar{g}(x) \rVert^2] = \frac{\sigma^2(x)}{b}, \qquad E[\lVert g_B \rVert^2] = \lVert \bar{g}(x) \rVert^2 + \frac{\sigma^2(x)}{b}$

証明. 1 番目は線形性による。 $u_j = g(x, \xi^{(j)}) - \bar{g}(x)$ は独立で $E[u_j] = 0$ , $E[\lVert u_j \rVert^2] = \sigma^2(x)$ であり、 $j \neq l$ なら $E[\langle u_j, u_l \rangle] = \sum_r E[u_{j,r}]E[u_{l,r}] = 0$ （22-statistics 第1章命題 1.6 の 3）なので、 $E[\lVert \sum_j u_j \rVert^2] = b\sigma^2(x)$ を $b^2$ で割れば 2 番目を得る。3 番目は $\lVert g_B \rVert^2 = \lVert \bar{g}(x) \rVert^2 + 2\langle \bar{g}(x), g_B - \bar{g}(x) \rangle + \lVert g_B - \bar{g}(x) \rVert^2$ の期待値をとればよい。 $\square$

組 $(\xi^{(1)}, \dots, \xi^{(b)})$ を 1 つの確率変数とみればミニバッチ版も定義 7.1 の形で、 $C$ 上で $\lVert \bar{g}(x) \rVert \leq M$ , $\sigma^2(x) \leq \sigma^2$ なら $G_b^2 = M^2 + \sigma^2/b$ ととれる。反復回数は $b$ とともに減るが、勾配の計算回数 $N = bk$ で書くと上界 $RG_b/\sqrt{k}$ は $R\sqrt{bM^2 + \sigma^2}/\sqrt{N}$ で、 $b$ について増加する。利点は、GPU などで $b$ 個の勾配を並列に計算すれば反復の時間がほとんど増えないことにある（問題 7.1）。

深層学習では、過去の勾配で方向や大きさを調整する方法が広く使われる（以下は紹介にとどめる）。モメンタム法（重球法。ポリャク, 1964 年）は $v_{t+1} = \beta v_t + g_t$ , $x_{t+1} = x_t - \eta v_{t+1}$ （ $0 \leq \beta < 1$ , $v_0 = 0$ ）とする。 $v_{t+1} = \sum_{s=0}^{t}\beta^{t-s}g_s$ では、反復ごとに符号が変わる成分（細長い谷を横切る振動）は打ち消し合い、一定の向きの成分は最大 $1/(1 - \beta)$ 倍に強まる。

Adam（Kingma–Ba, 2015 年）は、勾配の指数移動平均（モメンタム）を、勾配の 2 乗の指数移動平均の平方根で座標ごとに割る（ $g_t^2$ 、平方根、割り算は成分ごと）。 $x_{t-1}$ での確率的勾配を $g_t$ とし、 $m_0 = v_0 = 0$ から $t = 1, 2, \dots$ について

\begin{aligned} m_t &= \beta_1m_{t-1} + (1 - \beta_1)g_t, & v_t &= \beta_2v_{t-1} + (1 - \beta_2)g_t^2, \\ \hat{m}_t &= \frac{m_t}{1 - \beta_1^t}, & \hat{v}_t &= \frac{v_t}{1 - \beta_2^t}, \qquad x_t = x_{t-1} - \alpha\frac{\hat{m}_t}{\sqrt{\hat{v}_t} + \varepsilon} \end{aligned}

とする（推奨値は $\alpha = 0.001$ , $\beta_1 = 0.9$ , $\beta_2 = 0.999$ 、 $\varepsilon = 10^{-8}$ は $0$ で割るのを避ける定数）。勾配がずっと一定値 $g$ なら $m_t = (1 - \beta_1^t)g$ , $v_t = (1 - \beta_2^t)g^2$ で、 $1 - \beta^t$ で割るバイアス補正により $\hat{m}_t/\sqrt{\hat{v}_t} = g/\lvert g \rvert$ となる（補正がないと、推奨値で $t = 10$ の更新が約 $6.5$ 倍になる）。AdaGrad（Duchi–Hazan–Singer, 2011 年）や RMSProp も同じ系統の方法である。

Adam の元論文の凸の場合の収束証明には誤りがあり、Reddi–Kale–Kumar（2018 年）は収束しない凸の例を示した。区間 $[-1, 1]$ 上で、3 回に 1 回は $f_t(x) = Cx$ （ $C > 2$ ）、残りは $f_t(x) = -x$ が順に現れると、平均 $\frac{C - 2}{3}x$ の最小点は $x = -1$ なのに、 $\beta_1 = 0$ , $\beta_2 = 1/(1 + C^2)$ の Adam（ステップ幅 $\alpha/\sqrt{t}$ 、区間への射影つき）は最悪の点 $x = 1$ に近づく（計算機でも確かめた）。彼らは確率的な設定の例も与え、修正版 AMSGrad を提案した。

ヒント

実務では (1) 学習率は最も影響の大きい設定で、 $R$ , $G$ は普通わからないので、検証用データの損失を見ながら調整し、後半に小さくしていくことが多い。(2) 多くの実装はデータを無作為に並べ替えて 1 周（エポック）ずつ使う。これは非復元抽出で、独立性の仮定とは異なる。(3) $R$ , $G$ は特徴量の尺度で大きく変わるので、ここでも標準化が重要である。

7.3 非凸最適化の難しさ

凸でない問題（ニューラルネットワークの学習など）で勾配法に保証できるのは、一般には停留点への収束までである。障害は、大域最小点でない局所最小点（第1章例 1.15）と鞍点（第1章 1.5 節）で、鞍点の近くでは勾配が小さいので反復が停滞し、「勾配が小さくなったら止める」という停止条件もだまされる。

定義 7.8（狭義の鞍点） $C^2$ 級の関数 $f$ の停留点 $x^{\ast}$ で、 $\nabla^2 f(x^{\ast})$ が負の固有値をもつものを狭義の鞍点 (strict saddle point) という。

第1章定理 1.18 より狭義の鞍点は局所最小点でない（この定義では局所最大点も含む）。一方、第1章例 1.20 の $x^2 + y^3$ の原点のように、ヘッセ行列が半正定値の鞍点は狭義の鞍点でない。

例 7.9（鞍点での停滞） $f(x, y) = \cos x + y^2/2$ の停留点 $(j\pi, 0)$ （ $j \in \mathbb{Z}$ ）は、 $\nabla^2 f = \operatorname{diag}(-\cos x, 1)$ より $j$ が偶数なら狭義の鞍点（値 $1$ ）、奇数なら最小点（値 $-1$ ）である。ステップ幅 $1/2$ の勾配法 $x_{t+1} = x_t + \frac{1}{2}\sin x_t$ , $y_{t+1} = \frac{1}{2}y_t$ は、初期点 $(10^{-8}, 1)$ から 14 回目に約 $(2.9 \times 10^{-6}, 6.1 \times 10^{-5})$ で $\lVert \nabla f \rVert < 10^{-4}$ となり、そこで止めると鞍点のそばで止まる（計算機で確かめた）。 $x \mapsto x + \frac{1}{2}\sin x$ は狭義単調増加で $\pi\mathbb{Z}$ の点だけを動かさないので、区間 $(j\pi, (j + 1)\pi)$ の点は $\pi$ の奇数倍の端点に向かい、鞍点に収束するのは $x_0 \in 2\pi\mathbb{Z}$ のときだけである。この現象は一般に成り立つ。

定理 7.10（Lee–Simchowitz–Jordan–Recht, 2016 年） $f\colon \mathbb{R}^n \to \mathbb{R}$ を $C^2$ 級で $L$ -平滑な関数、 $0 < \eta < 1/L$ とし、 $x^{\ast}$ を $f$ の狭義の鞍点とする。勾配法 $x_{t+1} = x_t - \eta\nabla f(x_t)$ が $x^{\ast}$ に収束するような初期点 $x_0$ の全体は、ルベーグ測度 $0$ の集合（06-measure-integration 第2章定義 2.9）である。特に、密度をもつ分布から $x_0$ を選べば、 $x^{\ast}$ に収束する確率は $0$ である。

（主張のみ。証明は力学系の安定多様体定理による。）例 7.9 の $f$ は $\lVert \nabla^2 f \rVert \leq 1$ なので $1$ -平滑（第2章定理 2.23）である。

注意 7.11 (1) 定理 7.10 は、勾配法が収束することも、局所最小点に収束することも保証しない。狭義でない鞍点では結論も成り立たない。 $f(x) = \sin^3 x$ は $3$ -平滑で、停留点 $0$ （ $f''(0) = 0$ ）は鞍点だが、 $0 < x_0 < \min(\pi/2, 1/(3\eta))$ のすべての点から勾配法は $0$ に収束する（ $0 < x < \pi/2$ では $0 < 3\eta\sin^2 x\cos x \leq 3\eta x^2$ なので $x_t > x_{t+1} \geq x_t(1 - 3\eta x_t) > 0$ となり、単調に減る $x_t$ の極限は停留点 $0$ である）。(2) 鞍点のそばから抜け出すまでの反復回数は、次元について指数的になりうる（Du ら, 2017 年）。一方、勾配が小さいときに反復点へ小さな乱数を加える方法では、ヘッセ行列がリプシッツ連続なら、高い確率で、その回数の次元への依存は対数の多項式にとどまる（Jin ら, 2017 年）。(3) 局所最小点の問題はもっと深刻で、4 次多項式でも大域最小値の計算は NP 困難である（例 7.35）。

7.4 整数計画

トラックの台数や「倉庫を建てるか」のような決定は、整数で表す必要がある。

定義 7.12（整数計画・線形緩和）線形計画問題に「変数の一部が整数」という制約を加えた問題を混合整数計画問題、すべての変数が整数なら整数計画問題 (integer programming problem)、さらに $0$ か $1$ に限られるなら 0-1 整数計画問題という。整数の制約を外した線形計画問題を線形緩和（LP 緩和, LP relaxation）という。

命題 7.13 最小化の整数計画問題の最適値を $z_{\mathrm{IP}}$ 、その LP 緩和の最適値を $z_{\mathrm{LP}}$ とすると $z_{\mathrm{LP}} \leq z_{\mathrm{IP}}$ である（最大化なら $z_{\mathrm{LP}} \geq z_{\mathrm{IP}}$ ）。LP 緩和の最適解が整数の制約を満たせば、それは整数計画問題の最適解である。

証明. 整数計画の実行可能解は LP 緩和の実行可能解なので $z_{\mathrm{LP}} \leq z_{\mathrm{IP}}$ 。LP 緩和の最適解 $x$ が整数なら、 $x$ は整数計画で実行可能で、その値 $z_{\mathrm{LP}}$ は $z_{\mathrm{IP}}$ 以下だから最適である。 $\square$

両者の差（または比）を整数性ギャップ (integrality gap) という。

例 7.14（ナップサック問題：投資案件の選択）予算 10（百万円）で、4 つの案件から実施するものを選ぶ。案件 $i$ の費用 $w_i$ と見込み利益 $v_i$ （百万円）は $(w_i, v_i) = (3, 12), (4, 9), (6, 13), (7, 9)$ である。案件 $i$ を選ぶとき $x_i = 1$ とすると

\text{maximize} \quad 12x_1 + 9x_2 + 13x_3 + 9x_4 \qquad \text{subject to} \quad 3x_1 + 4x_2 + 6x_3 + 7x_4 \leq 10, \quad x_i \in \lbrace 0, 1 \rbrace

となる（容量 $W$ の袋に重さ $w_i$ ・価値 $v_i$ の品物を詰める形なので 0-1 ナップサック問題, knapsack problem という）。16 通りを調べると最適解は案件 1, 3（費用 9、利益 25）だが、効率 $v_i/w_i = 4, 2.25, 2.17, 1.29$ の高い順に入るだけ選ぶ貪欲法は案件 1, 2 で利益 21 にとどまる。LP 緩和（ $0 \leq x_i \leq 1$ ）の最適解は次の命題 7.15 より $(1, 1, 1/2, 0)$ （値 $27.5$ ）で、 $x_3$ を切り捨てると利益 21、切り上げると実行不能である。

命題 7.15（ナップサック問題の LP 緩和） $v_i, w_i > 0$ とし、品物を $v_1/w_1 \geq v_2/w_2 \geq \cdots \geq v_n/w_n$ の順に並べ、 $w_1 + \cdots + w_n > W \geq 0$ とする。 $w_1 + \cdots + w_k > W$ となる最小の $k$ をとり、 $\bar{x}_i = 1$ （ $i < k$ ）, $\bar{x}_k = \bigl(W - \sum_{i < k} w_i\bigr)/w_k$ , $\bar{x}_i = 0$ （ $i > k$ ）とおく。このとき $\bar{x}$ は LP 緩和「 $\sum_i w_ix_i \leq W$ , $0 \leq x_i \leq 1$ のもとで $\sum_i v_ix_i$ を最大化」の最適解である。

証明. $k$ の選び方から $0 \leq \bar{x}_k < 1$ , $\sum_i w_i\bar{x}_i = W$ で、 $\bar{x}$ は実行可能である。 $r = v_k/w_k > 0$ とおくと、 $i < k$ では $v_i - rw_i \geq 0$ 、 $i \geq k$ では $v_i - rw_i \leq 0$ なので、任意の実行可能解 $x$ について（ $0 \leq x_i \leq 1$ と $\sum_i w_ix_i \leq W$ より）

\sum_i v_ix_i = \sum_i (v_i - rw_i)x_i + r\sum_i w_ix_i \leq \sum_{i < k}(v_i - rw_i) + rW = \sum_{i < k} v_i + r\Bigl(W - \sum_{i < k} w_i\Bigr) = \sum_i v_i\bar{x}_i

である。 $\square$

例 7.16（施設配置）倉庫の候補地 $j$ （建設費 $f_j$ ）と顧客 $i$ （倉庫 $j$ からの配送費 $c_{ij}$ ）がある。倉庫 $j$ を建てるとき $y_j = 1$ 、顧客 $i$ を倉庫 $j$ に割り当てるとき $x_{ij} = 1$ とすると

\text{minimize} \quad \sum_{j} f_jy_j + \sum_{i, j} c_{ij}x_{ij} \qquad \text{subject to} \quad \sum_{j} x_{ij} = 1 \ (\forall i), \quad x_{ij} \leq y_j \ (\forall i, j), \quad x_{ij}, y_j \in \lbrace 0, 1 \rbrace

となる。制約 $x_{ij} \leq y_j$ を $\sum_i x_{ij} \leq my_j$ （ $m$ は顧客数）にまとめても 0-1 解は変わらないが、LP 緩和は弱くなる。倉庫 2 つ（ $f_1 = f_2 = 10$ ）、顧客 2 人（ $c_{11} = c_{22} = 0$ , $c_{12} = c_{21} = 20$ ）では、整数計画の最適値は両方を建てる $20$ で、元の形の LP 緩和も $20$ だが（ $y_1 \geq x_{11} = 1 - x_{12}$ より $10y_1 + 20x_{12} \geq 10$ 、同様に $10y_2 + 20x_{21} \geq 10$ ）、まとめた形では $y = (1/2, 1/2)$ , $x_{11} = x_{22} = 1$ が値 $10$ を与え（ $10(y_1 + y_2) \geq 5\sum_{i, j}x_{ij} = 10$ より最適）、下界が半分になる。

例 7.17（勤務シフト）1 日を 6 つの時間帯に分け、時間帯 $t$ には $d_t$ 人以上が必要とする。勤務は連続する 3 つの時間帯を担当し、開始は時間帯 1〜4 のいずれかとする。時間帯 $s$ に始まる勤務の人数を $x_s$ とすると、総人数の最小化は

\text{minimize} \quad x_1 + x_2 + x_3 + x_4 \qquad \text{subject to} \quad Ax \geq d, \quad x \in \mathbb{Z}_{\geq 0}^4, \qquad A = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 \end{pmatrix}

である（ $A$ の $(t, s)$ 成分は、勤務 $s$ が時間帯 $t$ を担当するとき $1$ ）。 $d = (2, 4, 5, 6, 3, 2)$ では、LP 緩和を単体法で解くと最適値 $8$ の整数解（たとえば $(2, 3, 0, 3)$ ）が得られ（計算機で確かめた）、時間帯 1 と 4 の制約の和 $x_1 + x_2 + x_3 + x_4 \geq 8$ より整数計画の最適解でもある。これは偶然ではない（定理 7.19、問題 7.3）。

定義 7.18（全単模行列）整数行列 $A$ のすべての正方部分行列（行と列を同じ数だけ選んで作る行列）の行列式が $0, 1, -1$ のいずれかであるとき、 $A$ は全単模 (totally unimodular) であるという。特に $A$ の成分は $0, \pm 1$ のいずれかである。

定理 7.19（全単模性と整数性） $A \in \mathbb{R}^{m \times n}$ を全単模行列、 $b \in \mathbb{Z}^m$ とする。

$P = \lbrace x \mid Ax = b,\ x \geq 0 \rbrace$ の頂点はすべて整数ベクトルである。

$Q = \lbrace x \mid Ax \leq b,\ x \geq 0 \rbrace$ の頂点もすべて整数ベクトルである。

したがって、 $P$ や $Q$ の上で一次関数を最小化（最大化）する線形計画問題が最適解をもてば整数の最適解があり、それは整数の制約を加えた整数計画問題の最適解でもある。

証明. (1) $x$ を $P$ の頂点、 $S = \operatorname{supp} x$ とする（ $S = \emptyset$ なら $x = 0$ ）。第3章定理 3.8 より列 $a_j$ （ $j \in S$ ）は一次独立なので、これらの列からなる行列の $\lvert S \rvert$ 個の行を選んで、 $A$ の正則な正方部分行列 $M$ を作れる。 $j \notin S$ では $x_j = 0$ だから $Mx_S = b'$ （ $b'$ は $b$ の対応する成分）で、 $\det M = \pm 1$ とクラメルの公式（02-linear-algebra 第4章定理 4.30）より $x_S$ は整数ベクトルである。(2) $x \mapsto (x, b - Ax)$ は $Q$ から $P' = \lbrace (x, s) \mid Ax + s = b,\ x, s \geq 0 \rbrace$ への全単射で、逆写像とともに凸結合を保つので、頂点を頂点に写す。 $[A\ I]$ も全単模なので（正方部分行列の $I$ から来た列は選んだ行の中に $1$ を高々 1 つしかもたず、その列での余因子展開を繰り返すと、行列式は $0$ , $\pm 1$ か $A$ の正方部分行列の行列式の $\pm 1$ 倍になる）、(1) を $P'$ に使えばよい。最後の主張は第3章定理 3.11（ $Q$ は (2) の変換で標準形に直す）と命題 7.13 による。 $\square$

逆に、整数行列 $A$ について、すべての整数ベクトル $b$ で $Q$ の頂点が整数なら $A$ は全単模である（ホフマン–クラスカル, 1956 年。Schrijver, Theory of Linear and Integer Programming を参照）。全単模性は次の形で確かめることが多い。

命題 7.20 各列に $+1$ が高々 1 個、 $-1$ が高々 1 個あり、他の成分が $0$ である行列は全単模である。

証明. 正方部分行列 $B$ の大きさについての帰納法による（ $B$ も同じ性質をもつ）。大きさ 1 なら成分は $0, \pm 1$ である。 $B$ に零ベクトルの列があれば $\det B = 0$ 。成分が 1 つだけの列があれば、その列で展開して大きさが 1 小さい部分行列の行列式の $\pm 1$ 倍になる。どちらでもなければ、すべての列が $+1$ と $-1$ を 1 つずつもつので、 $B$ のすべての行を足すと $0$ になり $\det B = 0$ 。 $\square$

この命題から次の行列が全単模とわかる。(i) 有向グラフの接続行列（行が頂点、列が辺で、辺 $(u, v)$ の列は $u$ の行が $+1$ 、 $v$ の行が $-1$ ）。第1章例 1.7 の最短路問題の制約はこの形なので、 $x_e \geq 0$ にゆるめた線形計画問題は、 $t$ に到達できれば整数の最適な頂点をもつ（ $c_e \geq 0$ より最適解がある）。(ii) 輸送問題・割当問題の制約行列（第3章 3.9 節）。店舗の行に $-1$ を掛ければ（行列式は符号しか変わらない）命題 7.20 の形になる。(iii) 例 7.17 のように各列の $1$ が連続した行に並ぶ $0$ - $1$ 行列（問題 7.3）。一方、三角形の頂点と辺の行列は、行が $(1, 1, 0), (1, 0, 1), (0, 1, 1)$ で行列式が $-2$ であり、全単模でない。実際、頂点を共有しない辺の組（マッチング）の辺数の最大化で、整数解の最適値は $1$ だが、LP 緩和はすべての変数を $1/2$ として $3/2$ を与える。

7.5 分枝限定法と切除平面法

分枝限定法 (branch and bound。Land–Doig, 1960 年) は、変数の範囲で問題を分け（分枝）、LP 緩和の値で見込みのない場合を捨てる（限定）。最大化の整数計画問題で、各変数に整数の上下限 $l_j \leq x_j \leq u_j$ が制約として含まれるとする。それまでに見つけた最良の整数解を暫定解、その値を $z^{\ast}$ （はじめは $-\infty$ ）とし、部分問題（節点）の集合を元の問題だけから始めて、空になるまで節点を 1 つ取り出して LP 緩和を解き、次のように処理する。

実行不能なら捨てる。
最適値が $z^{\ast}$ 以下なら捨てる（この節点の整数解は暫定解より良くならない）。
最適解 $\bar{x}$ が整数なら、 $\bar{x}$ を新しい暫定解として捨てる（2 に当たらないので $z^{\ast}$ より良い）。
それ以外なら、値が整数でない $x_j$ を 1 つ選び、制約 $x_j \leq \lfloor \bar{x}_j \rfloor$ を加えた節点と $x_j \geq \lceil \bar{x}_j \rceil$ を加えた節点を作る。

命題 7.21（分枝限定法の正しさ）上の設定で整数計画問題が実行可能ならば、分枝限定法は（節点をどの順に取り出しても）有限回で終了し、終了時の暫定解は最適解である。

証明. 有限性：手順 4 では、その節点での上下限 $l_j, u_j$ について $l_j < \bar{x}_j < u_j$ で $\bar{x}_j$ は整数でないから、 $l_j \leq \lfloor \bar{x}_j \rfloor \leq u_j - 1$ , $u_j \geq \lceil \bar{x}_j \rceil \geq l_j + 1$ であり、どちらの子でも $\sum_j (u_j - l_j)$ （ $\geq 0$ ）が 1 以上減る。よって木の深さは元の問題の $\sum_j (u_j - l_j)$ 以下で、節点は有限個である。正しさ：最適解 $x^{\ast}$ を 1 つとり、「暫定解が最適でない間は、 $x^{\ast}$ を含む節点が未処理の集合にある」ことを示す。初めは根が $x^{\ast}$ を含む。 $x^{\ast}$ を含む節点を処理するとき、その LP 緩和の最適値は $x^{\ast}$ の値以上なので、1 は起こらない。2 なら $z^{\ast}$ は $x^{\ast}$ の値以上で暫定解は最適である。3 なら $\bar{x}$ の値は $x^{\ast}$ の値以上で、最適解 $\bar{x}$ が暫定解になる。4 なら $x^{\ast}_j$ は整数なので $x^{\ast}$ はどちらかの子に含まれる。終了時には未処理の節点がないので、暫定解は最適である。 $\square$

例 7.22（例 7.14 を分枝限定法で解く）各節点の LP 緩和は、値を固定した変数を除いた品物と残りの予算についての同じ形の問題なので、命題 7.15 で計算できる（固定した品物の費用が予算を超えれば実行不能、残りの品物がすべて入れば全部 $1$ ）。新しく作った節点から先に、 $x_j = 1$ の節点を先に調べる（深さ優先）と、次の木ができる。

根          x = (1, 1, 1/2, 0)    上界 27.5    → x3 で分枝
├ x3 = 1    x = (1, 1/4, 1, 0)    上界 27.25   → x2 で分枝
│ ├ x2 = 1  x = (0, 1, 1, 0)      値 22 の整数解 → 暫定解 22
│ └ x2 = 0  x = (1, 0, 1, 1/7)    上界 184/7 ≈ 26.29 → x4 で分枝
│   ├ x4 = 1  実行不能（費用 6 + 7 > 10）
│   └ x4 = 0  x = (1, 0, 1, 0)    値 25 の整数解 → 暫定解を 25 に更新
└ x3 = 0    x = (1, 1, 0, 3/7)    上界 174/7 ≈ 24.86 < 25 → 限定により打ち切り

たとえば節点「 $x_3 = 1$ 」では、残りの予算 4 で案件 1 を入れ、残り 1 で案件 2 を $1/4$ 入れて、上界 $13 + 12 + 9/4 = 27.25$ を得る（各節点は計算機でも確かめた）。打ち切りの三つの理由がすべて現れている。

LP 緩和そのものを強めることもできる。すべての整数解を満たし、LP 緩和の分数解を満たさない不等式を切除平面 (cutting plane) という（Gomory, 1958 年）。次の丸めは、切除平面を作る基本的な方法である。

命題 7.23（Chvátal–Gomory の丸め）実行可能解がすべて非負の整数ベクトルで、すべての実行可能解が $\sum_j a_jx_j \leq \beta$ を満たすならば、すべての実行可能解は $\sum_j \lfloor a_j \rfloor x_j \leq \lfloor \beta \rfloor$ も満たす。

証明. $x \geq 0$ より $\sum_j \lfloor a_j \rfloor x_j \leq \sum_j a_jx_j \leq \beta$ で、左辺は整数だから $\lfloor \beta \rfloor$ 以下である。 $\square$

例 7.24（切除平面）例 7.14 で、予算の制約の $1/4$ 倍と $x_1 \leq 1$ の $1/4$ 倍を足すと $x_1 + x_2 + \frac{3}{2}x_3 + \frac{7}{4}x_4 \leq \frac{11}{4}$ で、命題 7.23 より $x_1 + x_2 + x_3 + x_4 \leq 2$ を得る。LP 緩和の解 $(1, 1, 1/2, 0)$ はこれを破る。この不等式を加えた LP 緩和では

12x_1 + 9x_2 + 13x_3 + 9x_4 \leq 12(x_1 + x_2 + x_3 + x_4) + x_3 \leq 24 + 1 = 25

で、等号は $x = (1, 0, 1, 0)$ のときに限るので、分枝せずに最適性がわかる（命題 7.13）。実際のソルバーは両者を組み合わせた分枝カット法 (branch and cut) を使う。

ヒント

実務では 整数計画ソルバーは、暫定解の値と、未処理の節点の LP 緩和から得られる最適値の限界との相対的な差（ギャップ）を報告し、それが 1% 以下になったら打ち切る、という使い方が多い。速く解けるかは定式化で大きく変わる（例 7.16）。「十分大きな定数 $M$ 」で条件を表す定式化（big-M）で $M$ を必要以上に大きくすると、緩和が弱くなり数値誤差も起きやすい。

7.6 最短路とダイクストラ法

この節以降、 $G = (V, E)$ はグラフを表す（7.1 節の $G$ や期待値の $E$ とは関係ない）。有向グラフの各辺 $(u, v)$ に重み $c(u, v)$ があり、始点 $s$ が与えられているとする。道（同じ頂点を二度通らない辺の列）の長さを辺の重みの和とし、 $s$ から $v$ への道の長さの最小値を $\operatorname{dist}(v)$ （道がなければ $\infty$ ）と書く。無向グラフは各辺を両向きの有向辺 2 本とみなす。

ダイクストラ法（Dijkstra, 1959 年）は、各頂点に暫定的な距離 $d(v)$ をもたせ、確定した頂点の集合 $S$ を 1 つずつ増やしていく。

$d(s) = 0$ 、 $v \neq s$ では $d(v) = \infty$ 、 $S = \emptyset$ とする。
$S \neq V$ である間、 $S$ に属さない頂点のうち $d(u)$ が最小の $u$ を $S$ に加え、 $u$ から出る各辺 $(u, v)$ について $d(u) + c(u, v) < d(v)$ なら $d(v) = d(u) + c(u, v)$ と更新する（ $v$ の直前の頂点を $u$ と記録する）。

定理 7.25（ダイクストラ法の正しさ）すべての辺の重みが非負ならば、頂点 $u$ が $S$ に加えられる時点で $d(u) = \operatorname{dist}(u)$ である。したがって終了時にはすべての頂点で $d(v) = \operatorname{dist}(v)$ であり、記録した直前の頂点をたどれば最短路が得られる。

証明. まず、常に $d(v) \geq \operatorname{dist}(v)$ である。 $d(v) < \infty$ なら $d(v)$ は $s$ から $v$ へのある歩道（頂点の重複を許す辺の列）の長さで、重みが非負なので閉路を除いても長さは増えず、ある道の長さ以上だからである。

$d(u) \neq \operatorname{dist}(u)$ のまま $S$ に加えられる最初の頂点を $u$ とすると、 $d(u) > \operatorname{dist}(u)$ だから $\operatorname{dist}(u) < \infty$ , $u \neq s$ である。 $s$ から $u$ への最短路 $P$ をとる。 $u$ を選んだ時点で $s \in S$ , $u \notin S$ なので、 $P$ 上で最初に現れる $S$ の外の頂点 $y$ と、その直前の頂点 $x \in S$ がある。 $x$ は $u$ より前に加えられたので $d(x) = \operatorname{dist}(x)$ で、そのとき辺 $(x, y)$ を調べたから（その後 $d(y)$ は増えない）

d(y) \leq \operatorname{dist}(x) + c(x, y) \leq (P \text{ の } s \text{ から } y \text{ までの長さ}) \leq (P \text{ の長さ}) = \operatorname{dist}(u) < d(u)

である。2 番目の不等号は $P$ の $s$ から $x$ までの長さが $\operatorname{dist}(x)$ 以上であることに、3 番目の不等号は $P$ の $y$ から $u$ までの長さが非負であることによる（重みの非負性はここで使う）。一方、 $u$ は $S$ の外で $d$ が最小だから $d(u) \leq d(y)$ であり、矛盾する。最後に、 $v$ の直前の頂点として記録された $u$ は $v$ より先に $S$ に加えられ、 $d(v) = d(u) + c(u, v)$ を満たすので、直前の頂点を $s$ までたどると長さ $d(v)$ の道が得られる。 $\square$

例 7.26（負の重みがあると誤る）辺 $s \to a$ （重み 2）、 $s \to b$ （3）、 $b \to a$ （ $-2$ ）、 $a \to t$ （2）では、ダイクストラ法は $a$ を $d(a) = 2$ で確定して $d(t) = 4$ とする。次に $b$ を加えると $d(a)$ は $1$ に下がるが、 $a$ から出る辺は調べ直されず、 $t$ は $d(t) = 4$ で確定する。実際は $s \to b \to a \to t$ の長さ $3$ が最短である（証明の $u = a$ , $y = b$ で、 $y$ から $u$ までの長さ $-2$ が負なので 3 番目の不等号が崩れる）。負の閉路がなければ、ベルマン–フォード法が $O(\lvert V \rvert\lvert E \rvert)$ 時間で最短路を求める。

例 7.27（道路網）拠点 $s, a, b, c, d, t$ を結ぶ道路（両方向に通れる）の所要時間が次のとおりとする（辺 $\lbrace u, v \rbrace$ を $uv$ と書く）。

道路	$sa$	$sb$	$sc$	$ab$	$ac$	$bd$	$cd$	$ct$	$dt$
所要時間	4	2	7	1	5	9	3	6	8

$s$ からのダイクストラ法は $s$ （0）, $b$ （2）, $a$ （3）, $c$ （7）, $d$ （10）, $t$ （13）の順に頂点を確定し、その途中で $d(a)$ は $4$ から $b$ 経由の $3$ に、 $d(d)$ は $11$ から $c$ 経由の $10$ に更新される。最短路は $s \to b \to a$ （3）、 $s \to c \to d$ （10）、 $s \to c \to t$ （13）などである。

答えが正しいことは、アルゴリズムを信用しなくても確かめられる。

命題 7.28（最短路の証明書）重みは任意の実数でよい。 $p\colon V \to \mathbb{R}$ が $p(s) = 0$ と、すべての辺 $(u, v)$ について $p(v) \leq p(u) + c(u, v)$ を満たすならば、 $s$ から $v$ へのどの道の長さも $p(v)$ 以上である。したがって長さ $p(v)$ の道があれば、それは最短路である。

証明. 道 $s = v_0, v_1, \dots, v_k = v$ について $\sum_{i=1}^{k} c(v_{i-1}, v_i) \geq \sum_{i=1}^{k}\bigl(p(v_i) - p(v_{i-1})\bigr) = p(v) - p(s) = p(v)$ 。 $\square$

重みが非負なら、ダイクストラ法の最終的な $d$ は（ $s$ から到達できる頂点の上で）この条件を満たす（辺 $(u, v)$ を調べた後、 $d(u)$ は変わらず $d(v)$ は増えない）。 $y = -p$ は 7.4 節 (i) の線形計画の双対問題（第3章定義 3.24）の実行可能解であり、命題 7.28 は弱双対定理（第3章定理 3.25）にほかならない。

7.7 最小全域木と貪欲法

すべての拠点を通信回線で結びたい。回線を引ける区間とその費用が与えられたとき、すべての拠点がつながる回線の組で費用の合計が最小のものを求める。

連結な無向グラフ $G = (V, E)$ と辺の重み $w(e)$ を考える。閉路をもたない連結なグラフを木 (tree)、すべての頂点を結ぶ木をなす $E$ の部分集合を全域木 (spanning tree)、重みの和が最小の全域木を最小全域木 (minimum spanning tree) という（重みが正なら、すべての頂点をつなぐ辺の組で重み最小のものは全域木である。閉路の辺を 1 本除けるからである）。次の基本的な事実を使う（証明は Korte–Vygen, Combinatorial Optimization などを参照）：頂点数 $n$ の木の辺は $n - 1$ 本で、どの 2 頂点もただ一つの道で結ばれる。全域木 $T$ に $T$ の外の辺 $e$ を加えると $e$ を含む閉路がちょうど 1 つでき、その閉路の任意の辺を除くと再び全域木になる。

頂点の集合 $S$ （ $\emptyset \neq S \neq V$ ）について、端点の一方が $S$ 、他方が $V \setminus S$ にある辺を、 $S$ をまたぐ辺という。

補題 7.29（カット性質, cut property） $F$ をある最小全域木に含まれる辺の集合、 $S$ を $F$ のどの辺もまたがない頂点の集合（ $\emptyset \neq S \neq V$ ）とし、 $e$ を $S$ をまたぐ辺のうち重みが最小のものとする。このとき $F \cup \lbrace e \rbrace$ もある最小全域木に含まれる。

証明. $F \subset T$ となる最小全域木 $T$ をとる。 $e \in T$ なら終わり。そうでなければ $T \cup \lbrace e \rbrace$ は $e$ を含むただ一つの閉路 $Z$ をもつ。 $Z$ から $e$ を除いた部分は、 $S$ の点と $V \setminus S$ の点を結ぶ道なので、 $S$ をまたぐ辺 $f \neq e$ を含む。 $f \in T$ で、 $F$ の辺は $S$ をまたがないので $f \notin F$ 。 $T' = (T \cup \lbrace e \rbrace) \setminus \lbrace f \rbrace$ は全域木で、 $e$ の最小性より $w(T') = w(T) + w(e) - w(f) \leq w(T)$ 。よって $T'$ は $F \cup \lbrace e \rbrace$ を含む最小全域木である。 $\square$

定理 7.30（クラスカル法, Kruskal, 1956 年）連結な無向グラフの辺を重みの小さい順に $e_1, e_2, \dots, e_M$ と並べ、 $F = \emptyset$ から始めて、 $i = 1, 2, \dots, M$ の順に「 $F \cup \lbrace e_i \rbrace$ が閉路をもたなければ $e_i$ を $F$ に加える」。終了時の $F$ は最小全域木である。

証明. 「 $F$ はある最小全域木に含まれる」が保たれることを示す。初めは正しい。 $e_i = \lbrace u, v \rbrace$ を加えるとき、 $u$ と $v$ はグラフ $(V, F)$ の異なる連結成分にある。 $u$ の連結成分の頂点集合を $S$ とすると、 $F$ の辺は $S$ をまたがず、 $e_i$ は $S$ をまたぐ。 $j < i$ の $e_j$ は、 $F$ に加えられたか、両端が同じ連結成分にあって捨てられたか（連結成分は合併するだけなので、両端は今も同じ成分にある）のどちらかで、いずれにしても $S$ をまたがない。よって $e_i$ は $S$ をまたぐ辺のうち重みが最小で、補題 7.29 より $F \cup \lbrace e_i \rbrace$ もある最小全域木に含まれる。終了時、 $(V, F)$ は連結である（異なる連結成分を結ぶ辺が $G$ にあれば、それを調べた時点でも両端は異なる成分にあり、加えられていたはずである）。よって $F$ は全域木で、ある最小全域木 $T$ に含まれ、辺の数がともに $n - 1$ なので $F = T$ 。 $\square$

例 7.31 例 7.27 の道路網で、所要時間と同じ費用で回線を引けるとする。重みの小さい順に $ab$ , $sb$ , $cd$ を採用し、 $sa$ は閉路を作るので捨て、 $ac$ , $ct$ を採用すると、費用 $17$ の最小全域木になる。例 7.27 の最短路をつないだ木（ $sb$ , $ab$ , $sc$ , $cd$ , $ct$ ）は費用 $19$ で、最小全域木の上の $s$ から $t$ への道 $s \to b \to a \to c \to t$ は長さ $14$ で最短（13）ではない。

現在の木をまたぐ最小の辺を加えて 1 つの頂点から木を育てるプリム法（Prim, 1957 年）も、補題 7.29 から正しい。貪欲法がここで最適になるのは、閉路をもたない辺の集合がマトロイドという構造をもつためである（Korte–Vygen を参照。例 7.14 のように、一般には最適と限らない）。

7.8 動的計画法

問題を小さい部分問題に分け、部分問題の最適値の表を小さい順に埋めていく方法を動的計画法 (dynamic programming) という（ベルマンが 1950 年代に体系化した）。最適解の一部分が部分問題の最適解になっていること（最適性の原理）が鍵である。

定理 7.32（ナップサック問題の動的計画法）重み $w_i$ と容量 $W$ は非負の整数とし、価値 $v_i$ は実数とする。 $0 \leq i \leq n$ , $0 \leq r \leq W$ について、品物 $1, \dots, i$ だけを使い、重さの合計が $r$ 以下となる選び方の価値の最大値を $V_i(r)$ とする。このとき $V_0(r) = 0$ であり、 $i \geq 1$ では
$V_i(r) = \begin{cases} V_{i-1}(r) & (w_i > r) \\ \max\bigl(V_{i-1}(r),\ V_{i-1}(r - w_i) + v_i\bigr) & (w_i \leq r) \end{cases}$
が成り立つ。最適値 $V_n(W)$ は、表 $V_i(r)$ を $O(nW)$ 回の演算で埋めて求められる。

証明. 品物 $1, \dots, i$ の選び方で重さの合計が $r$ 以下のものを、品物 $i$ を選ぶかどうかで分ける。選ばないものは品物 $1, \dots, i - 1$ の重さ $r$ 以下の選び方そのものなので、価値の最大値は $V_{i-1}(r)$ である。選ぶもの（ $w_i \leq r$ のときだけある）は、残りが品物 $1, \dots, i - 1$ の重さ $r - w_i$ 以下の選び方と一対一に対応するので、価値の最大値は $V_{i-1}(r - w_i) + v_i$ である。全体の最大値は両者の大きいほうである。表の欄は $(n + 1)(W + 1)$ 個で、各欄は $O(1)$ 回の演算で埋まる。 $\square$

例 7.33 例 7.14（ $W = 10$ ）の表は次のとおりである（計算機でも確かめた）。

	3	4	5	6	7	8	9	10
$V_0$	0	0	0	0	0	0	0	0
$V_1$ （ $w_1 = 3$ , $v_1 = 12$ ）	12	12	12	12	12	12	12	12
$V_2$ （ $w_2 = 4$ , $v_2 = 9$ ）	12	12	12	12	21	21	21	21
$V_3$ （ $w_3 = 6$ , $v_3 = 13$ ）	12	12	12	13	21	21	25	25
$V_4$ （ $w_4 = 7$ , $v_4 = 9$ ）	12	12	12	13	21	21	25	25

たとえば $V_3(9) = \max(V_2(9), V_2(3) + 13) = 25$ 。表を逆にたどると、 $V_4(10) = V_3(10)$ より品物 4 は選ばず、 $V_3(10) \neq V_2(10)$ より品物 3 を選んで $r = 4$ に移り、 $V_2(4) = V_1(4) \neq V_0(4)$ より品物 2 は選ばず品物 1 を選ぶ。最適解は品物 1, 3 で、例 7.22 と一致する。

計算時間 $O(nW)$ は $n$ と $W$ の多項式だが、 $W$ は 2 進法で約 $\log_2 W$ 桁で書けるので、入力の大きさの多項式ではない。このように入力に現れる数値の値の多項式で抑えられる計算時間を擬多項式時間 (pseudo-polynomial time) という。 $W$ が $10^6$ 程度までなら動的計画法は非常に実用的だが、 $10^{12}$ 程度になると表が大きすぎる。

7.9 計算量と NP 困難

アルゴリズムの速さは、入力の大きさ（入力を 2 進法で書いたときのビット数）に対する最悪の場合の計算時間で測り、多項式で抑えられるとき多項式時間という（25-cryptography-coding 第1章定義 1.2 と同じ考え方）。線形計画（第3章 3.5 節の楕円体法・内点法）、最短路、最小全域木は多項式時間で解ける。

定義 7.34（P, NP, NP 完全, NP 困難）答えが「はい」か「いいえ」の問題を判定問題という。

多項式時間のアルゴリズムで解ける判定問題全体を P という。

多項式時間で動く検証のアルゴリズムがあって、答えが「はい」の入力にはそれが受け入れる証拠 (certificate)（長さは入力の大きさの多項式以下）があり、「いいえ」の入力ではどんな証拠も受け入れられない、という判定問題全体を NP という。

判定問題 $A$ の入力を、答えを変えずに判定問題 $B$ の入力に多項式時間で変換できるとき、 $A$ は $B$ に多項式時間帰着されるという。NP に属し、NP のすべての問題が多項式時間帰着される判定問題を NP 完全 (NP-complete) という。

ある NP 完全な問題が、問題 $B$ （最適化問題でもよい）を解く手続きを多項式回呼び出す多項式時間のアルゴリズムで解けるとき、 $B$ を NP 困難 (NP-hard) という。

ナップサック問題の判定版「価値の合計が $K$ 以上で重さの合計が $W$ 以下の選び方はあるか」は、選び方が証拠になるので NP に属する。P は NP に含まれ、NP 困難な問題が多項式時間で解ければ NP のすべての問題が多項式時間で解ける（定義 7.34 の 3・4）。最初の NP 完全問題は論理式の充足可能性問題で（クック, 1971 年。レビンも独立に示した）、カープ（1972 年）は 0-1 整数計画やナップサック問題（次の例の部分和問題）など 21 の問題の NP 完全性を示した。巡回セールスマン問題や施設配置問題も NP 困難である。

P = NP かどうかは未解決である。 P ≠ NP と予想されており、クレイ数学研究所が 2000 年に選んだミレニアム懸賞問題の一つである。したがって「NP 困難な問題には多項式時間のアルゴリズムがない」は証明された事実ではなく、「P ≠ NP ならば、ない」が正確な言い方である。

例 7.35（非凸な 4 次多項式の最小化）正の整数 $a_1, \dots, a_n$ , $s$ について「和が $s$ になる $a_i$ の選び方はあるか」を問う部分和問題は NP 完全である。これに対し

p(x) = \Bigl(\sum_{i=1}^{n} a_ix_i - s\Bigr)^2 + \sum_{i=1}^{n} x_i^2(1 - x_i)^2 \qquad (x \in \mathbb{R}^n)

とおくと $p \geq 0$ で、 $p(x) = 0$ は「各 $x_i \in \lbrace 0, 1 \rbrace$ かつ $\sum_i a_ix_i = s$ 」と同値である。 $p$ は強圧的なので最小値をもち（第1章定理 1.11）、最小値が $0$ であることと部分和問題の答えが「はい」であることは同値になる。 $p$ の係数は入力から多項式時間で計算できるので、4 次多項式の大域最小値が $0$ かどうかを判定する問題は NP 困難である。

注意

「NP 困難だから解けない」は誤りである。NP 困難は、P ≠ NP ならばすべての入力に対して多項式時間で最適解を出すアルゴリズムはない、という最悪の場合の主張である。実務の問題では、分枝カット法で大規模なものまで最適解（あるいは最適値からの差を保証した解）が得られることも多い。規模と必要な精度に応じて、ソルバー・近似アルゴリズム・発見的解法を使い分ければよい。

最適解をあきらめる代わりに、質の保証された解を多項式時間で求めるのが近似アルゴリズム (approximation algorithm) である。最大化問題で、常に最適値の $\alpha$ 倍以上（最小化問題なら $\alpha$ 倍以下）の値の実行可能解を多項式時間で出すアルゴリズムを $\alpha$ -近似アルゴリズムという。

定理 7.36（ナップサック問題の $1/2$ -近似） $v_i, w_i > 0$ 、各品物の重さは $W$ 以下で $\sum_i w_i > W$ とし、命題 7.15 のように並べたときの $k$ について、 $A = \lbrace 1, \dots, k - 1 \rbrace$ と $\lbrace k \rbrace$ のうち価値の合計が大きいほうを選ぶ。その価値は最適値の $1/2$ 以上であり、計算時間は並べ替えの $O(n\log n)$ である。

証明. $k$ の定義より $A$ の重さは $W$ 以下で、仮定より $w_k \leq W$ なので、どちらも実行可能である。最適値を $z^{\ast}$ とすると、命題 7.13 と 7.15、および $W - \sum_{i < k} w_i < w_k$ より

z^{\ast} \leq \sum_{i < k} v_i + v_k\frac{W - \sum_{i < k} w_i}{w_k} < \sum_{i < k} v_i + v_k \leq 2\max\Bigl(\sum_{i < k} v_i,\ v_k\Bigr)

である。 $\square$

例 7.14 では $\lbrace 1, 2 \rbrace$ （価値 21）と $\lbrace 3 \rbrace$ （13）から 21 を選び、 $21 \geq 25/2$ である。 $\lbrace k \rbrace$ との比較を省くと比はいくらでも悪くなりうる（問題 7.6）。近似のしやすさは問題によって大きく違う。たとえば一般の距離の巡回セールスマン問題には、P ≠ NP なら定数倍の近似アルゴリズムすらない（サーニ–ゴンザレス, 1976 年）。

まとめ

確率的勾配降下法は、不偏な確率的勾配、 $E[\lVert g \rVert^2] \leq G^2$ 、 $\lVert x_0 - x^{\ast} \rVert \leq R$ のもとで、ステップ幅 $R/(G\sqrt{k})$ の平均反復点について $E[f(\bar{x}_k)] - f(x^{\ast}) \leq RG/\sqrt{k}$ を満たす（鍵は $x_t$ と $\xi_t$ の独立性）。強凸なら $O(1/k)$ 。
ミニバッチは分散を $1/b$ にするが、勾配の計算回数は減らさない。Adam には凸問題でも収束しない例がある。
非凸問題では、狭義の鞍点に収束する初期点は測度 $0$ だが、停滞は起こり、大域最小は一般に難しい。
LP 緩和は最適値の限界を与え、制約行列が全単模なら頂点は整数である。分枝限定法は有限回で最適解を返し、切除平面は緩和を強める。
重みが非負ならダイクストラ法は正しく、ポテンシャルは最短性の証明書になる。カット性質から、クラスカル法は最小全域木を与える。
ナップサック問題は動的計画法で擬多項式時間で解けるが、判定版は NP 完全で、P = NP かどうかは未解決である。

演習問題

問題 7.1 ★ 定理 7.4 の設定で $R = 10$ , $G = 2$ とする。(1) 誤差の期待値を $0.01$ 以下にすることを定理 7.4 で保証するには、何回の反復が必要か。そのときのステップ幅も求めよ。(2) 確率的勾配が $\lVert \bar{g}(x) \rVert \leq 1$ , $\sigma^2(x) \leq 3$ （命題 7.7 の記号）を満たすとする（このとき $G^2 = 4$ ととれる）。大きさ $b = 10$ のミニバッチを使うと、同じ保証に必要な反復回数と、勾配の計算回数の合計はどうなるか。

解答

(1) $RG/\sqrt{k} \leq 0.01$ は $\sqrt{k} \geq 2000$ 、すなわち $k \geq 4 \times 10^6$ と同値である。ステップ幅は $\eta = R/(G\sqrt{k}) = 10/(2 \cdot 2000) = 0.0025$ 。

(2) 命題 7.7 より $E[\lVert g_B \rVert^2] \leq 1 + 3/10$ なので $G_{10}^2 = 1.3$ ととれ、 $k \geq R^2G_{10}^2/0.01^2 = 1.3 \times 10^6$ で反復回数は (1) の約 3 分の 1 になるが、勾配の計算回数は $1.3 \times 10^7$ で (1) の $3.25$ 倍に増える。10 個の勾配を並列に計算して 1 回の反復の時間がほぼ変わらない場合に限り、時間の短縮になる。

問題 7.2 ★★★ 定理 7.6 を証明せよ。（ヒント：(7.1) と第2章定理 2.22 の 2 から $E[D_{t+1}] \leq (1 - \mu\eta_t)E[D_t] - 2\eta_t\bigl(E[f(x_t)] - f(x^{\ast})\bigr) + \eta_t^2G^2$ を導き、 $t$ 倍して足す。）

解答

定理 7.4 の証明の記号を使う。(7.1) はステップ幅 $\eta_t$ でも同じく成り立つ。第2章定理 2.22 の 2（ $x = x_t$ , $y = x^{\ast}$ ）より $\langle \nabla f(x_t), x_t - x^{\ast} \rangle \geq f(x_t) - f(x^{\ast}) + \frac{\mu}{2}D_t$ で、補題 7.3 より $E[\langle g_t, x_t - x^{\ast} \rangle] = E[\langle \nabla f(x_t), x_t - x^{\ast} \rangle]$ だから、(7.1) の期待値をとるとヒントの不等式を得る。これを $E[f(x_t)] - f(x^{\ast})$ について解き、 $\frac{1}{2\eta_t} = \frac{\mu(t + 1)}{4}$ , $\frac{1 - \mu\eta_t}{2\eta_t} = \frac{\mu(t - 1)}{4}$ , $\frac{\eta_t}{2} = \frac{1}{\mu(t + 1)}$ を代入して $t$ 倍し、 $\frac{t}{t + 1} \leq 1$ を使うと

t\bigl(E[f(x_t)] - f(x^{\ast})\bigr) \leq \frac{\mu}{4}\bigl((t - 1)t\,E[D_t] - t(t + 1)E[D_{t+1}]\bigr) + \frac{G^2}{\mu}

$t = 1, \dots, k$ について足すと、右辺の括弧の中は打ち消し合って $0 \cdot E[D_1] - k(k + 1)E[D_{k+1}] \leq 0$ となるので、 $\sum_{t=1}^{k} t\bigl(E[f(x_t)] - f(x^{\ast})\bigr) \leq kG^2/\mu$ 。 $\tilde{x}_k$ は $x_1, \dots, x_k$ の重み $\frac{2t}{k(k + 1)}$ の凸結合だから $C$ に属し、イェンセンの不等式より実現値ごとに $f(\tilde{x}_k) \leq \frac{2}{k(k + 1)}\sum_t tf(x_t)$ 。期待値をとって $E[f(\tilde{x}_k)] - f(x^{\ast}) \leq \frac{2}{k(k + 1)} \cdot \frac{kG^2}{\mu} = \frac{2G^2}{\mu(k + 1)}$ 。重み $t$ のおかげで $E[D_1]$ の係数が $0$ になり、初期点からの距離が評価に現れない。

問題 7.3 ★★ (1) 各列の $1$ が連続した行に並び、他の成分が $0$ である $0$ - $1$ 行列は全単模であることを示せ（ヒント：正方部分行列の各行から、そのすぐ下の行を引く）。(2) 日をまたいで循環する勤務（例 7.17 で、時間帯 $s, s + 1, s + 2$ を担当する勤務を $s = 1, \dots, 6$ について考え、番号は 6 を法として読む）を許すと、制約行列が全単模でなくなることを、3 次の部分行列の行列式で示せ。

解答

(1) 大きさ $k$ の正方部分行列 $B$ をとる。選んだ行だけを見ても、 $B$ の各列の $1$ は連続した行に並ぶ。 $i = 1, 2, \dots, k - 1$ の順に、第 $i$ 行から（まだ変更していない）第 $i + 1$ 行を引く。この操作で行列式は変わらない。ある列の $1$ が第 $p$ 行から第 $q$ 行にあるとすると、操作後のその列は、第 $q$ 行が $1$ 、 $p \geq 2$ なら第 $p - 1$ 行が $-1$ で、他は $0$ である。よって操作後の行列は命題 7.20 の形で、行列式（ $= \det B$ ）は $0, \pm 1$ のいずれかである。

(2) 勤務 1 は時間帯 1, 2, 3 を、勤務 3 は 3, 4, 5 を、勤務 5 は 5, 6, 1 を担当する。時間帯 1, 3, 5 の行と勤務 1, 3, 5 の列からなる部分行列は、行が $(1, 0, 1)$ , $(1, 1, 0)$ , $(0, 1, 1)$ で、行列式は $1 \cdot (1 - 0) - 0 + 1 \cdot (1 - 0) = 2$ である（7.4 節の三角形の行列の列を並べ替えたもの）。

問題 7.4 ★ 有向グラフの辺と重みを $s \to a$ （6）、 $s \to b$ （2）、 $b \to a$ （3）、 $a \to c$ （1）、 $b \to c$ （7）、 $c \to t$ （2）、 $a \to t$ （5）とする。ダイクストラ法で $s$ から各頂点への最短距離と最短路を求め、命題 7.28 の条件を確かめて答えが正しいことを確認せよ。

解答

$s$ を加えて $d(a) = 6$ , $d(b) = 2$ 。 $b$ （2）を加えて $d(a) = \min(6, 2 + 3) = 5$ , $d(c) = 9$ 。 $a$ （5）を加えて $d(c) = \min(9, 5 + 1) = 6$ , $d(t) = 10$ 。 $c$ （6）を加えて $d(t) = \min(10, 6 + 2) = 8$ 。最後に $t$ （8）を加える。最短距離は $a$ が 5, $b$ が 2, $c$ が 6, $t$ が 8 で、 $t$ への最短路は $s \to b \to a \to c \to t$ である。

$p = d$ として 7 本の辺で $p(v) \leq p(u) + c(u, v)$ を確かめると、 $5 \leq 6$ , $2 \leq 2$ , $5 \leq 2 + 3$ , $6 \leq 5 + 1$ , $6 \leq 2 + 7$ , $8 \leq 6 + 2$ , $8 \leq 5 + 5$ ですべて成り立つ。各頂点に長さ $p(v)$ の道があるので、命題 7.28 よりそれらは最短である。

問題 7.5 ★★ 負の重みの辺を含む有向グラフの最短路を求めるために、ある実装は「すべての辺の重みに同じ定数 $M$ を足して非負にしてから、ダイクストラ法を使う」。辺 $s \to a$ （1）、 $a \to t$ （ $-2$ ）、 $s \to t$ （0）のグラフで、この実装（ $M = 2$ ）を試して誤りを説明せよ。また、頂点の関数 $h$ によって $c'(u, v) = c(u, v) + h(u) - h(v)$ と重みを変えるのは正しいことを示し、このグラフで $c' \geq 0$ となる $h$ を 1 つ挙げよ。

解答

重みは $s \to a$ （3）、 $a \to t$ （0）、 $s \to t$ （2）になり、ダイクストラ法は $d(t) = 2$ で $t$ を確定して $s \to t$ （元の長さ $0$ ）を答えるが、 $s \to a \to t$ の元の長さ $-1$ のほうが短い。定数を足すと道の長さは $M \times$ （辺の数）だけ増え、辺の多い道ほど不利になるからである。

一方、 $u$ から $v$ への道 $u = v_0, \dots, v_k = v$ では $h$ の項が打ち消し合って $\sum_i c'(v_{i-1}, v_i) = \sum_i c(v_{i-1}, v_i) + h(u) - h(v)$ となり、同じ両端の道の長さはすべて同じだけずれるので、最短路は変わらない。 $h(s) = 0$ , $h(a) = 1$ , $h(t) = -1$ （ $s$ からの真の距離）とすると $c'(s, a) = c'(a, t) = 0$ , $c'(s, t) = 1$ である。一般に $h$ が命題 7.28 の条件 $h(v) \leq h(u) + c(u, v)$ を満たせば $c' \geq 0$ で、そのような $h$ をベルマン–フォード法で求めてからダイクストラ法を使うのがジョンソンの方法（1977 年）である。

問題 7.6 ★ 容量 $W \geq 2$ のナップサックに、品物 1（重さ 1、価値 2）と品物 2（重さ $W$ 、価値 $W$ ）を詰める。価値と重さの比の大きい順に入る限り詰める貪欲法の値と最適値を求め、 $W$ を大きくすると比がいくらでも悪くなることを確かめよ。定理 7.36 の方法では何が得られるか。

解答

比は品物 1 が $2$ 、品物 2 が $1$ なので、貪欲法は品物 1 を入れ、残りの容量 $W - 1$ に品物 2 は入らず、値は $2$ 。2 つは同時に入らない（重さ $W + 1$ ）ので、最適解は品物 2 だけで値 $W$ であり、比 $2/W$ は $W \to \infty$ で $0$ に近づく。定理 7.36 の方法では $k = 2$ で、 $\lbrace 1 \rbrace$ （価値 2）と $\lbrace 2 \rbrace$ （価値 $W$ ）のよいほうの品物 2 が選ばれ、最適解が得られる。