直線探索（Line Search）とは？

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

直線探索の概要​

直線探索（Line Search） は、数理最適化（特に関数の最小化問題）において、アルゴリズムが「どの方向に進むか」を決定した後、「その方向にどれだけの歩幅（ステップサイズ）で進むか」 を決定するための重要な手法です。

機械学習やディープラーニングにおける「勾配降下法」では、歩幅を「学習率（Learning Rate）」という固定のハイパーパラメータとして手動で設定することが一般的です。しかし、固定の学習率では、大きすぎると最適解を通り越して発散してしまい、小さすぎると収束までに膨大な時間がかかるというジレンマがあります。

直線探索は、現在の位置と探索方向に関する情報を元に、毎回のステップで最適な歩幅を動的に計算・探索する アプローチです。これにより、手動での学習率チューニングの手間を省きつつ、安全かつ高速に最適解へ向かうことが可能になります。

これまで解説した 共役勾配法（CG） における「二次形式の解析的な歩幅計算」や、TRPO における「制約を満たすための後退代入法」も、すべてこの直線探索の応用例です。

歩幅の決定ルール（固定・正確・不正確）​

最適化アルゴリズムにおいて、探索方向 $p_k$ （例えばマイナスの勾配方向）が決まった後、新しい位置 $x_{k+1} = x_k + \alpha_k p_k$ を決めるための歩幅 $\alpha_k$ の決定方法には、大きく分けて3つのアプローチがあります。

1. 固定ステップサイズ (Fixed Step Size)​

ディープラーニングの標準的なオプティマイザ（SGDなど）でよく使われる方法です。

• 手法: あらかじめ決めた定数（例: $\alpha = 0.01$）や、ステップ数に応じて減衰する固定スケジュールを用います。
• 特徴: 計算コストはゼロですが、問題の曲率（地形の急激な変化）に対応できないため、ジグザグ現象や発散のリスクが常に伴います。

2. 正確な直線探索 (Exact Line Search)​

進む方向の直線上で、目的関数 $f(x_k + \alpha p_k)$ が完全に最小になるような $\alpha$ を厳密に計算します。

• 手法: $\frac{d}{d\alpha} f(x_k + \alpha p_k) = 0$ となる $\alpha$ を求めます。共役勾配法のような目的関数が二次形式（$f(x) = \frac{1}{2}x^T A x - b^T x$）の問題では、解析的に $\alpha = \frac{r^T r}{p^T A p}$ と一発で計算できます。
• 特徴: 最も理想的ですが、一般的な複雑な非線形関数においては、この1ステップのための最小値探索自体が重い最適化問題になってしまうため、実用的ではありません。

3. 不正確な直線探索 (Inexact Line Search / Backtracking)​

「完全に最小の点を見つける必要はなく、十分に目的関数が減少する安全な歩幅が見つかればそれでよい」という妥協的かつ実用的なアプローチです。現代の多くの最適化手法（TRPOなど）で採用されています。

• 手法: 最初に大きな歩幅（例えば $\alpha = 1.0$）を試し、条件（Armijo条件やWolfe条件など）を満たさなければ歩幅を半分（$\alpha \leftarrow 0.5 \alpha$）に縮めていくバックトラッキング（後退代入法） が主流です。
• Armijo（アルミホ）条件: 「歩幅 $\alpha$ に比例して、目的関数が最低限これくらいは減少してほしい」という基準を定めた条件です。 $f(x_k + \alpha p_k) \le f(x_k) + c \alpha \nabla f(x_k)^T p_k$ （ここで $c \in (0, 1)$ はごく小さな定数）

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

それでは、Pythonコードを使って「固定ステップサイズ」と「不正確な直線探索（バックトラッキング）」の挙動を比較してみましょう。 目的関数として、一方向だけ極端に傾きが急な二次関数 $f(x, y) = x^2 + 10y^2$ を設定します。

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

# 目的関数 f(x, y) = x^2 + 10y^2
# y方向の曲率（傾き）がx方向の10倍ある、最適化が難しい細長い楕円状の関数です。
def f(x):
    return x[0]**2 + 10 * x[1]**2

# 勾配（1階微分） grad_f(x, y) = [2x, 20y]
# 現在の位置における最も急な上り坂の方向を示します。最適化ではこの逆方向に進みます。
def grad_f(x):
    return np.array([2 * x[0], 20 * x[1]])

