如何在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

为先停止准则，只用一个较低的误差边界比1e20。如果您在每次迭代打印phi，你会看到，设置

phi0 = 1e10 

将停止迭代在i == 1具有非常相似的结果（甚至稍低一些）。另外，如果您需要更多帮助，您应该提供更多关于您尝试解决的优化问题类型，您使用的方法以及停止标准背后的想法的更多详细信息。

Answer 2

我看到您的问题的两个主要方面进行评论。

1）两种方法的收敛性。

您的第一种方法是收敛的，但不是像您设定的那样高。使用L1超范围，np.max(np.abs(x_new1 - x_new))，将先前的迭代值与当前迭代值进行比较，表明您的第一个更新机制收敛于略高于1e-14的容差（您可以计算phi的相应收敛级别）。你的第二种方法可能根本不会收敛。例程被最大迭代界限切断，但即使进行1000次迭代，第二种方法下的L1超范围也不会低于0.009，迭代步骤一般比第一个例程小得多。此外，增加迭代界限会降低其性能。因此，我会将第二种方法的准确性归因于初始猜测，而不是算法性能。

2）如何提高性能

有两个建议，我会给予了蝙蝠的权利。首先，考虑你如何产生你的初步猜测。牛顿型优化方法对初始条件非常敏感。我不确定你目前的猜测是否有任何理论基础（现在，看起来你只是选择了一个随机值并重复了所有参数），但是如果不是，请考虑一些方法来更好地通知它（可能是一个简化的解决方案方法 - OLS有时用于初始值，但由于系统未定），您可能必须考虑其他内容。其次，处理负面参数值的方法（x_new1[x_new1<0] = 0.001）非常特殊，并且不能帮助您的算法。如果参数应该是非负的，那么实际上你正在解决一个约束优化问题，并且应该在算法中考虑这个问题，尤其是在渐变中。有关牛顿型算法的初始猜测灵敏度和约束优化算法的理论细节，任何关于非线性优化/编程的优秀教材都应该有所帮助。 Boyd和Vandenberghe的凸优化是一个很好的选择，Boyd通过他的网站here免费提供。对于实现/代码，很难击败Numerical Recipes。根据你看的版本，它会给你在C++，C或Fortran中的代码。但是，你应该能够很轻松地将他们的算法转换为Python/NumPy。

关于你最后一个关于np.linalg.norm的问题，我不确定你指的是哪部分代码。

编辑

话虽这么说，我不知道你为什么在所有做任何这一点。您正在尝试使用的论文包含的代码几乎可以在Python中完全复制。在本文中，笔者使用了双共轭梯度法，他在（4.1.3）和（4.1.4）中使用了Matlab中的bicg函数。与其尝试编写自己的优化例程，不如使用Python模块scipy中包含的相应bicg方法。它可以用from scipy.sparse.linalg import bicg进口。

作为优化例程的一般说明：如果您不必亲自编写它们，则不要这样做。大多数情况下，已经有人花费了大部分时间来开发有效实施所需方法的人员。通常，特别是在Python中，这些都是免费提供的（除专有解算器之外）。所以，除非数字方法是你的东西，否则你的时间可能会更好地用于确定使用这些预先编写的例程的最有效的方法。在这个例子中，将会包括理解您的论文的作者在方程（4.1.2）中定义的稀疏结构。如果没有这一点，论文只是用方程（3.2.3）计算解决方案，你可能用np.linalg.solve（尽管效率不高，因为你没有使用稀疏结构）做了解。或者，由于您的系统不确定，因此您可以使用scipy.optimize.nnls，这也有助于保持值不为负。有一个很好的使用示例here。