optimization - 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.舍入误差主导计算”。他的意思是，你的函数是一个非常平坦的表面，其中的增量是机器 epsilon 的数量级(在这种情况下，你也许可以重新缩放函数)，现在，我想当你的功能太奇怪时，也许应该有第三种选择。振荡？我可以看到像 $\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 个月。为了将来的缘故，我把它放在这里。