scipy.optimize.fmin_l_bfgs_b返回“”ABNORMAL_TERMINATION_IN_LNSRCH“”

Question

我正在使用scipy.optimize.fmin_l_bfgs_b来解决高斯混合问题。混合分布的均值由回归建模，回归的权重必须使用EM算法进行优化。

sigma_sp_new, func_val, info_dict = fmin_l_bfgs_b(func_to_minimize, self.sigma_vector[si][pj], 
                       args=(self.w_vectors[si][pj], Y, X, E_step_results[si][pj]),
                       approx_grad=True, bounds=[(1e-8, 0.5)], factr=1e02, pgtol=1e-05, epsilon=1e-08)

但有时我会在信息字典中收到警告'ABNORMAL_TERMINATION_IN_LNSRCH‘：

func_to_minimize value = 1.14462324063e-07
information dictionary: {'task': b'ABNORMAL_TERMINATION_IN_LNSRCH', 'funcalls': 147, 'grad': array([  1.77635684e-05,   2.87769808e-05,   3.51718654e-05,
         6.75015599e-06,  -4.97379915e-06,  -1.06581410e-06]), 'nit': 0, 'warnflag': 2}

RUNNING THE L-BFGS-B CODE

           * * *

Machine precision = 2.220D-16
 N =            6     M =           10
 This problem is unconstrained.

At X0         0 variables are exactly at the bounds

At iterate    0    f=  1.14462D-07    |proj g|=  3.51719D-05

           * * *

Tit   = total number of iterations
Tnf   = total number of function evaluations
Tnint = total number of segments explored during Cauchy searches
Skip  = number of BFGS updates skipped
Nact  = number of active bounds at final generalized Cauchy point
Projg = norm of the final projected gradient
F     = final function value

           * * *

   N    Tit     Tnf  Tnint  Skip  Nact     Projg        F
    6      1     21      1     0     0   3.517D-05   1.145D-07
  F =  1.144619474757747E-007

ABNORMAL_TERMINATION_IN_LNSRCH                              

 Line search cannot locate an adequate point after 20 function
  and gradient evaluations.  Previous x, f and g restored.
 Possible causes: 1 error in function or gradient evaluation;
                  2 rounding error dominate computation.

 Cauchy                time 0.000E+00 seconds.
 Subspace minimization time 0.000E+00 seconds.
 Line search           time 0.000E+00 seconds.

 Total User time 0.000E+00 seconds.

我并不是每次都收到这个警告，但有时。(大多数人得到的是'CONVERGENCE: NORM_OF_PROJECTED_GRADIENT_<=_PGTOL‘或'CONVERGENCE: REL_REDUCTION_OF_F_<=_FACTR*EPSMCH')。

我知道这意味着在这次迭代中可以达到最小值。我用谷歌搜索了这个问题。有人说，这种情况经常发生，因为目标函数和梯度函数不匹配。但这里我没有提供梯度函数，因为我使用的是'approx_grad‘。

我应该调查的可能原因是什么？“四舍五入误差主导计算”是什么意思？

======

我还发现对数似然不是单调增加的：

########## Convergence !!! ##########
log_likelihood_history: [-28659.725891322563, 220.49993177669558, 291.3513633060345, 267.47745327823907, 265.31567762171181, 265.07311121000367, 265.04217683341682]

它通常在第二次或第三次迭代时开始减少，即使'ABNORMAL_TERMINATION_IN_LNSRCH‘没有发生。我不知道这个问题是否与前一个问题有关。

Answer 1

Scipy调用原始的L-BFGS-B实现。这是一些fortran77 (古老但美丽和超快的代码)，我们的问题是下降方向实际上是向上的。问题开始于第2533行(链接到底部的代码)

gd = ddot(n,g,1,d,1)
  if (ifun .eq. 0) then
     gdold=gd
     if (gd .ge. zero) then
c                               the directional derivative >=0.
c                               Line search is impossible.
        if (iprint .ge. 0) then
            write(0,*)' ascent direction in projection gd = ', gd
        endif
        info = -4
        return
     endif
  endif

换句话说，你告诉它通过上山下山。代码在您提供的下降方向上总共尝试了20次称为行搜索的东西，并意识到您并不是在告诉它下坡，而是上坡。都是20次。

写这篇文章的人(Jorge Nocedal，顺便说一句，他是一个非常聪明的人)写了20，因为这已经足够了。机器epsilon是10E-16，我认为20实际上有点太多了。所以，对于大多数有这个问题的人来说，我的意见是，你的梯度与你的函数不匹配。

现在，它也可能是"2.舍入误差主导计算“。他的意思是，你的函数是一个非常平坦的表面，其中的增量是机器ε的量级(在这种情况下，你也许可以重新调整函数的比例)，现在，我在想，当你的函数太奇怪时，也许应该有第三种选择。振荡？我可以看到像$\sin({\frac{1}{x}})$这样的东西导致了这种问题。但我不是个聪明人，所以别以为会有第三个案例。

所以我认为OP的解决方案应该是你的函数太扁平了。或者看看fortran代码。

https://github.com/scipy/scipy/blob/master/scipy/optimize/lbfgsb/lbfgsb.f

对于那些想看它的人，这里有行搜索。https://en.wikipedia.org/wiki/Line_search

请注意。这已经晚了7个月了。我把它放在这里是为了将来。

Answer 2

正如Wilmer E. Henao在答案中指出的那样，问题可能存在于梯度中。由于您使用的是approx_grad=True，因此梯度是以数值方式计算的。在这种情况下，减小epsilon的值可能会有所帮助。

Answer 3

我使用L-BFGS-B优化器也得到了错误"ABNORMAL_TERMINATION_IN_LNSRCH“。

虽然我的梯度函数指向正确的方向，但我通过它的L2范数重新缩放了函数的实际梯度。删除它或添加另一种适当类型的重新缩放是可行的。以前，我猜梯度太大了，以至于它立即超出了边界。

如果我没读错，来自OP的问题是无界的，所以这在这个问题设置中肯定不会有帮助。然而，在谷歌上搜索错误"ABNORMAL_TERMINATION_IN_LNSRCH“会得到这个页面作为第一个结果，所以它可能会对其他人有所帮助……