nonlinear-solvers

非線形ソルバー

目的

根探し、最適化、最小二乗問題に対して、非線形ソルバーの選択、大域化戦略の設定、収束の診断を行う汎用的なワークフローを提供します。

要件

• Python 3.10+
• NumPy（ヤコビアンの診断用）
• SciPy（高度な解析用、任意）

収集する入力

入力	説明	例
問題の種類	根探し、最適化、最小二乗	root-finding
問題の規模	未知数の数	n = 10000
ヤコビアンの利用可否	解析的、有限差分、利用不可	analytic
ヤコビアンの計算コスト	計算が安価か高価か	expensive
制約	なし、境界、等式、不等式	none
滑らかさ	目的関数／残差は滑らかか	yes
残差の履歴	残差ノルムの列	1,0.1,0.01,...

選択の指針

ソルバー選択フローチャート

Is Jacobian available and cheap?
├── YES → Problem size?
│   ├── Small (n < 1000) → Newton (full)
│   └── Large (n ≥ 1000) → Newton-Krylov
└── NO → Is objective smooth?
    ├── YES → Memory limited?
    │   ├── YES → L-BFGS or Broyden
    │   └── NO → BFGS
    └── NO → Anderson acceleration or Picard

クイックリファレンス

問題の種類	第一候補	代替候補	大域化
小規模な根探し	Newton	Broyden	ラインサーチ
大規模な根探し	Newton-Krylov	Anderson	信頼領域
最適化	L-BFGS	BFGS	Wolfe ラインサーチ
最小二乗	Levenberg-Marquardt	Gauss-Newton	信頼領域
境界制約付き	L-BFGS-B	信頼領域リフレクティブ法	射影法

スクリプトの出力（JSON フィールド）

スクリプト	主な出力
scripts/solver_selector.py	recommended、alternatives、notes
scripts/convergence_analyzer.py	converged、convergence_type、estimated_rate、diagnosis
scripts/jacobian_diagnostics.py	condition_number、jacobian_quality、rank_deficient
scripts/globalization_advisor.py	strategy、line_search_type、trust_region_type、parameters
scripts/residual_monitor.py	patterns_detected、alerts、recommendations
scripts/step_quality.py	ratio、step_quality、accept_step、trust_radius_action

ワークフロー

1. 問題の特性を把握する - 種類、規模、ヤコビアンの利用可否を確認します
2. ソルバーを選択する - scripts/solver_selector.py を実行します
3. 大域化戦略を選ぶ - scripts/globalization_advisor.py を実行します
4. ヤコビアンを解析する - 利用可能な場合は、scripts/jacobian_diagnostics.py を実行します
5. 残差を監視する - 求解中に scripts/residual_monitor.py を使用します
6. 収束を解析する - scripts/convergence_analyzer.py を実行します
7. ステップを評価する - 信頼領域法では scripts/step_quality.py を使用します

会話形式のワークフロー例

ユーザー：フェーズフィールドシミュレーションの Newton ソルバーの収束が非常に遅いです。50 回反復した後も、残差は 1 から 0.1 にしか下がりません。

エージェントのワークフロー：

1. 収束を解析します：

   python3 scripts/convergence_analyzer.py --residuals 1,0.8,0.6,0.5,0.4,0.3,0.2,0.15,0.12,0.1 --json
   

2. 大域化戦略を確認します：

   python3 scripts/globalization_advisor.py --problem-type root-finding --jacobian-quality ill-conditioned --previous-failures 0 --json
   

3. 推奨：Levenberg-Marquardt 正則化を用いた信頼領域法に切り替えるか、より優れた前処理を適用した Newton-Krylov を使用します。

求解前チェックリスト

• 問題の種類を確認する（根探し、最適化、最小二乗）
• ヤコビアンの利用可否と計算コストを評価する
• 初期値の品質を確認する
• 適切な許容誤差を設定する
• 大域化戦略を選択する
• 収束を監視する準備をする

CLI の例

# Select solver for large unconstrained optimization
python3 scripts/solver_selector.py --size 50000 --smooth --memory-limited --json

