直線探索法（Line Search Methods）
概要
直線探索法は、最適化アルゴリズムにおいて探索方向が決定された後、最適なステップサイズを決定する手法です。効率的な直線探索は、最適化アルゴリズム全体の収束速度と安定性に大きく影響する重要な要素です。
基本概念
直線探索問題
点 から探索方向 に向かって移動する際の1次元最適化問題：
ここで：
- : 現在の点
- : 探索方向
- : ステップサイズ
- : 直線関数
減少方向の条件
探索方向 が減少方向であるための必要条件：
完全直線探索（Exact Line Search）
定義
直線関数 の正確な最小値を求める手法：
最適性条件
が最小点であるための必要条件：
実装例
黄金分割探索
import numpy as np
def golden_section_search(phi, a, b, tol=1e-6, max_iter=100):
"""
黄金分割探索による1次元最適化
Parameters:
phi: 目的関数
a, b: 探索区間 [a, b]
tol: 許容誤差
max_iter: 最大反復回数
"""
golden_ratio = (1 + np.sqrt(5)) / 2
inv_golden = 1 / golden_ratio
# 初期点の設定
x1 = a + (1 - inv_golden) * (b - a)
x2 = a + inv_golden * (b - a)
f1 = phi(x1)
f2 = phi(x2)
history = {'iterations': [], 'intervals': [], 'values': []}
for k in range(max_iter):
history['iterations'].append(k)
history['intervals'].append([a, b])
history['values'].append([f1, f2])
# 収束判定
if abs(b - a) < tol:
break
if f1 < f2:
b = x2
x2 = x1
f2 = f1
x1 = a + (1 - inv_golden) * (b - a)
f1 = phi(x1)
else:
a = x1
x1 = x2
f1 = f2
x2 = a + inv_golden * (b - a)
f2 = phi(x2)
optimal_point = (a + b) / 2
return optimal_point, phi(optimal_point), history
def parabolic_interpolation(phi, a, b, c, tol=1e-6, max_iter=50):
"""
放物線補間による1次元最適化
Parameters:
phi: 目的関数
a, b, c: 3点 (a < b < c)
"""
fa, fb, fc = phi(a), phi(b), phi(c)
for k in range(max_iter):
# 放物線補間による新しい点
denom = 2 * ((b - a) * (fb - fc) - (b - c) * (fb - fa))
if abs(denom) < 1e-12:
break
x_new = b - ((b - a)**2 * (fb - fc) - (b - c)**2 * (fb - fa)) / denom
# 区間チェック
if x_new <= a or x_new >= c:
break
f_new = phi(x_new)
# 収束判定
if abs(x_new - b) < tol:
return x_new, f_new
# 区間の更新
if x_new < b:
if f_new < fb:
c, fc = b, fb
b, fb = x_new, f_new
else:
a, fa = x_new, f_new
else:
if f_new < fb:
a, fa = b, fb
b, fb = x_new, f_new
else:
c, fc = x_new, f_new
return b, fb
三次補間法
def cubic_interpolation(phi, dphi, alpha0, alpha1, tol=1e-6):
"""
三次補間による直線探索
Parameters:
phi: 目的関数
dphi: 目的関数の導関数
alpha0, alpha1: 2つの点
"""
f0, f1 = phi(alpha0), phi(alpha1)
df0, df1 = dphi(alpha0), dphi(alpha1)
# 三次多項式の係数を計算
d1 = df0 + df1 - 3 * (f0 - f1) / (alpha0 - alpha1)
d2 = np.sqrt(d1**2 - df0 * df1)
if alpha1 > alpha0:
alpha_new = alpha1 - (alpha1 - alpha0) * (df1 + d2 - d1) / (df1 - df0 + 2*d2)
else:
alpha_new = alpha0 - (alpha0 - alpha1) * (df0 + d2 - d1) / (df0 - df1 + 2*d2)
return alpha_new
不完全直線探索（Inexact Line Search）
計算効率を重視し、十分な改善を示すステップサイズを求める手法です。
Armijo条件（十分減少条件）
ここで、（通常 ）
幾何学的意味: 関数値が直線の十分下方にあることを保証
Wolfe条件
Armijo条件に加えて曲率条件を追加：
ここで、（通常 ）
意味: ステップサイズが小さすぎることを防ぐ
Strong Wolfe条件
曲率条件を強化：
実装例
def armijo_backtracking(f, grad_f, x, d, alpha_init=1.0, c1=1e-4, rho=0.5, max_iter=50):
"""
Armijo条件によるバックトラッキング直線探索
Parameters:
f: 目的関数
grad_f: 勾配関数
x: 現在の点
d: 探索方向
alpha_init: 初期ステップサイズ
c1: Armijo定数
rho: 減少率
"""
alpha = alpha_init
f_x = f(x)
grad_x = grad_f(x)
# 減少方向のチェック
directional_derivative = np.dot(grad_x, d)
if directional_derivative >= 0:
raise ValueError("探索方向が減少方向ではありません")
armijo_threshold = c1 * directional_derivative
history = {'alpha_values': [], 'f_values': [], 'armijo_values': []}
for i in range(max_iter):
x_new = x + alpha * d
f_new = f(x_new)
# 履歴の記録
history['alpha_values'].append(alpha)
history['f_values'].append(f_new)
history['armijo_values'].append(f_x + alpha * armijo_threshold)
# Armijo条件のチェック
if f_new <= f_x + alpha * armijo_threshold:
return alpha, x_new, history
alpha *= rho
# 収束しなかった場合
print(f"警告: Armijo直線探索が{max_iter}回で収束しませんでした")
return alpha, x + alpha * d, history
def wolfe_line_search(f, grad_f, x, d, alpha_init=1.0, c1=1e-4, c2=0.9, max_iter=50):
"""
Wolfe条件による直線探索
"""
def phi(alpha):
return f(x + alpha * d)
def dphi(alpha):
return np.dot(grad_f(x + alpha * d), d)
alpha_lo, alpha_hi = 0, None
alpha = alpha_init
phi_0 = phi(0)
dphi_0 = dphi(0)
history = {'alpha_values': [], 'phi_values': [], 'dphi_values': []}
for i in range(max_iter):
phi_alpha = phi(alpha)
dphi_alpha = dphi(alpha)
history['alpha_values'].append(alpha)
history['phi_values'].append(phi_alpha)
history['dphi_values'].append(dphi_alpha)
# Armijo条件をチェック
if phi_alpha > phi_0 + c1 * alpha * dphi_0:
alpha_hi = alpha
alpha = zoom(phi, dphi, alpha_lo, alpha_hi, phi_0, dphi_0, c1, c2)
break
# Wolfe条件をチェック
if abs(dphi_alpha) <= -c2 * dphi_0:
return alpha, x + alpha * d, history
if dphi_alpha >= 0:
alpha_hi = alpha
alpha = zoom(phi, dphi, alpha_lo, alpha_hi, phi_0, dphi_0, c1, c2)
break
alpha_lo = alpha
if alpha_hi is None:
alpha *= 2
else:
alpha = (alpha_lo + alpha_hi) / 2
return alpha, x + alpha * d, history
def zoom(phi, dphi, alpha_lo, alpha_hi, phi_0, dphi_0, c1, c2, max_iter=20):
"""Wolfe条件のzoomフェーズ"""
for i in range(max_iter):
# 二分法または補間
alpha = (alpha_lo + alpha_hi) / 2
phi_alpha = phi(alpha)
dphi_alpha = dphi(alpha)
# Armijo条件をチェック
if phi_alpha > phi_0 + c1 * alpha * dphi_0 or phi_alpha >= phi(alpha_lo):
alpha_hi = alpha
else:
# Wolfe条件をチェック
if abs(dphi_alpha) <= -c2 * dphi_0:
return alpha
if dphi_alpha * (alpha_hi - alpha_lo) >= 0:
alpha_hi = alpha_lo
alpha_lo = alpha
return alpha
def strong_wolfe_line_search(f, grad_f, x, d, alpha_init=1.0, c1=1e-4, c2=0.1):
"""Strong Wolfe条件による直線探索"""
def phi(alpha):
return f(x + alpha * d)
def dphi(alpha):
return np.dot(grad_f(x + alpha * d), d)
alpha = alpha_init
phi_0 = phi(0)
dphi_0 = dphi(0)
alpha_prev = 0
phi_prev = phi_0
max_iter = 50
for i in range(1, max_iter + 1):
phi_alpha = phi(alpha)
# Armijo条件またはphi値の増加をチェック
if (phi_alpha > phi_0 + c1 * alpha * dphi_0) or \
(i > 1 and phi_alpha >= phi_prev):
return zoom_strong_wolfe(phi, dphi, alpha_prev, alpha,
phi_0, dphi_0, c1, c2)
dphi_alpha = dphi(alpha)
# Strong Wolfe条件をチェック
if abs(dphi_alpha) <= -c2 * dphi_0:
return alpha
if dphi_alpha >= 0:
return zoom_strong_wolfe(phi, dphi, alpha, alpha_prev,
phi_0, dphi_0, c1, c2)
alpha_prev = alpha
phi_prev = phi_alpha
alpha *= 2 # αを倍増
return alpha
def zoom_strong_wolfe(phi, dphi, alpha_lo, alpha_hi, phi_0, dphi_0, c1, c2):
"""Strong Wolfe条件のzoomフェーズ"""
max_iter = 20
for i in range(max_iter):
# 補間または二分法でαを選択
alpha = (alpha_lo + alpha_hi) / 2
phi_alpha = phi(alpha)
# Armijo条件またはphi値の比較
if (phi_alpha > phi_0 + c1 * alpha * dphi_0) or \
(phi_alpha >= phi(alpha_lo)):
alpha_hi = alpha
else:
dphi_alpha = dphi(alpha)
# Strong Wolfe条件をチェック
if abs(dphi_alpha) <= -c2 * dphi_0:
return alpha
if dphi_alpha * (alpha_hi - alpha_lo) >= 0:
alpha_hi = alpha_lo
alpha_lo = alpha
return alpha
More-Thuente直線探索
高品質な直線探索手法として広く使用される手法です。
def more_thuente_line_search(f, grad_f, x, d, alpha_init=1.0,
c1=1e-4, c2=0.9, xtol=1e-12, max_iter=50):
"""
More-Thuente直線探索アルゴリズム
高精度で安定した直線探索手法
"""
def phi(alpha):
return f(x + alpha * d)
def dphi(alpha):
return np.dot(grad_f(x + alpha * d), d)
# 初期化
alpha = alpha_init
phi_0 = phi(0)
dphi_0 = dphi(0)
finit = phi_0
ginit = dphi_0
gtest = c1 * ginit
width = 1e20
width1 = width / 2
# ブラケティングフェーズ
stx = 0.0
fx = finit
gx = ginit
sty = 0.0
fy = finit
gy = ginit
stmin = 0.0
stmax = alpha + 4.0 * alpha
stage1 = True
for iteration in range(max_iter):
fxm = fx - stx * gtest
fym = fy - sty * gtest
gxm = gx - gtest
gym = gy - gtest
# 更新されたTrialステップを計算
if stage1 and f(x + alpha * d) <= finit + alpha * gtest and \
dphi(alpha) < min(c2, 0.9) * ginit:
stage1 = False
# 3次補間による新しいα値の計算
if stage1:
alpha = cubic_step(stx, fx, gx, sty, fy, gy, alpha,
f(x + alpha * d), dphi(alpha))
else:
alpha = cubic_step(stx, fxm, gxm, sty, fym, gym, alpha,
f(x + alpha * d) - alpha * gtest,
dphi(alpha) - gtest)
# 収束判定
if abs(alpha - stx) < xtol * max(1.0, abs(alpha)):
break
# Strong Wolfe条件のチェック
f_alpha = f(x + alpha * d)
g_alpha = dphi(alpha)
if (f_alpha <= finit + c1 * alpha * ginit) and \
(abs(g_alpha) <= -c2 * ginit):
return alpha, x + alpha * d
# 区間の更新
if f_alpha > finit + alpha * gtest or f_alpha >= fx:
sty, fy, gy = stx, fx, gx
else:
if g_alpha * (stx - sty) >= 0:
sty, fy, gy = stx, fx, gx
stx, fx, gx = alpha, f_alpha, g_alpha
return alpha, x + alpha * d
def cubic_step(x1, f1, g1, x2, f2, g2, x3, f3, g3):
"""三次補間によるステップサイズ計算"""
# 三次多項式の係数を計算
d1 = g1 + g2 - 3 * (f1 - f2) / (x1 - x2)
d2_squared = d1**2 - g1 * g2
if d2_squared < 0:
return (x1 + x2) / 2 # 安全な値を返す
d2 = np.sqrt(d2_squared)
if x2 > x1:
return x2 - (x2 - x1) * (g2 + d2 - d1) / (g2 - g1 + 2 * d2)
else:
return x1 - (x1 - x2) * (g1 + d2 - d1) / (g1 - g2 + 2 * d2)
直線探索の可視化と性能比較
import matplotlib.pyplot as plt
def visualize_line_search_methods():
"""直線探索手法の可視化と比較"""
# テスト関数の定義
def test_function(x):
return x[0]**4 - 2*x[0]**2 + x[1]**2 + 1
def test_gradient(x):
return np.array([4*x[0]**3 - 4*x[0], 2*x[1]])
# 現在の点と探索方向
x_current = np.array([2.0, 1.0])
direction = -test_gradient(x_current) # 最急降下方向
direction = direction / np.linalg.norm(direction) # 正規化
# 直線関数の定義
def phi(alpha):
return test_function(x_current + alpha * direction)
def dphi(alpha):
x_new = x_current + alpha * direction
return np.dot(test_gradient(x_new), direction)
# 各手法の実行
alpha_range = np.linspace(0, 2, 1000)
phi_values = [phi(alpha) for alpha in alpha_range]
plt.figure(figsize=(15, 10))
# 1. 直線関数の可視化
plt.subplot(2, 3, 1)
plt.plot(alpha_range, phi_values, 'b-', linewidth=2, label='φ(α)')
# 黄金分割探索
alpha_golden, _, golden_history = golden_section_search(phi, 0, 2)
plt.axvline(x=alpha_golden, color='gold', linestyle='--',
label=f'黄金分割 (α={alpha_golden:.3f})')
plt.xlabel('α')
plt.ylabel('φ(α)')
plt.title('直線関数と最適ステップサイズ')
plt.legend()
plt.grid(True)
# 2. Armijo条件の可視化
plt.subplot(2, 3, 2)
plt.plot(alpha_range, phi_values, 'b-', linewidth=2, label='φ(α)')
# Armijoバックトラッキング
alpha_armijo, _, armijo_history = armijo_backtracking(
test_function, test_gradient, x_current, direction)
# Armijo直線の描画
phi_0 = phi(0)
dphi_0 = dphi(0)
armijo_line = phi_0 + 0.0001 * alpha_range * dphi_0
plt.plot(alpha_range, armijo_line, 'r--', alpha=0.7, label='Armijo線')
# 各反復点の描画
for i, alpha in enumerate(armijo_history['alpha_values']):
color = 'red' if i == len(armijo_history['alpha_values'])-1 else 'orange'
plt.plot(alpha, phi(alpha), 'o', color=color, markersize=8)
plt.axvline(x=alpha_armijo, color='red', linestyle='-',
label=f'Armijo (α={alpha_armijo:.3f})')
plt.xlabel('α')
plt.ylabel('φ(α)')
plt.title('Armijo条件による直線探索')
plt.legend()
plt.grid(True)
# 3. Wolfe条件の可視化
plt.subplot(2, 3, 3)
plt.plot(alpha_range, phi_values, 'b-', linewidth=2, label='φ(α)')
# Wolfe直線探索
try:
alpha_wolfe, _, wolfe_history = wolfe_line_search(
test_function, test_gradient, x_current, direction)
plt.axvline(x=alpha_wolfe, color='green', linestyle='-',
label=f'Wolfe (α={alpha_wolfe:.3f})')
# 曲率条件の可視化
dphi_range = [dphi(alpha) for alpha in alpha_range]
plt.subplot(2, 3, 6)
plt.plot(alpha_range, dphi_range, 'g-', label="φ'(α)")
plt.axhline(y=0.9*dphi_0, color='purple', linestyle='--',
label='曲率条件線')
plt.axvline(x=alpha_wolfe, color='green', linestyle='-',
label=f'Wolfe (α={alpha_wolfe:.3f})')
plt.xlabel('α')
plt.ylabel("φ'(α)")
plt.title('曲率条件')
plt.legend()
plt.grid(True)
except:
print("Wolfe直線探索でエラーが発生しました")
plt.xlabel('α')
plt.ylabel('φ(α)')
plt.title('Wolfe条件による直線探索')
plt.legend()
plt.grid(True)
# 4. 収束比較
plt.subplot(2, 3, 4)
methods = ['Golden Section', 'Armijo', 'Wolfe']
step_sizes = [alpha_golden, alpha_armijo, alpha_wolfe if 'alpha_wolfe' in locals() else 0]
function_values = [phi(alpha) for alpha in step_sizes]
plt.bar(methods, function_values, color=['gold', 'red', 'green'], alpha=0.7)
plt.ylabel('φ(α)')
plt.title('各手法による目的関数値')
plt.xticks(rotation=45)
# 5. 反復履歴の比較
plt.subplot(2, 3, 5)
# 黄金分割の収束履歴
golden_intervals = [interval[1] - interval[0] for interval in golden_history['intervals']]
plt.semilogy(golden_intervals, 'o-', color='gold', label='黄金分割')
# Armijoの収束履歴
armijo_steps = [abs(alpha - alpha_armijo) for alpha in armijo_history['alpha_values']]
plt.semilogy(range(len(armijo_steps)), armijo_steps, 's-', color='red', label='Armijo')
plt.xlabel('反復回数')
plt.ylabel('誤差 (対数スケール)')
plt.title('収束履歴の比較')
plt.legend()
plt.grid(True)
plt.tight_layout()
plt.show()
# 結果の要約
print("=== 直線探索結果の比較 ===")
print(f"黄金分割探索: α = {alpha_golden:.6f}, φ(α) = {phi(alpha_golden):.6f}")
print(f"Armijo探索: α = {alpha_armijo:.6f}, φ(α) = {phi(alpha_armijo):.6f}")
if 'alpha_wolfe' in locals():
print(f"Wolfe探索: α = {alpha_wolfe:.6f}, φ(α) = {phi(alpha_wolfe):.6f}")
def performance_comparison():
"""各直線探索手法の性能比較"""
# 様々なテスト関数での比較
test_functions = [
{
'name': 'Rosenbrock',
'f': lambda x: 100*(x[1] - x[0]**2)**2 + (1 - x[0])**2,
'grad': lambda x: np.array([-400*x[0]*(x[1] - x[0]**2) - 2*(1 - x[0]),
200*(x[1] - x[0]**2)])
},
{
'name': 'Beale',
'f': lambda x: (1.5 - x[0] + x[0]*x[1])**2 + (2.25 - x[0] + x[0]*x[1]**2)**2 + (2.625 - x[0] + x[0]*x[1]**3)**2,
'grad': lambda x: np.array([2*(1.5 - x[0] + x[0]*x[1])*(x[1] - 1) +
2*(2.25 - x[0] + x[0]*x[1]**2)*(x[1]**2 - 1) +
2*(2.625 - x[0] + x[0]*x[1]**3)*(x[1]**3 - 1),
2*(1.5 - x[0] + x[0]*x[1])*x[0] +
2*(2.25 - x[0] + x[0]*x[1]**2)*2*x[0]*x[1] +
2*(2.625 - x[0] + x[0]*x[1]**3)*3*x[0]*x[1]**2])
}
]
methods = ['Golden Section', 'Armijo', 'Wolfe', 'Strong Wolfe']
results = []
for func_info in test_functions:
f = func_info['f']
grad_f = func_info['grad']
x_start = np.array([1.5, 1.5])
print(f"\n=== {func_info['name']} 関数での比較 ===")
direction = -grad_f(x_start)
direction = direction / np.linalg.norm(direction)
def phi(alpha):
return f(x_start + alpha * direction)
# 各手法の実行と時間測定
import time
method_results = {}
# 黄金分割探索
start_time = time.time()
alpha_golden, f_golden, _ = golden_section_search(phi, 0, 2)
time_golden = time.time() - start_time
method_results['Golden Section'] = {'alpha': alpha_golden, 'value': f_golden, 'time': time_golden}
# Armijo探索
start_time = time.time()
alpha_armijo, _, _ = armijo_backtracking(f, grad_f, x_start, direction)
time_armijo = time.time() - start_time
method_results['Armijo'] = {'alpha': alpha_armijo, 'value': phi(alpha_armijo), 'time': time_armijo}
# Wolfe探索
try:
start_time = time.time()
alpha_wolfe, _, _ = wolfe_line_search(f, grad_f, x_start, direction)
time_wolfe = time.time() - start_time
method_results['Wolfe'] = {'alpha': alpha_wolfe, 'value': phi(alpha_wolfe), 'time': time_wolfe}
except:
method_results['Wolfe'] = {'alpha': 0, 'value': float('inf'), 'time': float('inf')}
# Strong Wolfe探索
try:
start_time = time.time()
alpha_strong_wolfe = strong_wolfe_line_search(f, grad_f, x_start, direction)
time_strong_wolfe = time.time() - start_time
method_results['Strong Wolfe'] = {'alpha': alpha_strong_wolfe, 'value': phi(alpha_strong_wolfe), 'time': time_strong_wolfe}
except:
method_results['Strong Wolfe'] = {'alpha': 0, 'value': float('inf'), 'time': float('inf')}
# 結果の表示
for method in methods:
if method in method_results:
result = method_results[method]
print(f"{method:15}: α = {result['alpha']:.6f}, f = {result['value']:.6f}, 時間 = {result['time']:.6f}秒")
results.append((func_info['name'], method_results))
return results
# 実行例
if __name__ == "__main__":
print("=== 直線探索手法の可視化 ===")
visualize_line_search_methods()
print("\n=== 性能比較 ===")
performance_results = performance_comparison()
特殊な場合の処理
非凸関数での直線探索
def robust_line_search(f, grad_f, x, d, alpha_max=10.0,
safeguard_factor=0.1, max_backtracks=20):
"""
非凸関数に対する堅牢な直線探索
"""
# 初期ステップサイズの適応的決定
grad_norm = np.linalg.norm(grad_f(x))
if grad_norm > 1e-6:
alpha_init = min(1.0, 1.0 / grad_norm)
else:
alpha_init = 1.0
# セーフガード付きArmijo探索
alpha = min(alpha_init, alpha_max)
f_x = f(x)
grad_x = grad_f(x)
descent_condition = np.dot(grad_x, d)
if descent_condition >= 0:
# 減少方向でない場合の処理
print("警告: 減少方向ではありません。勾配方向に修正します。")
d = -grad_x / np.linalg.norm(grad_x)
descent_condition = np.dot(grad_x, d)
c1 = 1e-4
rho = 0.5
for i in range(max_backtracks):
x_new = x + alpha * d
f_new = f(x_new)
# Armijo条件のチェック
if f_new <= f_x + c1 * alpha * descent_condition:
return alpha, x_new
# 極端に小さなステップサイズの回避
if alpha < safeguard_factor * alpha_init:
print("警告: ステップサイズが極小になりました。強制的に小さなステップを採用します。")
alpha = safeguard_factor * alpha_init
return alpha, x + alpha * d
alpha *= rho
# 最悪の場合の処理
alpha = safeguard_factor * alpha_init
return alpha, x + alpha * d
制約付き問題での直線探索
def projected_line_search(f, grad_f, project_func, x, d, alpha_init=1.0):
"""
制約付き問題での射影付き直線探索
Parameters:
project_func: 実行可能領域への射影関数
"""
alpha = alpha_init
f_x = f(x)
while alpha > 1e-12:
# 新しい点を計算し、実行可能領域に射影
x_trial = x + alpha * d
x_new = project_func(x_trial)
# 十分減少条件のチェック（修正版）
actual_direction = x_new - x
if np.linalg.norm(actual_direction) > 0:
predicted_decrease = np.dot(grad_f(x), actual_direction)
actual_decrease = f_x - f(x_new)
if actual_decrease >= 0.1 * abs(predicted_decrease):
return alpha, x_new
alpha *= 0.5
# 射影のみを返す
return 0, project_func(x)
まとめ
直線探索法の主な特徴：
- 完全 vs 不完全: 精度と計算効率のトレードオフ
- Armijo条件: 十分な関数値減少の保証
- Wolfe条件: ステップサイズの適切性の保証
- 実装の重要性: 最適化アルゴリズム全体の性能に大きく影響
手法選択の指針
- 高精度が必要: 黄金分割探索、三次補間
- 計算効率重視: Armijoバックトラッキング
- 汎用性重視: Wolfe条件
- 堅牢性重視: More-Thuente法
実用的考慮事項
- 初期ステップサイズ: 問題の性質に応じた適応的設定
- パラメータ調整: の適切な選択
- 数値的安定性: 極端な値の処理
- 収束判定: 複数の基準の組み合わせ
実装のポイント
直線探索を実装する際は、数値的安定性と計算効率のバランスを考慮してください。特に、減少方向の確認、適切な初期ステップサイズの設定、そして堅牢な収束判定が重要です。
参考文献
- Nocedal, J., & Wright, S. J. (2006). Numerical Optimization. Springer.
- More, J. J., & Thuente, D. J. (1994). Line search algorithms with guaranteed sufficient decrease. ACM Transactions on Mathematical Software.
- Fletcher, R. (2013). Practical Methods of Optimization. John Wiley & Sons.
- Wolfe, P. (1969). Convergence conditions for ascent methods. SIAM Review.