メインコンテンツまでスキップ

直線探索(Line Search)とは? 最適化の歩幅の決め方

概要 (画像は、Geminiで作成)

💡この記事のゴール

進む方向を決めたあとに、どれだけ進むか(歩幅)を決める直線探索について、固定の歩幅・正確な直線探索・バックトラッキング(Armijo 条件)の違いを理解すること。固定の学習率では歩幅を大きくすると発散する例と比べて、バックトラッキングが調整なしで関数を確実に下げる歩幅を選べること、ただし方向は変えないのでジグザグは残ることを確かめ、共役勾配法や TRPO での使われ方を説明できるようになること。

直線探索(Line Search)とは?​

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

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

直線探索は、現在の位置と探索方向に関する情報を元に、毎回のステップで適切な歩幅を動的に計算・探索する アプローチです。これにより、手動での学習率チューニングの手間を省きつつ、目的関数が確実に下がる歩幅で進めるようになります。ただし、決めるのは歩幅だけで、進む方向は変えません。この違いは、後半の実験で確かめます。

共役勾配法(CG) における「二次形式の解析的な歩幅計算」や、TRPO における「制約を満たすまで歩幅を縮めるバックトラッキング」も、この直線探索の応用例です。

この記事の読み方​

目的に合わせて、次の節から読み始めてください。

知りたいこと読む節
すぐに使ってみたい直後の「最短の使い方」(バックトラッキングの関数と SciPy)
歩幅の決め方の種類と Armijo 条件歩幅の決定ルール(固定・正確・不正確)
固定の学習率では何が困るのか固定歩幅(学習率)による探索
直線探索で最適化を回したときの動きバックトラッキング直線探索による探索と探索軌跡の可視化

最短の使い方:バックトラッキングの関数と SciPy で歩幅を決める​

Armijo 条件を使ったバックトラッキングを1つの関数にまとめ、SciPy の scipy.optimize.line_search と同じ点・同じ方向で歩幅を比べます。目的関数 f(x,y)=x2+10y2f(x, y) = x^2 + 10y^2 と初期点 (−8,3)(-8, 3) は、本文の実験と同じです。

import numpy as np
from scipy.optimize import line_search

def backtracking(f, grad, x, p, alpha=1.0, rho=0.5, c=1e-4):
"""Armijo 条件を満たすまで歩幅を縮め、方向 p に進む歩幅を返す"""
g = grad(x)
# 予想減少量の c 倍すら下がらない間は「進みすぎ」とみなして歩幅を縮める
while f(x + alpha * p) > f(x) + c * alpha * np.dot(g, p):
alpha *= rho
return alpha

# 本文と同じ目的関数 f(x, y) = x^2 + 10y^2 と、その勾配
f = lambda x: x[0]**2 + 10 * x[1]**2
grad = lambda x: np.array([2 * x[0], 20 * x[1]])

x = np.array([-8.0, 3.0])
p = -grad(x) # 進む方向:最急降下方向
print("バックトラッキングの歩幅:", backtracking(f, grad, x, p))
print("SciPy(Wolfe 条件)の歩幅:", line_search(f, grad, x, p)[0])
  • backtracking(f, grad, x, p): 目的関数 f・勾配 grad・現在の位置 x・進む方向 p を受け取り、歩幅を返します。関数と勾配を引数で渡すので、ほかの最適化問題にもそのまま使えます。
    • while の条件: Armijo 条件 f(x+αp)≤f(x)+c α ∇f(x)⊤pf(x + \alpha p) \le f(x) + c\,\alpha\,\nabla f(x)^\top p が成り立たない間、つまり「接線で予想した減少量の cc 倍すら下がっていない」間は、進みすぎとみなして歩幅を rho 倍(半分)にします。
    • 既定値: 初期の歩幅 1、c=10−4c = 10^{-4}、縮小率 0.5 は、本文と同じく Nocedal & Wright の教科書(Numerical Optimization)が挙げる標準的な値です。
  • line_search(f, grad, x, p): SciPy の直線探索です。Armijo 条件に加えて、進んだ先の傾きが十分に緩やかになっていることも求める(強い)Wolfe 条件を満たす歩幅を探します(既定値は c1=10−4c_1 = 10^{-4}、c2=0.9c_2 = 0.9)。戻り値はタプルで、先頭([0])が歩幅です。