# 探索空間の設定
# x, yの範囲を指定し、等高線を描画するための格子点（メッシュグリッド）を作成します。
x_vals = np.linspace(-10, 10, 100)
y_vals = np.linspace(-5, 5, 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=np.logspace(-1, 3, 20), cmap='viridis', alpha=0.8)
plt.title("目的関数 f(x, y) = x^2 + 10y^2 の等高線")
plt.xlabel("変数 x")
plt.ylabel("変数 y")
plt.colorbar(label='f(x) の値')
plt.plot(0, 0, marker='*', color='gold', markersize=15, markeredgecolor='black', label='最適解')
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

上記のコードでは、最適化アルゴリズムの挙動を検証するため、あえて 「方向によって傾きが極端に異なる目的関数」 を構築しています。

• 目的関数の定義: def f(x) で定義された関数 $f(x, y) = x^2 + 10y^2$ は、$y$ 軸方向の傾きが $x$ 軸方向の10倍もあるため、等高線が細長い楕円になります。このような曲率（ヘッセ行列の条件数）が大きい地形は、固定歩幅のアルゴリズムにとって非常に厄介な課題となります。
• 勾配ベクトル: def grad_f(x) は、現在の座標における勾配 $\nabla f(x)$ を計算します。接線の傾きを表すこのベクトルは、後述する Armijo 条件の $\nabla f(x_k)^T p_k$ の計算や、降下方向 $p_k = -\nabla f(x_k)$ の決定において中心的な役割を果たします。
• 可視化の意図: plt.contour を用いて等高線を描画することで、アルゴリズムがどのように谷を下っていくか（あるいは谷を飛び越えて振動してしまうか）を直感的に確認するための土台を作っています。

実行結果​

ここでは、$y$ 方向の傾きが $x$ 方向の10倍急になっている関数（細長い楕円の等高線）を定義しています。 このような関数は、固定の学習率で最適化しようとすると非常に厄介な性質を示します。

固定歩幅（学習率）による探索（ジグザグ現象）​

まず、固定の学習率（歩幅 $\alpha = 0.085$）を用いた単純な最急降下法で探索を行います。

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

# 固定ステップサイズ（学習率）
alpha_fixed = 0.085

x_fixed = x_init.copy()
path_fixed = [x_fixed.copy()]

for i in range(30):
    g = grad_f(x_fixed)
    
    # 勾配が十分に小さければ（最適解に十分近ければ）探索を終了
    if np.linalg.norm(g) < 1e-4:
        break
        
    # パラメータの更新（固定歩幅）
    # x_{k+1} = x_k - α * ∇f(x_k) に相当します。
    x_fixed = x_fixed - alpha_fixed * g
    path_fixed.append(x_fixed.copy())

print(f"固定歩幅の反復回数: {len(path_fixed)-1}")
print(f"到達した解: {x_fixed}")
print("❌ 課題: 歩幅の調整ができないため、y方向で大きく振動（ジグザグ）してしまう。")

# 軌跡の可視化
path_fixed_arr = np.array(path_fixed)
plt.figure(figsize=(8, 6))
plt.contour(X, Y, Z, levels=np.logspace(-1, 3, 20), cmap='viridis', alpha=0.6)
plt.plot(path_fixed_arr[:, 0], path_fixed_arr[:, 1], marker='o', color='red', linestyle='-', label='固定歩幅')
plt.plot(0, 0, marker='*', color='gold', markersize=15, markeredgecolor='black', label='最適解')
plt.title("固定歩幅の探索軌跡")
plt.xlabel("変数 x")
plt.ylabel("変数 y")
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

ここでは、ディープラーニングなどでよく用いられる「固定の学習率（歩幅）」による最急降下法を実装しています。

• 固定歩幅の適用: alpha_fixed = 0.085 という固定の定数を用いて、x_fixed = x_fixed - alpha_fixed * g としてパラメータを更新しています。これはテイラー展開に基づく一次近似の方向に、地形の変化を無視して一定の距離を進むことを意味します。
• ジグザグ現象の発生: 前述の通り、$y$ 方向の傾きが急であるため、歩幅 $\alpha$ が大きすぎると $y$ 軸の谷を飛び越えてしまいます。固定歩幅では「進みすぎ」を検知して歩幅を縮める安全装置がないため、収束までに無駄な反復（振動）を繰り返すことになります。

