共役勾配法（Conjugate Gradient Method）とは？

(画像は、Geminiで作成されたものです)

共役勾配法の概要​

共役勾配法（Conjugate Gradient Method：CG法） は、正定値対称行列を係数とする大規模な連立一次方程式を高速に解くための反復法です。機械学習や最適化の文脈では、目的関数を最小化するための強力なアルゴリズムとして知られています。

単純な勾配降下法（最急降下法）で最適化を行おうとすると、目的関数の等高線が楕円形に歪んでいる場合にジグザグと無駄な探索を繰り返し、収束が著しく遅くなる問題があります。ニュートン法を使えば少ないステップで最適解に到達できますが、パラメータ数が多い巨大なモデルでは、ヘッシアン（2階微分行列）の全成分の保持や逆行列の計算がメモリ・計算量の観点から完全に不可能になります。

CG法は、行列に対して「共役（互いに独立・非干渉）」という特別な直交性を持つ探索方向を次々と生成することで、一度探索した成分のロスを再発させることなく効率的に最適解へと向かいます。 理論上はパラメータ次元数以下の反復で厳密解に到達できるという素晴らしい性質を持っています。さらに最大の利点として、アルゴリズムの計算過程で必要になるのは「行列とベクトルの掛け算」の演算結果だけであり、巨大な行列の全成分や逆行列を直接メモリに展開・計算する必要が一切ありません。

最急降下法・ニュートン法との違い（探索のルール）​

各アルゴリズムが、現在の解 $x$ からどのように探索方向を決定するかを比較してみましょう。ここでは二次関数 $f(x) = \frac{1}{2}x^T A x - b^T x$ の最小化（方程式 $Ax = b$ の解決）を考えます。

最急降下法 (Steepest Descent)​

常に現在位置の最も傾きが急な方向（マイナスの勾配方向）へ進みます。

• 探索方向: 勾配の逆方向 $-g = b - Ax$

• 課題: 谷が細長い（条件数が大きい）場合、谷の壁をジグザグに反射するように進んでしまい、谷底の最適解に向かうスピードが極端に落ちます。

ニュートン法 (Newton’s Method)​

2階微分（ヘッシアン $A$）の情報を使い、曲率を考慮して1回のステップで直接最適解（谷底）を狙います。

• 探索方向: $A^{-1} (-g)$

• 課題: 巨大な行列 $A$ の逆行列を計算する必要があり、高次元の問題では計算量（$O(N^3)$）やメモリがパンクして実行不可能です。

共役勾配法 (Conjugate Gradient)​

最急降下法の「ジグザグ現象」を回避し、かつニュートン法のような「逆行列計算」を不要にするのが共役勾配法です。各ステップの探索方向 $p_k$ を、過去のすべての探索方向と「行列 $A$ に関して直交（共役）」になるように決定して進みます。

添え字の意味について（$k, i, j$ など） 共役勾配法のような「反復法（何度もループを繰り返して正解に近づいていくアルゴリズム）」において、数式に登場するこれらの添え字は基本的に「何回目のステップ（反復）か」というカウント番号（1回目、2回目、3回目…）を表しています。このことを踏まえて、以下の解説をお読みください。

「行列 $A$ に関して共役」とは？ 2つのベクトル $p_i$ と $p_j$ が以下の関係を満たすとき、それらは行列 $A$ に関して共役（$A$-直交）であると言います。

ここで $i$ と $j$ は特定の「今」や「1つ前」ではなく、「全体のステップの中の、ある適当な2つのステップ」を指す記号です。つまり、カッコの中の $(i \neq j)$ は「ステップ番号 $i$ と $j$ が違う数字のとき」を意味しており、この式は「1回目と2回目、2回目と5回目など、とにかく『違うステップ』の方向を2つ取り出して計算したら、必ず $A$-直交（結果がゼロ）になる」という状態を表しています。 通常の直交（$p_i^T p_j = 0$）とは異なり、目的関数の歪み（行列 $A$ の影響）を考慮した空間上で直交していることを意味します。