実行結果​

バックトラッキングの歩幅: 0.0625
SciPy(Wolfe 条件)の歩幅: 0.05317740511915269

CPU で1秒もかかりません。

  • バックトラッキング: 歩幅 1 から 0.5・0.25・0.125・0.0625 と4回縮めて、0.0625 で Armijo 条件を満たしました。本文の「1 回目:歩幅 0.0625(4 回縮めた)」と同じ値です。
  • SciPy: 歩幅は 0.0532 で、この点での正確な直線探索の答え α=g⊤g/(2 g⊤Ag)=3856/72512≈0.0532\alpha = g^\top g / (2\, g^\top A g) = 3856 / 72512 \approx 0.0532(gg は勾配、A=diag(1,10)A = \mathrm{diag}(1, 10))とほぼ同じです。SciPy は、試した歩幅での関数の値と傾きから f(x+αp)f(x + \alpha p) を2次式・3次式で補間して次に試す歩幅を決めるので、目的関数が2次式のこの例では、最適な歩幅にほぼ一致しました。
  • どちらも正しい歩幅: 0.0625 も、Wolfe 条件を満たしています。直線探索の目的は「最適な歩幅」ではなく「関数を確実に下げる歩幅」を安く見つけることなので、条件を満たす歩幅が複数あるのは普通です。

この1ステップを30回くり返したときの軌跡と、固定の学習率との違いは、本文の実験で確かめます。

歩幅の決定ルール(固定・正確・不正確)​

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

3つの決め方を並べると、次のようになります。

歩幅 α の決め方の 3 つの種類。固定ステップサイズは、あらかじめ決めた定数(例:α = 0.01)を使い、計算コストはゼロだが、曲率に対応できず、ジグザグや発散のおそれがある。正確な直線探索は、f(x_k + α p_k) が最小になる α を求め、二次形式なら解析的に求まるが、一般の関数では重い。不正確な直線探索(バックトラッキング)は、α = 1.0 から始めて Armijo 条件を満たすまで半分に縮める歩幅 α の決め方の 3 つの種類。固定ステップサイズは、あらかじめ決めた定数(例:α = 0.01)を使い、計算コストはゼロだが、曲率に対応できず、ジグザグや発散のおそれがある。正確な直線探索は、f(x_k + α p_k) が最小になる α を求め、二次形式なら解析的に求まるが、一般の関数では重い。不正確な直線探索(バックトラッキング)は、α = 1.0 から始めて Armijo 条件を満たすまで半分に縮める

(図は、diagram-designで作成)

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

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

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

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

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

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

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

  • 手法: 最初に大きな歩幅(例えば α=1.0\alpha = 1.0)を試し、条件(Armijo条件やWolfe条件など)を満たさなければ歩幅を半分(α←0.5α\alpha \leftarrow 0.5 \alpha)に縮めていくバックトラッキング(後戻りしながら歩幅を縮める方法)が主流です。
  • Armijo(アルミホ)条件: 「歩幅 α\alpha に比例して、目的関数が最低限これくらいは減少してほしい」という基準を定めた条件です。 f(xk+αpk)≤f(xk)+cα∇f(xk)Tpkf(x_k + \alpha p_k) \le f(x_k) + c \alpha \nabla f(x_k)^T p_k (ここで c∈(0,1)c \in (0, 1) はごく小さな定数)
テイラー展開による数式の意味

この式の右辺は、テイラー展開による一次近似(接線)の考え方がベースになっています。ある点 xkx_k から方向 pkp_k に歩幅 α\alpha だけ進んだ際の関数の値は、テイラー展開を用いると以下のように一次近似できます。

f(xk+αpk)≈f(xk)+α∇f(xk)Tpkf(x_k + \alpha p_k) \approx f(x_k) + \alpha \nabla f(x_k)^T p_k