このコードでは、常に $\alpha = 0.085$ という一定の割合で勾配の逆方向に進みます。 実行結果は以下のようになります。

実行結果​

固定歩幅の反復回数: 30
到達した解: [0.03810145  0.13841287]
❌ 課題: 歩幅の調整ができないため、y方向で大きく振動（ジグザグ）してしまう。

$y$ 方向の傾き（勾配）が大きいため、一定の歩幅を掛けると $y$ 方向に進みすぎて谷を飛び越えてしまい、 振動が発生して収束が遅れています。もし $\alpha = 0.1$ 以上に設定すると、谷を飛び越える幅がどんどん大きくなり発散してしまいます。

バックトラッキング直線探索による探索​

次に、不正確な直線探索（Armijo条件を用いたバックトラッキング）を実装して、同じ初期位置から探索を行います。

# バックトラッキング直線探索のパラメータ
c = 0.1       # Armijo条件の許容定数（予想減少量に対する最低保証割合）
rho = 0.5     # 歩幅の縮小率（条件を満たさない場合に歩幅を半分にする）

x_ls = x_init.copy()
path_ls = [x_ls.copy()]

for i in range(30):
    g = grad_f(x_ls)
    
    if np.linalg.norm(g) < 1e-4:
        break
        
    # 探索方向 p_k はマイナスの勾配（最急降下方向）
    p = -g
    
    # 直線探索：初期歩幅を0.4とし、Armijo条件を満たすまで縮める
    alpha = 0.4
    
    # Armijo条件のチェック
    # f(x_k + αp_k) > f(x_k) + c * α * ∇f(x_k)^T p_k
    # この条件がTrueの間は「関数の減少量が、一次近似による予想減少量のc倍に達していない（進みすぎ）」と判断します。
    while f(x_ls + alpha * p) > f(x_ls) + c * alpha * np.dot(g, p):
        alpha *= rho  # 歩幅を半分にする（バックトラッキング）
        
    # Armijo条件を満たす安全な歩幅 α が見つかったので、パラメータを更新
    x_ls = x_ls + alpha * p
    path_ls.append(x_ls.copy())

print(f"直線探索の反復回数: {len(path_ls)-1}")
print(f"到達した解: {x_ls}")
print("⭕ 利点: 毎ステップで安全な歩幅を自動で探すため、振動せずに素早く収束する。")

# 軌跡の可視化
path_ls_arr = np.array(path_ls)
plt.figure(figsize=(8, 6))
plt.contour(X, Y, Z, levels=np.logspace(-1, 3, 20), cmap='viridis', alpha=0.6)
plt.plot(path_ls_arr[:, 0], path_ls_arr[:, 1], marker='s', color='blue', linestyle='-', label='バックトラッキング直線探索')
plt.plot(0, 0, marker='*', color='gold', markersize=15, markeredgecolor='black', label='最適解')
plt.title("バックトラッキング直線探索の探索軌跡")
plt.xlabel("変数 x")
plt.ylabel("変数 y")
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

ここでは、記事の前半で解説した Armijo条件 と テイラー展開による一次近似 の概念を組み込んだ、バックトラッキング（不正確な直線探索）を実装しています。

• 予想減少量の計算: np.dot(g, p) は、数式における $\nabla f(x_k)^T p_k$ に相当します。降下方向へ進むためこれはマイナスの値となり、これに歩幅 $\alpha$ を掛けたものが「一次近似による理想的な予想減少量」になります。
• Armijo条件による評価: while f(...) > f(...) + c * alpha * np.dot(g, p): のループが直線探索の心臓部です。実際の関数の値が、予想減少量の $c$ 倍（c = 0.1）すら下がっていない場合は「地形が曲がっていて谷を飛び越えた」と判断します。
• バックトラッキング（後退）: 条件を満たさない限り、alpha *= rho によって歩幅を半分（rho = 0.5）に縮めていきます。これにより、毎ステップで「最適解に向かって安全かつ最大限に進める歩幅」が自動的に決定され、固定歩幅のような発散やジグザグ現象を回避できます。

実行結果​

直線探索の反復回数: 9
到達した解: [-1.8432e-05  0.0000e+00]
⭕ 利点: 毎ステップで安全な歩幅を自動で探すため、振動せずに素早く収束する。