# Select solver for a small nonlinear least-squares (data-fitting) problem
python3 scripts/solver_selector.py --problem-type least-squares --size 6 --jacobian-available --smooth --json

# Analyze convergence from residual history
python3 scripts/convergence_analyzer.py --residuals 1,0.1,0.01,0.001,0.0001 --tolerance 1e-6 --json

# Diagnose Jacobian quality
python3 scripts/jacobian_diagnostics.py --matrix jacobian.txt --json

# Get globalization recommendation
python3 scripts/globalization_advisor.py --problem-type optimization --jacobian-quality good --json

# Globalization for a distant initial guess (favors trust region)
python3 scripts/globalization_advisor.py --problem-type root-finding --jacobian-quality good --far-from-solution --json

# Monitor residual patterns
python3 scripts/residual_monitor.py --residuals 1,0.8,0.9,0.7,0.75,0.6 --target-tolerance 1e-8 --json

# Evaluate step quality for trust region
python3 scripts/step_quality.py --predicted-reduction 0.5 --actual-reduction 0.4 --step-norm 0.8 --gradient-norm 1.0 --trust-radius 1.0 --json

エラー処理

エラー	原因	解決方法
problem_size must be positive	サイズが無効です	問題の次元を確認してください
problem_size (...) exceeds maximum (...)	サイズが上限の10 billionを超えています	単位／値を再確認してください
constraint_type must be one of...	制約が不明です	次のいずれかを使用してください：none、bound、equality、inequality
problem_type must be one of...	問題の種類が不明です	次のいずれかを使用してください：root-finding、optimization、least-squares
residuals must be non-negative	残差データが無効です	残差の計算を確認してください
residuals must be finite	残差データにNaN/Infが含まれています	残差履歴をサニタイズしてください
residual list length (...) exceeds limit (...)	エントリ数が100,000を超えています	履歴をダウンサンプリングしてください
Matrix file not found	パスが無効です	ヤコビアンファイルが存在することを確認してください
Matrix file exceeds size limit ...	行列ファイルが大きすぎます	より小さい／疎な行列を使用してください

解釈の指針

収束の種類

種類	意味	対応
quadratic	最適なNewton法（次数 p ≈ 2）	続行してください。解に近づいています
superlinear	比が0に向かって減少しています（1 < p < 2）。準Newton法が機能しています	停滞がないか監視してください
linear	収縮比が一定です（p ≈ 1）。小さな一定比は高速な線形収束であり、超線形収束ではありません	前処理で改善できる可能性があります
sublinear	遅すぎます（比 → 1）	方法または定式化を変更してください
stagnated	進展がありません	ヤコビアンと前処理を確認してください
diverged	残差が増加しています	大域化を追加し、ヤコビアンを確認してください

ヤコビアンの品質

品質	条件数	対応
good	< 10⁶	標準的なNewton法が機能します
moderately-conditioned	10⁶ - 10¹⁰	スケーリングを検討してください
ill-conditioned	> 10¹⁰	正則化を使用してください
near-singular	∞	再定式化するか、LMを使用してください

ステップの品質（信頼領域）

比率 ρ	品質	信頼半径
ρ < 0	非常に低い	積極的に縮小します
ρ < 0.25	境界的	縮小します
0.25 ≤ ρ < 0.75	良好	維持します
ρ ≥ 0.75	非常に良好	境界に達している場合は拡大します

検証チェックリスト

次の具体的な成果物が記録されるまでは、「解決済み」という主張を信用しないでください。