降下方向(∇f(xk)Tpk<0\nabla f(x_k)^T p_k < 0)へ進む場合、第2項 α∇f(xk)Tpk\alpha \nabla f(x_k)^T p_k はマイナスの値となり、「接線に沿ってまっすぐ進んだ場合の理想的な予想減少量」を表します。 しかし実際の関数は曲がっているため、大きく進むと接線から上にズレてしまいます。そこで、「理想的な減少量の100%とは言わないが、せめてその cc 倍以上は確実に下がってほしい」という妥協ラインを設定したのがArmijo条件です。 これにより、「進みすぎて逆に坂を登り始めていないか」を監視する安全装置の役割を果たします。

探索方向に沿った関数の値 φ(α)=f(xk+αpk)\varphi(\alpha) = f(x_k + \alpha p_k) で描くと、Armijo 条件とバックトラッキングは次のようになります。

探索方向に沿った目的関数 φ(α) と、α = 0 での接線、その傾きを c 倍に緩めた Armijo の線の模式図。φ(α) が Armijo の線より下にある α が条件を満たす。バックトラッキングは α = 1 から試し、線を上回れば半分にして、下回った最初の α を採用する探索方向に沿った目的関数 φ(α) と、α = 0 での接線、その傾きを c 倍に緩めた Armijo の線の模式図。φ(α) が Armijo の線より下にある α が条件を満たす。バックトラッキングは α = 1 から試し、線を上回れば半分にして、下回った最初の α を採用する

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

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

方向によって傾きが大きく違う目的関数 f(x,y)=x2+10y2f(x, y) = x^2 + 10y^2 と、その勾配を定義し、等高線を描くコードです。

  • 目的関数の選び方: yy 方向の曲率(2 階微分)は 20 で、xx 方向の 2 の 10 倍です。等高線は横に細長い楕円になり、勾配の方向が最適解(原点)の方向からずれます。固定歩幅や最急降下法の弱点が見えやすい、最小の例です。最適解が原点だと分かっているので、到達した点の良し悪しも ff の値でそのまま比べられます。
  • 勾配: grad_f は ∇f=(2x,20y)\nabla f = (2x, 20y) です。最急降下法は pk=−∇f(xk)p_k = -\nabla f(x_k) の方向に進み、Armijo 条件の ∇f(xk)Tpk\nabla f(x_k)^T p_k の計算にも使います。
  • 等高線: 値の範囲が 0.1 から 1,000 まで広いので、np.logspace(-1, 3, 20) で対数の間隔に 20 本引き、原点の近くの細い楕円も見えるようにしています。日本語のラベルは japanize_matplotlib で表示します(pip install japanize-matplotlib が必要です)。

実行結果​

目的関数の等高線

等高線は、yy 方向に詰まった細長い楕円です。yy 方向に少し動くだけで値が大きく変わるため、同じ歩幅でも yy 方向には進みすぎやすくなります。

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

まず、固定の学習率(歩幅 α=0.085\alpha = 0.085)を用いた単純な最急降下法で探索を行います。この関数では、yy 方向の 1 回の更新が y←(1−20α) yy \leftarrow (1 - 20\alpha)\, y になるので、α\alpha が 2/20=0.12/20 = 0.1 を超えると yy の振れ幅が毎回大きくなり、発散します。

# 初期解の設定
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方向で大きく振動(ジグザグ)してしまう。")

# 参考:歩幅を変えて、30 回後の最適解からの距離を比べる
# y 方向の 1 回の更新は y ← (1 - 20α) y なので、α が 2/20 = 0.1 を超えると振動が大きくなっていく
for a_test in [0.05, 0.085, 0.1, 0.105]:
x_t = x_init.copy()
for _ in range(30):
x_t = x_t - a_test * grad_f(x_t)
print(f" α = {a_test:<5}: 30 回後の最適解からの距離 {np.linalg.norm(x_t):.4g}")

# 軌跡の可視化
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()