• 探索方向: 新しい探索方向 $p_k$ は、現在の最も急な方向である残差（マイナスの勾配 $r_k = -g_k$）と、直前の探索方向 $p_{k-1}$ の線形結合として計算されます。

添え字の $k$ は「現在計算しているステップ（今まさに進めようとしている番）」を、$k-1$ は「今のステップの1つ前（直前のステップ）」を表します。 すなわちこの式は、「今の新しい進み方（$p_k$）は、現在の最も急な傾き（$r_k$）に、1つ前で進んだ方向（$p_{k-1}$）をうまく混ぜ合わせて（線形結合して）決定する」というルールを数式で表現しているものです。

共役勾配法の最も優れているポイントは、更新式では「1つ前の方向（$k-1$）」だけを見て新しい方向（$k$）を決めているのに、結果として出来上がった方向は、過去のすべてのステップ（前述の $i$ と $j$）の方向と互いに独立して干渉しない（$A$-直交になる）という点にあります。

• 利点: アルゴリズムの中で最も重い計算は、$\beta_k$ や歩幅を求める際の 「行列 $A$ とベクトル $p$ の掛け算（$Ap$）」 だけであり、逆行列 $A^{-1}$ を求める必要がありません。 また、一度探索した方向については最適化が完全に完了し、その方向の最適性が後から崩れることがありません（独立性が保たれる）。添え字を「ステップの番号札」として読み替えると、アルゴリズムが互いに干渉しない独立したステップを順番に踏んでいる様子が直感的にイメージしやすくなるはずです。 結果として、変数の数が $N$ 個（$N$ 次元空間）であれば、最大でも $N$ 回のステップで必ず厳密解に到達します。

コードによる挙動の確認​

それでは、Pythonコードを使って最急降下法と共役勾配法の挙動を確認してみましょう。 目的関数として、等高線が細長い楕円となる二次関数 $f(x) = \frac{1}{2}x^T A x - b^T x$ を設定します。

import numpy as np
import matplotlib.pyplot as plt
import japanize_matplotlib  # グラフ日本語表示用

# 係数行列 A と ベクトル b の設定（細長い谷を作るために固有値に差をつける）
A = np.array([[3.0, 2.0], 
              [2.0, 6.0]])
b = np.array([2.0, -8.0])

# 目的関数 f(x)
def f(x):
    return 0.5 * np.dot(x.T, np.dot(A, x)) - np.dot(b.T, x)

# 勾配（1階微分）
def grad_f(x):
    return np.dot(A, x) - b

# 探索空間の設定
x_vals = np.linspace(-6, 6, 100)
y_vals = np.linspace(-6, 6, 100)
X, Y = np.meshgrid(x_vals, y_vals)
Z = np.zeros_like(X)

for i in range(X.shape[0]):
    for j in range(X.shape[1]):
        Z[i, j] = f(np.array([X[i, j], Y[i, j]]))

# 目的関数の等高線の可視化
plt.figure(figsize=(8, 6))
plt.contour(X, Y, Z, levels=30, cmap='viridis', alpha=0.8)
plt.title("目的関数 f(x) の等高線")
plt.xlabel("変数 x1")
plt.ylabel("変数 x2")
plt.colorbar(label='f(x) の値')
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

ここでは、共役勾配法と最急降下法の性能を比較するため、あえて最適化が難しい「細長い谷」を持つ目的関数を定義しています。