• 残差ノルムの履歴全体を記録し、convergence_analyzer.py --residuals <history>を実行しました。convergence_typeとestimated_rateを記録し、既定の1e-10ではなく、実際のソルバー許容誤差に照らしてconverged: trueであることを確認しました。
• 残差の系列が単調減少していることを確認するか、residual_monitor.pyに渡しました。patterns_detectedを記録し、許容誤差を上回っている間に、これにdiverging、oscillating、plateau、slow_convergenceが含まれていないことを確認しました。
• ヤコビアンを利用できる場合は、jacobian_diagnostics.py --matrix J.txtを実行し、condition_numberとjacobian_qualityを記録しました。解析的ヤコビアンの場合は、--finite-diff-matrixを渡し、finite_diff_errorが約1e-2未満であること（「Large discrepancy」という注記がないこと）を確認しました。
• jacobian_diagnostics.pyのrank_deficientがfalseであることを確認しました（または、ランク落ち／ほぼ特異なヤコビアンが想定され、Levenberg-Marquardt正則化を使用している理由を記録しました）。
• 信頼領域法による求解では、step_quality.pyを使って採用されたステップを評価し、縮小ratioを記録しました。採用されたステップのratio >= 0.25（very_poor／poorではない）を確認し、trust_radius_actionが記録されたρと一致することを確認しました。
• 実際に使用したソルバーと大域化手法を記録し、提示された問題の種類、サイズ、ヤコビアンの品質に対するsolver_selector.pyおよびglobalization_advisor.pyの推奨と一致することを確認しました（例：サイズが大きくヤコビアンの計算コストが高い場合 → Newton-Krylov、最小二乗法 → Levenberg-Marquardt信頼領域法）。
• 許容誤差、初期推定値、または前処理を変更した後、収束を再確認しました。収束の種類は変化する場合がある（例：二次収束 → 線形収束／停滞）ため、決めつけずに再分類する必要があります。

よくある落とし穴と誤った理由づけ

ありがちな近道	なぜ間違っているのか／何をすべきか
「残差比は小さな定数（約 0.1）なので、超線形収束しています。」	定数の収縮比は線形収束であり、超線形収束ではありません。convergence_analyzer.py はこれを linear（「fast linear」と注記）として報告します。超線形収束には、比がゼロに近づく必要があります（次数 p > 1.2）。比が一定のままなのに、ニュートン法相当の収束だと主張しないでください。
「エラーなしで停止したので、ソルバーは収束しました。」	実行の完了は収束を意味しません。convergence_analyzer.py／residual_monitor.py の converged を実際の許容誤差と照らして確認してください。stagnated や plateau という結果も「停止」しますが、f(x)=0 は解けていません。
「2 回の反復で減少しているようなので、収束率は問題ありません。」	次数の推定には、厳密に減少する正の残差が少なくとも 3 つ必要です。それより少ない場合、convergence_analyzer.py は unknown を返すか、収束率のみで判断します。収束の種類を述べる前に、反復回数を増やしてください。
「解析的ヤコビアンを実装したので、正しいはずです。」	間違ったヤコビアンでも、何らかのステップは生成されます。jacobian_diagnostics.py --finite-diff-matrix を実行し、finite_diff_error が小さいことを確認してください。「Large discrepancy with finite-diff」という注記がある場合、解析的ヤコビアンにバグがあり、ニュートン法の収束が気づかないうちに線形収束へ劣化しています。
「ニュートン法が発散したので、全体の許容誤差を小さくして、十分近いということにします。」	発散（convergence_type: diverged、または diverging パターン）は、ステップの方向が適切でないか、解から遠い初期値であることを示しています。大域化を追加してください。globalization_advisor.py を実行し（--far-from-solution を使用するか、失敗を報告）、目標を緩めるのではなく、信頼領域法または減衰ステップに切り替えてください。
「信頼領域法のステップで目的関数が減少したので、採用して半径を拡大します。」	ステップの採否と半径の拡大は、符号だけではなく減少比 ρ によって決まります。step_quality.py が expand を示すのは、ρ ≥ 0.75 かつステップが境界に達した場合だけです。小さい正の ρ（marginal）の場合は、採用して半径を縮小します。記録された trust_radius_action を使用してください。
「ヤコビアンは大きく、計算コストも高いですが、完全なニュートン法が最善なので、とにかく形成します。」	n ≥ 1000、またはヤコビアンの計算コストが高い場合、solver_selector.py は、J の形成／因数分解が実行不可能であるため、行列フリーの Newton-Krylov（JFNK）を選択します。代わりに、前処理とヤコビアン・ベクトル積を使用してください。