固定の歩幅で最急降下法を 30 回行い、軌跡と到達点を確かめるコードです。歩幅を変えたときの違いも比べます。

  • 初期点と回数: 初期点 (−8,3)(-8, 3) は、xx と yy の両方が最適解から離れた点です。30 回は、3 つの方法の軌跡を同じ回数で比べるための上限で、勾配の大きさが 10−410^{-4} より小さくなったら(ほぼ最適解に着いたら)途中で止めます。
  • 歩幅 0.085: yy 方向の発散の境目 0.1 に近い値です。境目に近いほど xx 方向には大きく進めますが、yy 方向には 1−20×0.085=−0.71 - 20 \times 0.085 = -0.7 倍ずつ、符号を変えながら(谷を飛び越えながら)縮みます。この関数で固定歩幅の収束が最も速くなる 2/(2+20)≈0.0912/(2 + 20) \approx 0.091 にも近く、固定歩幅としてはよく調整した値です。
  • 歩幅の比較: 0.05・0.085・0.1・0.105 で 30 回進め、最適解からの距離を比べます。0.1 を境に振る舞いが変わることを、数値で確かめるためです。

実行結果​

固定歩幅の反復回数: 30
到達した解: [-2.98835892e-02 6.76180209e-05]
❌ 課題: 歩幅の調整ができないため、y方向で大きく振動(ジグザグ)してしまう。
α = 0.05 : 30 回後の最適解からの距離 0.3391
α = 0.085: 30 回後の最適解からの距離 0.02988
α = 0.1 : 30 回後の最適解からの距離 3
α = 0.105: 30 回後の最適解からの距離 52.35

固定歩幅の探索軌跡

  • 歩幅 0.085: 30 回で (−0.030, 0.000068)(-0.030,\ 0.000068) に着きました。軌跡は、yy 方向の谷を飛び越えるたびに符号が変わるジグザグになっています。
  • 歩幅による違い: 0.05 では xx 方向の進みが遅く、30 回後でも距離は 0.339 です。0.1 では yy が +3+3 と −3-3 を行き来して縮まらず(距離 3)、0.105 では振れ幅が増えて距離 52.35 と発散しました。固定歩幅は、関数の曲がり具合(ここでは 0.1 という境目)を知らないと、適切な値を選べません。

歩幅ごとの 30 回後の距離を並べると、次のようになります。

固定歩幅で 30 回更新した後の、最適解からの距離。α = 0.05 は 0.3391、α = 0.085 は 0.02988、α = 0.1 は 3(y が +3 と −3 を行き来する)、α = 0.105 は 52.35(振れ幅が増えて発散する)。対数目盛りで示す固定歩幅で 30 回更新した後の、最適解からの距離。α = 0.05 は 0.3391、α = 0.085 は 0.02988、α = 0.1 は 3(y が +3 と −3 を行き来する)、α = 0.105 は 52.35(振れ幅が増えて発散する)。対数目盛りで示す

(図は、diagram-designで作成)

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

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

# バックトラッキング直線探索のパラメータ
c = 1e-4 # Armijo条件の許容定数(予想減少量に対する最低保証割合。Nocedal & Wright の教科書が挙げる典型的な値)
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

# 直線探索:毎回、歩幅 1 から試し、Armijo条件を満たすまで縮める(初期歩幅 1 は教科書の標準的な選び方)
alpha = 1.0
n_backtrack = 0

# 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 # 歩幅を半分にする(バックトラッキング)
n_backtrack += 1

# Armijo条件を満たす安全な歩幅 α が見つかったので、パラメータを更新
x_ls = x_ls + alpha * p
path_ls.append(x_ls.copy())
if i < 5:
print(f" {i + 1} 回目:歩幅 {alpha:.4f}({n_backtrack} 回縮めた)、f = {f(x_ls):.4f}")

print(f"直線探索の反復回数: {len(path_ls)-1}")
print(f"到達した解: {x_ls}")
print(f"到達した点での f の値: {f(x_ls):.3e}(固定歩幅は {f(x_fixed):.3e})")

