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。

Agent 工作流：

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 (...)	大小超过 100 亿的上限	重新检查单位/数值
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	路径无效	确认 Jacobian 文件存在
Matrix file exceeds size limit ...	矩阵文件过大	使用更小或更稀疏的矩阵

解读指南

收敛类型

类型	含义	操作
quadratic	最优 Newton 收敛（阶数 p ≈ 2）	继续，已接近解
superlinear	比率趋近于 0（1 < p < 2）；拟 Newton 方法运行正常	监测是否停滞
linear	收缩比率恒定（p ≈ 1）；较小的恒定比率属于快速线性收敛，而非超线性收敛	可尝试使用预条件器改进
sublinear	速度过慢（比率 → 1）	更换方法或问题表述
stagnated	没有进展	检查 Jacobian、预条件器
diverged	残差增大	添加全局化策略，检查 Jacobian

Jacobian 质量

质量	条件数	操作
good	< 10⁶	使用标准 Newton 方法
moderately-conditioned	10⁶ - 10¹⁰	考虑缩放
ill-conditioned	> 10¹⁰	使用正则化
near-singular	∞	重新表述问题或使用 LM

步长质量（信赖域）

比率 ρ	质量	信赖半径
ρ < 0	very_poor	大幅缩小
ρ < 0.25	marginal	缩小
0.25 ≤ ρ < 0.75	good	保持
ρ ≥ 0.75	excellent	若已到边界则扩大

验证清单

在记录以下具体产物之前，不要相信“已求解”的说法：

• 记录了完整的残差范数历史，并运行了 convergence_analyzer.py --residuals <history>；记录了 convergence_type 和 estimated_rate，并根据实际求解器容差（而非默认值 1e-10）确认 converged: true。
• 确认残差序列单调递减，或将其输入 residual_monitor.py；记录了 patterns_detected，并确认其中不包含 diverging、oscillating、plateau 或 slow_convergence，且残差仍高于容差。
• 如果有 Jacobian，则运行了 jacobian_diagnostics.py --matrix J.txt，并记录了 condition_number 和 jacobian_quality；对于解析 Jacobian，传入了 --finite-diff-matrix，并确认 finite_diff_error 低于约 1e-2（没有“Large discrepancy”提示）。
• 检查了 jacobian_diagnostics.py 的 rank_deficient 为 false（或者记录预期 Jacobian 秩亏/近奇异的原因，以及正在使用 Levenberg-Marquardt 正则化）。
• 对于信赖域求解，使用 step_quality.py 评估了已接受的步长，并记录了缩减 ratio；确认已接受步长的 ratio >= 0.25（不是 very_poor/poor），且 trust_radius_action 与记录的 ρ 相符。
• 记录了实际使用的求解器和全局化策略，并确认其与 solver_selector.py 和 globalization_advisor.py 针对所述问题类型、规模和 Jacobian 质量给出的建议一致（例如，大型问题/计算昂贵的 Jacobian → Newton-Krylov；最小二乘 → Levenberg-Marquardt 信赖域）。
• 在更改容差、初始猜测或预条件器后，重新确认了收敛情况——收敛类型可能发生变化（例如从 quadratic 变为 linear/stagnated），必须重新分类，不可想当然。

常见误区与合理化说辞

看似省事的做法	为什么不对／应该怎么做
“残差比是一个较小的常数（约为 0.1），所以它正在超线性收敛。”	常数收缩比意味着线性收敛，而非超线性收敛——convergence_analyzer.py 会将其报告为 linear（并标注为“fast linear”）。超线性收敛要求该比值趋于零（阶数 p > 1.2）。不要仅凭一个平稳的比值就声称达到了牛顿法级别的收敛。
“它停止时没有报错，所以求解器已经收敛。”	运行结束不等于收敛。请检查 convergence_analyzer.py／residual_monitor.py 返回的 converged，并与实际容差进行比较；stagnated 或 plateau 结果同样会“停止”，但并未求解 f(x)=0。
“看起来两次迭代都在缩小，所以收敛速率没问题。”	阶数估计至少需要 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／报告失败），并改用信赖域或阻尼步长，而不是放宽目标。
“信赖域步长降低了目标函数，所以接受该步长并扩大半径。”	是否接受以及是否扩大半径取决于缩减比 ρ，而不只是其正负。只有当 ρ ≥ 0.75 且步长触及边界时，step_quality.py 才会标记为 expand；较小的正 ρ（marginal）意味着接受但缩小半径。请使用记录的 trust_radius_action。
“雅可比矩阵规模很大，计算成本也高，但完整牛顿法是黄金标准，所以我还是构造它吧。”	对于 n ≥ 1000 或雅可比矩阵计算成本高的情况，solver_selector.py 会选择无矩阵牛顿–克雷洛夫法（JFNK），正是因为构造／分解 J 不可行；此时应使用雅可比矩阵–向量乘积和预条件器。

安全性

输入验证

• --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 参数提供
• 脚本仅向 stdout 写入内容（JSON 输出）

工具限制

• Read：用于检查脚本源代码、参考资料和用户配置文件
• Bash：用于使用明确的参数列表执行六个 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）
• 加载 Jacobian 文件时的矩阵维度限制可防止内存耗尽
• 残差历史分析仅处理长度受限的数值数组

局限性

• 不保证全局收敛：对于病态问题，所有方法都可能失败
• Jacobian 精度：在不连续点附近，有限差分 Jacobian 可能不准确
• 大型稠密问题：可能需要此处未涵盖的专用求解器
• 约束优化：复杂约束需要 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 输出关联起来——收敛类型/速率、残差模式、Jacobian 条件数/有限差分误差、秩、信赖域步长比以及求解器/全局化策略的一致性），并新增“常见陷阱与合理化说辞”表，涵盖恒定比率与超线性、运行完成与收敛、迭代次数过少、未经验证的解析 Jacobian、发散处理、信赖域接受，以及大型问题/高成本 Jacobian 的路由
• v1.2.0（2026-06-23）：在 solver_selector.py 中新增 --problem-type，支持非线性最小二乘路径（Levenberg-Marquardt / Gauss-Newton）；调整求解器选择顺序，使问题规模优先于高精度，并将大型问题/高成本 Jacobian 问题路由至 Newton-Krylov；在 globalization_advisor.py 中新增 --far-from-solution，并将 Levenberg-Marquardt 作为最小二乘问题的信赖域类型；修正收敛分类，将恒定比率序列归类为线性（而非超线性）；采用符合 RFC-8259 的 JSON（不使用 -Infinity）；强化输入验证
• v1.1.0（2026-03-26）：优化 Agent 发现描述、评估套件、安全审查文档，标准化元数据块，新增 CHANGELOG
• v1.0.0：初始版本，包含 6 个分析脚本