セキュリティ

入力の検証

• --size（問題サイズ）は正の整数として検証され、上限は 100 億です
• --residuals は有限の非負数として検証され、エントリ数の上限は 100,000 です
• --tolerance と --target-tolerance は有限の正数として検証されます
• --problem-type と --constraint-type は固定の許可リストに対して検証されます
• --jacobian-quality は固定の許可リスト（good、ill-conditioned など）に対して検証されます
• ステップ品質のパラメーター（predicted-reduction、actual-reduction、step-norm、gradient-norm、trust-radius）は有限数として検証されます

ファイルアクセス

• jacobian_diagnostics.py は --matrix で指定された単一の行列ファイルを読み込みます。指定されたパス以外へのディレクトリトラバーサルはありません
• 行列ファイルにはサイズ制限があり、コード実行を防ぐため allow_pickle=False を指定して読み込まれます
• ほかのスクリプトは外部ファイルを読み込みません。入力は CLI 引数で指定します
• スクリプトは標準出力にのみ書き込みます（JSON 出力）

ツールの制限

• Read：スクリプトのソース、参照情報、ユーザー設定ファイルの確認に使用します
• Bash：6 つの Python 分析スクリプト（solver_selector.py、convergence_analyzer.py、jacobian_diagnostics.py、globalization_advisor.py、residual_monitor.py、step_quality.py）を明示的な引数リストで実行するために使用します
• Write：分析結果やソルバーの推奨事項の保存に使用します。書き込み先はユーザーの作業ディレクトリに限定されます
• Grep/Glob：関連ファイルの特定と参照情報の検索に使用します

安全対策

• eval()、exec()、動的コード生成は使用しません
• すべてのサブプロセス呼び出しで明示的な引数リストを使用します（shell=True は使用しません）
• ヤコビアンファイルの読み込み時に、行列の次元制限によってメモリ枯渇を防ぎます
• 残差履歴の分析では、長さが制限された数値配列のみを扱います

制限事項

• 大域的な収束保証はありません：病的な問題では、すべての手法が失敗する可能性があります
• ヤコビアンの精度：有限差分ヤコビアンは、不連続点の近くで不正確になる場合があります
• 大規模な密問題：ここでは扱っていない専用ソルバーが必要になる場合があります
• 制約付き最適化：複雑な制約には、SQP または内点法が必要です

参考資料

• references/solver_decision_tree.md - 問題に基づくソルバーの選択
• references/method_catalog.md - 手法の詳細とパラメーター
• references/convergence_diagnostics.md - 収束問題の診断
• references/globalization_strategies.md - ラインサーチと信頼領域

バージョン履歴

• v1.2.2（2026-06-24）：各スクリプトの JSON 出力に紐づく証拠（収束の種類／速度、残差パターン、ヤコビアンの条件数／有限差分誤差、ランク、信頼領域のステップ比、ソルバー／大域化戦略の整合性）を記載した「検証チェックリスト」と、一定比率と超線形収束、実行完了と収束、反復回数の不足、解析ヤコビアンの未検証、発散時の処理、信頼領域の受理、大規模または高コストなヤコビアンの振り分けを扱う「よくある落とし穴とその正当化」の表を追加
• v1.2.0（2026-06-23）：solver_selector.py に非線形最小二乗法の経路（Levenberg-Marquardt／Gauss-Newton）を備えた --problem-type を追加。高精度より問題サイズを優先するようソルバー選択順序を変更し、大規模または高コストなヤコビアンを Newton-Krylov に振り分けるよう変更。globalization_advisor.py に --far-from-solution を追加し、最小二乗法の信頼領域の種類として Levenberg-Marquardt を表示。収束の分類を修正し、一定比率の数列を超線形ではなく線形と分類。RFC-8259 に準拠した JSON（-Infinity なし）に対応。入力検証を強化
• v1.1.0（2026-03-26）：エージェント検出の説明、評価スイート、セキュリティレビュー文書を最適化し、メタデータブロックと CHANGELOG を標準化
• v1.0.0：6 つの分析スクリプトを含む初回リリース