# 軌跡の可視化
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) は ∇f(xk)Tpk\nabla f(x_k)^T p_k で、最急降下方向では −∥∇f∥2-\|\nabla f\|^2 の負の値です。これに α\alpha を掛けたものが、接線に沿って進んだときの減少量です。
  • Armijo 条件の確認: while の条件は、Armijo 条件が成り立たない(実際の値が、予想減少量の cc 倍すら下がっていない)ことです。成り立たない間は alpha *= rho で歩幅を半分にします。
  • 値の選び方: 初期の歩幅 1、c=10−4c = 10^{-4}、縮小率 0.5 は、Nocedal & Wright の教科書(Numerical Optimization)が挙げる標準的な値です。cc が小さいので、「少しでも下がれば採用」に近い緩い条件です。固定歩幅と違い、関数に合わせた値を選んでいません。
  • 途中の表示: 最初の 5 回について、採用した歩幅と縮めた回数を表示し、歩幅が毎回変わることを確かめます。

実行結果​

1 回目:歩幅 0.0625(4 回縮めた)、f = 54.6250
2 回目:歩幅 0.1250(3 回縮めた)、f = 40.2188
3 回目:歩幅 0.0625(4 回縮めた)、f = 21.8936
4 回目:歩幅 0.2500(2 回縮めた)、f = 17.9319
5 回目:歩幅 0.0625(4 回縮めた)、f = 4.8302
直線探索の反復回数: 30
到達した解: [-0.00314024 0.00083522]
到達した点での f の値: 1.684e-05(固定歩幅は 8.931e-04)

バックトラッキング直線探索の探索軌跡

  • 歩幅の決まり方: 1 回目は歩幅 1 から 4 回縮めて 0.0625 で、関数の値は 154 から 54.6 に下がりました。その後も 0.0625・0.125・0.25 と、位置によって違う歩幅が選ばれています。歩幅 1 のままでは yy 方向に大きく行き過ぎるので、Armijo 条件が「進みすぎ」を検知して縮めています。
  • 到達点: 30 回で f=1.68×10−5f = 1.68 \times 10^{-5} まで下がり、固定歩幅(8.93×10−48.93 \times 10^{-4})より小さくなりました。歩幅を手で調整していないのに、よく調整した固定歩幅と同程度以上に進めています。
  • ジグザグは残る: ただし、軌跡は固定歩幅と同じようにジグザグです。直線探索が決めるのは「どれだけ進むか」だけで、「どの方向に進むか」は最急降下方向のままだからです。

最初の 5 回の歩幅と f の値を表にすると、次のようになります。

バックトラッキング直線探索の最初の 5 回の更新。歩幅 1 から半分ずつ縮め、1 回目は 4 回縮めて 0.0625 で f = 54.6250(最初は約 154)、2 回目は 3 回縮めて 0.1250 で 40.2188、3 回目は 0.0625 で 21.8936、4 回目は 2 回縮めて 0.2500 で 17.9319、5 回目は 0.0625 で 4.8302。30 回で f は 1.684e-05 になり、固定歩幅の 8.931e-04 より小さいバックトラッキング直線探索の最初の 5 回の更新。歩幅 1 から半分ずつ縮め、1 回目は 4 回縮めて 0.0625 で f = 54.6250(最初は約 154)、2 回目は 3 回縮めて 0.1250 で 40.2188、3 回目は 0.0625 で 21.8936、4 回目は 2 回縮めて 0.2500 で 17.9319、5 回目は 0.0625 で 4.8302。30 回で f は 1.684e-05 になり、固定歩幅の 8.931e-04 より小さい

(図は、diagram-designで作成)

探索軌跡の可視化​

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