• A と b の設定: A = np.array([[3.0, 2.0], [2.0, 6.0]]) とすることで、固有値に差がある（条件数が大きい）正定値対称行列を作成しています。これにより、目的関数 f(x) の等高線は真円ではなく、細長い楕円形に歪みます。
• f(x) の実装: 目的関数である二次形式を 0.5 * np.dot(x.T, np.dot(A, x)) - np.dot(b.T, x) として実装しています。この関数の最小値（谷底）を求めることが、連立一次方程式 Ax = b を解くことと同値になります。
• grad_f(x) の実装: 目的関数の1階微分である勾配ベクトルを np.dot(A, x) - b で計算します。最急降下法や共役勾配法において、どの方向に進むべきかを決定するための重要な情報源となります。
• np.meshgrid による探索空間の設定: -6 から 6 までの範囲で格子状の座標点（X, Y）を作成し、それぞれの点における関数の高さ（Z）を計算しています。これを plt.contour に渡すことで、最適化の軌跡を視覚的にマッピングするための等高線ベースマップが構築されます。 上記のコードを実行すると、目的関数の等高線が細長い楕円形になっていることが確認できます。

この目的関数の最適解（谷底）は、$Ax = b$ を満たす点になります。

最急降下法による探索（ジグザグ現象）​

最初に、最急降下法（正確な直線探索付き）で探索します。

# 初期解の設定
x_init = np.array([-5.0, 4.0])

# 最急降下法
x_sd = x_init.copy()
path_sd = [x_sd.copy()]

for _ in range(15):
    g = grad_f(x_sd)
    
    # 勾配が十分に小さければ終了
    if np.linalg.norm(g) < 1e-5:
        break
        
    # 正確な直線探索（Exact Line Search）による最適な歩幅 alpha の計算
    alpha = np.dot(g, g) / np.dot(g, np.dot(A, g))
    
    # パラメータの更新
    x_sd = x_sd - alpha * g
    path_sd.append(x_sd.copy())

print(f"最急降下法の反復回数: {len(path_sd)-1}")
print(f"到達した解: {x_sd}")
print("❌ 課題: 谷の壁をジグザグに進むため、反復回数が多くなる。")

# 最急降下法の探索軌跡の可視化
path_sd_np = np.array(path_sd)
plt.figure(figsize=(8, 6))
plt.contour(X, Y, Z, levels=30, cmap='viridis', alpha=0.8)
plt.plot(path_sd_np[:, 0], path_sd_np[:, 1], marker='o', color='red', linestyle='-', linewidth=2, label='最急降下法')
plt.plot(2.0, -2.0, marker='*', color='gold', markersize=15, markeredgecolor='black', label='最適解')
plt.title("最急降下法の探索軌跡（ジグザグ現象）")
plt.xlabel("変数 x1")
plt.ylabel("変数 x2")
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

ここでは、古典的な勾配降下法（最急降下法）を実装し、その挙動をシミュレーションしています。

• g = grad_f(x_sd): 各ループの先頭で現在の位置における勾配ベクトル（最も傾きが急な方向）を計算します。
• alpha = np.dot(g, g) / np.dot(g, np.dot(A, g)): 固定の学習率（歩幅）を使うのではなく、「正確な直線探索（Exact Line Search）」によって最適な歩幅 alpha を動的に計算しています。これは、現在向いている方向（-g）に進んだときに、目的関数が最小になる距離を二次形式の解析解から求めたものです。
• x_sd = x_sd - alpha * g: 現在の位置から、勾配の逆方向に向かって最適な歩幅分だけパラメータを更新します。
• 探索の記録と終了判定: path_sd.append() で各ステップの座標を保存し、勾配のノルム（大きさ）が 1e-5 を下回った時点で「最適解（谷底）に十分近づいた」と判定してループを終了します。

上記のコードを実行すると、最急降下法が谷の壁に沿ってジグザグに進む様子が可視化されます。

実行結果​

最急降下法の反復回数: 15
到達した解: [ 1.99881524 -1.99982332]
❌ 課題: 谷の壁をジグザグに進むため、反復回数が多くなる。

最急降下法は、15回の更新を行ってもまだ少し誤差が残っています。最適解に向かって一直線に進めず、非効率な探索を行っていることがわかります。

