least-squares - 如何在Python的最小化中正确停止迭代？

Question

我发布此问题是因为，我的代码没有在正确的位置停止迭代。谁能让我确定哪里出了问题？

一切工作正常(我一直认为这是现实中的错误。)

问题:

1)在每次迭代中，我都在最小化不幸的是，它没有正确地最小化(非常差的结果)。我是否在最小化过程中正确停止了迭代？有什么建议么？

只需运行以下代码:

import numpy as np
from scipy.stats import stats
def run_iter():
    # Initial guess
    x_new = x0
    # just to pretend we have huge error
    phi0 = 1e20
    for i in range(iter_num):
         # first solution
         x_next = x_new

         # FIRST WAY
         # First assumption to stop the iteration...

         # SECOND WAY
         '''
         # Second assumption to stop the iteration
         '''
    return x_new

def example_run():

if __name__ == '__main__':
    print example_run()

Answer 1

我认为您的问题有两个主要方面需要评论。

1)两种方法的收敛性。

您的第一种方法是收敛的，但不能达到您设置的公差。使用L1-supnorm np.max(np.abs(x_new1 - x_new))将先前的迭代值与当前的迭代值进行比较，这表明您的第一个更新机制收敛于1e-14以上的容差(您可以计算phi的相应收敛水平)。您的第二种方法可能根本无法收敛。该例程已被最大迭代界限所切断，但是即使进行1000次迭代，第二种方法下的L1-supnorm也永远不会低于0.009，而迭代步骤通常比第一种例程小得多。此外，增加迭代边界会降低其性能。因此，我将第二种方法的准确性更多地归因于您的最初猜测而不是算法性能。

2)如何提高性能

我会马上提出两个建议。首先，考虑一下您是如何产生初始猜测的。牛顿型优化方法对初始条件非常敏感。我不确定您当前的猜测是否有任何理论基础(现在，您似乎只是选择了一个随机值并对所有参数重复)，但如果没有，请考虑一些更好的方法(也许是简化的解决方案)方法-OLS有时用于初始值，但鉴于您的系统未确定，您可能不得不考虑其他事情。其次，您处理负参数值(x_new1[x_new1<0] = 0.001)的方法非常特殊，对您的算法没有帮助。如果参数应为非负数，则实际上是在解决约束优化问题，在算法中尤其是在“梯度”中应考虑到这一点。有关牛顿型算法和约束优化算法的初始猜测灵敏度的理论细节，任何有关非线性优化/编程的优秀教科书都应有所帮助。一个很好的可能选择是Boyd和Vandenberghe的Convex Optimization，Boyd从他的网站here免费提供。对于实现/代码，很难击败Numerical Recipes。根据您所查看的版本，它会为您提供C++，C或Fortran代码。但是，您应该能够轻松地将其算法转换为Python / NumPy。

关于您最后一个关于np.linalg.norm的问题，我不确定您要引用的代码的哪一部分。

编辑

话虽这么说，我不确定您为什么要这么做。您尝试使用的论文包含几乎可以在Python中完全复制的代码。在本文中，作者使用双共轭梯度法，他在Matlab中使用bicg函数将其应用于(4.1.3)和(4.1.4)。与其尝试编写自己的优化例程，不如使用Python模块bicg中包含的相应scipy方法。可以使用from scipy.sparse.linalg import bicg导入。

作为优化例程的一般说明:如果您不必自己编写它们，则不必。在大多数情况下，已经有人花费了大部分时间来开发所需方法的有效实现。通常，尤其是使用Python，这些都是免费提供的(专有求解器除外)。因此，除非您需要数值方法，否则您最好花费时间找出使用这些预编写例程的最有效方法。在此示例中，将包括理解稀疏结构，您的论文作者用公式(4.1.2)定义。否则，本文将变成使用方程(3.2.3)计算解决方案的问题，您可以使用np.linalg.solve(尽管没有使用稀疏结构，但是效率很低)。或者，由于系统的不确定性，您可以使用 scipy.optimize.nnls ，这还有保持您的值非负的好处。有一个很好的用法示例here。