# 正確な直線探索:二次関数 f = x^T A x(A = diag(1, 10))では、最急降下方向に進むときの最適な歩幅が
# α = (g^T g) / (2 g^T A g) と式で求まる(f(x + αp) を α で微分して 0 とおく)
A = np.diag([1.0, 10.0])
x_ex = x_init.copy()
path_ex = [x_ex.copy()]
for i in range(30):
g = grad_f(x_ex)
if np.linalg.norm(g) < 1e-4:
break
alpha = (g @ g) / (2 * g @ A @ g)
x_ex = x_ex - alpha * g
path_ex.append(x_ex.copy())
print(f"正確な直線探索:反復回数 {len(path_ex) - 1}、f の値 {f(x_ex):.3e}")
print(f"バックトラッキング:反復回数 {len(path_ls) - 1}、f の値 {f(x_ls):.3e}")
print(f"固定歩幅:反復回数 {len(path_fixed) - 1}、f の値 {f(x_fixed):.3e}")

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

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(path_ex[:, 0], path_ex[:, 1], marker='^', color='green',
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()

3 つの方法の到達点と軌跡を比べるコードです。正確な直線探索も加え、歩幅を最も良く選んだ場合でもジグザグが残るかを確かめます。

  • 正確な直線探索: f=xTAxf = x^T A x(A=diag(1,10)A = \mathrm{diag}(1, 10))のような二次関数では、f(xk+αpk)f(x_k + \alpha p_k) を α\alpha で微分して 0 とおくと、最適な歩幅が α=gTg2 gTAg\alpha = \frac{g^T g}{2\, g^T A g}(g=∇f(xk)g = \nabla f(x_k))と式で求まります。一般の関数ではこの式が使えないので、バックトラッキングのような方法が使われます。
  • 配列への変換: 履歴のリストを np.array で 2 次元配列にし、[:, 0](xx 座標)と [:, 1](yy 座標)を取り出して描きます。

実行結果​

正確な直線探索:反復回数 23、f の値 1.742e-09
バックトラッキング:反復回数 30、f の値 1.684e-05
固定歩幅:反復回数 30、f の値 8.931e-04

固定歩幅・バックトラッキング・正確な直線探索の探索軌跡の比較

  • 正確な直線探索: 23 回で勾配が 10−410^{-4} より小さくなり、f=1.74×10−9f = 1.74 \times 10^{-9} まで下がりました。3 つの中で最も速く収束しています。
  • 3 つともジグザグ: それでも、緑の軌跡は直角に折れ曲がりながら進みます。正確な直線探索では、その方向で最小になる点で止まるので、次の勾配(次の方向)は今の方向と直交します。細長い楕円では、直交する方向を交互に進むことになり、ジグザグは避けられません。
  • 方向を変える手法へ: ジグザグをなくすには、方向そのものを変える必要があります。共役勾配法(CG) は、前の方向と「共役」な方向に進むことで、この 2 変数の二次関数なら 2 回で最適解に着きます。直線探索は、こうした方向の決め方と組み合わせて使います。

3つの決め方の最終的な f の値を並べると、次のようになります。

3 つの歩幅の決め方の結果。正確な直線探索は 23 回で勾配が 10^−4 より小さくなり、f = 1.742e-09。バックトラッキングは 30 回で 1.684e-05、固定歩幅は 30 回で 8.931e-04。直線探索は進む量を決めるだけで、方向は最急降下方向のままなので、どれもジグザグになる。方向を変えるのが共役勾配法3 つの歩幅の決め方の結果。正確な直線探索は 23 回で勾配が 10^−4 より小さくなり、f = 1.742e-09。バックトラッキングは 30 回で 1.684e-05、固定歩幅は 30 回で 8.931e-04。直線探索は進む量を決めるだけで、方向は最急降下方向のままなので、どれもジグザグになる。方向を変えるのが共役勾配法

(図は、diagram-designで作成)

まとめ​

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

  • できること: 固定の学習率では、関数の曲がり具合を知らないと発散する(今回は 0.1 を超えると発散)のに対し、直線探索はその場の地形に合わせて、関数が確実に下がる歩幅を自動で選びます。今回の例では、調整なしのバックトラッキングが、よく調整した固定歩幅より小さい値まで下がりました。

  • できないこと: 直線探索は歩幅を決めるだけで、方向は変えません。最急降下方向のままでは、正確な直線探索でもジグザグが残りました。

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

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

    • 共役勾配法(CG)では、二次形式の特性を活かした「正確な直線探索」で一発で歩幅を決定します。
    • TRPOなどの強化学習アルゴリズムでは、「KLダイバージェンス制約」と「目的関数の改善」の両方をチェックするバックトラッキング直線探索が、1 回の更新で方策が変わりすぎるのを防いでいます。

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

参考文献​

本記事の文章・構成の一部に生成AIを使用しています。