直線探索を用いた場合、わずか9回の反復でほぼ最適解 [-1.8432e-05 0.0000e+00] に到達しました。

探索軌跡の可視化​

両者の軌跡を等高線グラフ上で比較します。

# これまで保存してきた探索履歴（リスト）をNumPy配列に変換し、スライス（[:, 0]など）を使えるようにします
path_fixed = np.array(path_fixed)
path_ls = np.array(path_ls)

plt.figure(figsize=(10, 8))
plt.contour(X, Y, Z, levels=np.logspace(-1, 3, 20), cmap='viridis', alpha=0.6)

# 固定歩幅の軌跡（赤色）
# marker='o' で丸印をつけて各ステップをプロットします
plt.plot(path_fixed[:, 0], path_fixed[:, 1], marker='o', color='red', 
         linestyle='-', linewidth=2, label='固定歩幅 (lr=0.085)', alpha=0.8)

# バックトラッキング直線探索の軌跡（青色）
# marker='s' で四角印をつけてプロットします
plt.plot(path_ls[:, 0], path_ls[:, 1], marker='s', color='blue', 
         linestyle='-', linewidth=2, label='バックトラッキング直線探索', alpha=0.8)

# 最適解（原点）を黄色の星マークで強調します
plt.plot(0, 0, marker='*', color='gold', markersize=15, 
         markeredgecolor='black', label='最適解')

plt.title("固定歩幅と直線探索の探索軌跡の比較", fontsize=14, fontweight='bold')
plt.xlabel("変数 x", fontsize=12)
plt.ylabel("変数 y", fontsize=12)
plt.legend()
plt.grid(True, linestyle='--', alpha=0.5)
plt.show()

ここでは、2つのアルゴリズムが最適解にどのように近づいていくかを同じ等高線グラフ上で比較・可視化しています。

• 配列の変換: np.array(path_fixed) によって履歴リストを2次元配列に変換することで、path_fixed[:, 0] （すべてのステップのx座標）と path_fixed[:, 1] （すべてのステップのy座標）のように簡潔に抽出してプロットできるようにしています。
• グラフから読み取れる違い: プロット結果を見ると、固定の学習率（赤色）では等高線の急な変化に対応できず、$y$ 軸の谷を飛び越えて激しく振動している様子が確認できます。対照的に、バックトラッキング直線探索（青色）では地形に合わせて歩幅を適切に制御し、無駄な振動を起こすことなく滑らかに最適解（中心の星マーク）へと収束していく様子が視覚的にもはっきりと理解できます。

実行結果​

グラフからわかるように、固定歩幅（赤線）は $y$ 方向の急な傾きに対応できず、谷を何度も挟んでジグザグと振動しながら進んでいます。 一方、バックトラッキング直線探索（青線）は、最初は $y$ 方向に大きく進もうとしますが、 Armijo条件によって「進みすぎ」を検知して自動的に歩幅を狭めるため、谷を飛び越えることなく中心の最適解に向かって滑らかに降下しています。

まとめ​

本記事では、最適化アルゴリズムにおいてステップサイズを動的に決定する「直線探索（Line Search）」について解説しました。

• 課題の解決: 固定の学習率では回避困難な「ジグザグ現象（振動）」や「発散」を、その場の地形に合わせて歩幅を調整することで防ぎます。

• 実用的なアプローチ（バックトラッキング）: 完全に最適な歩幅を計算するのではなく、「十分に目的関数が改善する」条件（Armijo条件など）を満たすまで歩幅を縮めていく不正確な直線探索が実務では広く使われています。

• 他アルゴリズムとの繋がり:

  • 共役勾配法（CG）では、二次形式の特性を活かした「正確な直線探索」で一発で歩幅を決定します。
  • TRPOなどの強化学習アルゴリズムでは、「KLダイバージェンス制約」と「目的関数の改善」の両方をArmijo条件のようにチェックするバックトラッキング直線探索が、方策崩壊を防ぐ要として機能しています。

アルゴリズムの性能は、「どの方向へ進むか（勾配、ニュートン方向、共役方向など）」と「どれくらい進むか（直線探索）」の強力な組み合わせによって決まります。直線探索の概念を理解することで、様々な最適化アルゴリズムの挙動をより深く解釈できるようになります。