Levenberg-Marquardt算法时间复杂度是否为多项式？求替代算法

1. Levenberg-Marquardt（LM）算法的时间复杂度 #

LM算法是迭代式的非线性最小二乘求解器，它的时间复杂度不是严格的多项式时间：

• 单次迭代的核心开销是雅可比矩阵的计算与分解（如QR或Cholesky分解），针对n维参数的问题，单次迭代时间复杂度为O(n³)；
• 但迭代次数没有多项式上界，它高度依赖问题的非线性程度、初始点质量以及收敛阈值。最坏情况下，迭代次数可能呈指数增长，因此整体复杂度无法保证为多项式时间。

2. 多项式时间的非线性最小二乘算法是否存在？ #

需分场景讨论：

• 全局最优解：普通非线性最小二乘问题属于NP难问题，不存在能在多项式时间内找到全局最优解的精确算法。
• 局部最优解：若问题满足特定条件（如目标函数的雅可比矩阵具有Lipschitz连续性），部分信赖域方法、正则化牛顿法变体可保证在多项式时间内收敛到局部最优解。
• 凸非线性最小二乘问题：当残差函数为凸函数时，平方和目标函数也具备凸性，此时梯度下降、牛顿法等算法可在多项式时间内收敛到全局最优解。

补充：Scipy least_squares中的lm方法属于局部优化算法，适合初始点接近最优解的场景，能快速收敛到局部最优。

内容的提问来源于stack exchange，提问作者David Pham