共役勾配法による探索​

次に、共役勾配法を用いて同じ初期位置から探索を行います。

# 共役勾配法 (Conjugate Gradient)
x_cg = x_init.copy()
path_cg = [x_cg.copy()]

# 初期状態のセットアップ
r = b - np.dot(A, x_cg)  # 残差（-勾配に相当）
p = r.copy()             # 探索方向

for _ in range(15):
    if np.linalg.norm(r) < 1e-5:
        break
        
    # Aと探索方向pの掛け算（これがアルゴリズム中で最も重い計算）
    Ap = np.dot(A, p)
    
    # 歩幅 alpha の計算
    alpha = np.dot(r, r) / np.dot(p, Ap)
    
    # パラメータの更新
    x_cg = x_cg + alpha * p
    path_cg.append(x_cg.copy())
    
    # 新しい残差の計算
    r_new = r - alpha * Ap
    
    # 探索方向の修正係数 beta の計算
    beta = np.dot(r_new, r_new) / np.dot(r, r)
    
    # 共役な新しい探索方向 p の決定
    p = r_new + beta * p
    r = r_new

print(f"共役勾配法の反復回数: {len(path_cg)-1}")
print(f"到達した解: {x_cg}")
print("⭕ 利点: 過去の探索方向と共役（干渉しない）に進むため、2次元なら2ステップで厳密解に到達する。")

# 共役勾配法の探索軌跡の可視化
path_cg_np = np.array(path_cg)
plt.figure(figsize=(8, 6))
plt.contour(X, Y, Z, levels=30, cmap='viridis', alpha=0.8)
plt.plot(path_cg_np[:, 0], path_cg_np[:, 1], marker='s', color='blue', linestyle='-', linewidth=2, label='共役勾配法 (CG)')
plt.plot(2.0, -2.0, marker='*', color='gold', markersize=15, markeredgecolor='black', label='最適解')
plt.title("共役勾配法の探索軌跡（2ステップで到達）")
plt.xlabel("変数 x1")
plt.ylabel("変数 x2")
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

続いて、本記事の主役である共役勾配法（CG法）の実装です。最急降下法と比較して、各ステップがどのように過去の情報を引き継いでいるかに注目してください。

• 初期状態と残差の設定 ($r_0 = b - Ax_0$, $p_0 = r_0$): r = b - np.dot(A, x_cg) で初期の「残差ベクトル（最適解からのズレ、マイナスの勾配に相当）」を計算し、最初の探索方向 p = r.copy() に設定します。
• 行列ベクトル積 ($A p_k$): Ap = np.dot(A, p) はアルゴリズムの反復ループ内で唯一計算コストの高い部分です。巨大な行列 A の逆行列を求めることなく、この掛け算だけで済む点がCG法の真髄です。
• 歩幅 alpha の計算 ($\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k}$): np.dot(r, r) / np.dot(p, Ap) により、現在の探索方向 p 上で目的関数が最小となる最適な移動量 alpha を一発で決定します。
• 変数と残差の更新 ($x_{k+1} = x_k + \alpha_k p_k$, $r_{k+1} = r_k - \alpha_k A p_k$): x_cg = x_cg + alpha * p で位置を更新し、それと同時に新しい残差 r_new を r - alpha * Ap として効率よく差分更新します。
• 共役な新しい探索方向 p の決定 ($\beta_{k+1} = \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k}$, $p_{k+1} = r_{k+1} + \beta_{k+1} p_k$): beta = np.dot(r_new, r_new) / np.dot(r, r) で直前の探索方向を混ぜ合わせる比率 beta を計算します。これを用いて p = r_new + beta * p を実行することで、先ほど解説した「過去の探索方向と $A$-直交になる新しい方向」が魔法のように生成されます。

上記のコードを実行すると、共役勾配法がわずか2回の更新で最適解に到達する様子が可視化されます。

実行結果​

共役勾配法の反復回数: 2
到達した解: [ 2. -2.]
⭕ 利点: 過去の探索方向と共役（干渉しない）に進むため、2次元なら2ステップで厳密解に到達する。

結果として、2次元空間の最適化問題に対し、理論通り たった2ステップ で厳密な最適解に到達することができました。

探索軌跡の可視化​

両者の軌跡を等高線グラフ上で比較し、どれほどの差が出るのかを視覚的に確認します。

path_sd = np.array(path_sd)
path_cg = np.array(path_cg)

plt.figure(figsize=(10, 8))
# 等高線の描画
plt.contour(X, Y, Z, levels=30, cmap='viridis', alpha=0.6)

# 最急降下法の軌跡（赤色）
plt.plot(path_sd[:, 0], path_sd[:, 1], marker='o', color='red', 
         linestyle='-', linewidth=2, label='最急降下法', alpha=0.8)

# 共役勾配法の軌跡（青色）
plt.plot(path_cg[:, 0], path_cg[:, 1], marker='s', color='blue', 
         linestyle='-', linewidth=2, label='共役勾配法 (CG)', alpha=0.8)

# 最適解のプロット
plt.plot(2.0, -2.0, marker='*', color='gold', markersize=15, 
         markeredgecolor='black', label='最適解')

plt.title("最急降下法と共役勾配法の探索軌跡の比較", fontsize=14, fontweight='bold')
plt.xlabel("変数 x1", fontsize=12)
plt.ylabel("変数 x2", fontsize=12)
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

最後に、ここまでのシミュレーション結果（最急降下法と共役勾配法の軌跡）を1つの等高線グラフに重ねて描画します。

• 探索軌跡の統合表示: plt.plot() を用いて、最急降下法の軌跡（path_sd）を赤色の丸印（marker='o'）で、共役勾配法の軌跡（path_cg）を青色の四角印（marker='s'）でプロットしています。
• 最適解のハイライト: グラフの中心となる厳密解を plt.plot(2.0, -2.0, marker='*') で大きな星印として描画し、両アルゴリズムがどこに向かっているのかを視覚的に明確にしています。
• alpha パラメータによる視認性向上: 等高線や軌跡の描画時に alpha を指定して半透明にすることで、要素が重なっても双方の軌跡や等高線の形状が潰れずに比較できる工夫が施されています。（※ここでの alpha は共役勾配法の歩幅ではなく、Matplotlib における描画の「透明度」を指定するパラメータです）

上記のコードを実行すると、最急降下法と共役勾配法の軌跡を比較したグラフを得られます。

実行結果​

グラフからわかるように、最急降下法（赤線）が等高線の壁で反射して無駄なジグザグ軌跡を描くのに対し、共役勾配法（青線）は無駄なく一直線に最適解へ到達しています。 前述した「過去の探索と干渉しない（$A$-直交）」という性質が、この圧倒的な効率の差を生み出していることが視覚的にもはっきりと確認できます。

まとめ​

本記事では、大規模な最適化問題や連立一次方程式を効率的に解くための「共役勾配法（CG法）」について解説しました。

• ジグザグ現象の解消: 単純な勾配降下法が陥りやすいジグザグとした無駄な探索を、探索方向を「共役」に保つことで防ぎます。
• 逆行列計算の回避: ニュートン法のような優れた収束性を持ちながら、巨大な行列の全成分を保持したり逆行列を計算したりする必要がありません。
• 実装の応用: TRPOなどの高度な強化学習アルゴリズムでは、このCG法の特性と自動微分（フィッシャー・ベクトル積）を組み合わせることで、巨大なニューラルネットワークのパラメータ更新を高速に行っています。

最適化アルゴリズムは、問題の規模や目的関数の性質によって適切なものを選択することが不可欠です。共役勾配法は、計算リソースの制約が厳しい現代の機械学習においても極めて重要な役割を担っています。