Line search in LBFGSB package

General Usage
, ,
1

Hi guys,

I am using LBFGSB package to optimize my problem (see below the message). However, I don’t understand the ABNORMAL_TERMINATION_IN_LINSEARCH flag it threw to me at the final point…why is that?

julia> x0 = Cdouble.(default_values)   # or Cdouble.(optim_para) if you have CMAES output
       # Construct optimizer: (max dimension, max memory corrections)
22-element Vector{Float64}:
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 ⋮
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0
 1.0

julia> optimizer = L_BFGS_B(npar, npar)
L_BFGS_B(22, 22, UInt8[0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20  …  0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20], UInt8[0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20  …  0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20, 0x20], Int32[0, 0, 0, 0], Int32[0, 0, 0, 0, 0, 0, 0, 0, 0, 0  …  0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], Int32[0, 0, 0, 0, 0, 0, 0, 0, 0, 0  …  0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], Int32[0, 0, 0, 0, 0, 0, 0, 0, 0, 0  …  0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0  …  0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0])

julia> fout, xout = optimizer(
           f, g!, x0, bounds;
           m       = 10,       # history length (like LBFGS memory)
           factr   = 1e7,      # stop when relative f-change is small
           pgtol   = 1e-4,     # projected gradient tolerance
           # iprint  = 101,      # iprint > 100 print details of every iteration including x and g
           iprint  = 1,      # iprint > 100 print details of every iteration including x and g
           maxfun  = 15000,    # max function evaluations
           maxiter = 15000     # max iterations
       )
RUNNING THE L-BFGS-B CODE

           * * *

Machine precision = 2.220D-16
 N =           22     M =           10

At X0         0 variables are exactly at the bounds

At iterate    0    f=  1.90347D+00    |proj g|=  1.56504D-01

At iterate    1    f=  1.90344D+00    |proj g|=  7.99358D-02

At iterate    2    f=  1.90242D+00    |proj g|=  6.10529D-02

At iterate    3    f=  1.90211D+00    |proj g|=  6.83349D-02

At iterate    4    f=  1.90158D+00    |proj g|=  4.70281D-02

At iterate    5    f=  1.90056D+00    |proj g|=  5.18739D-02

At iterate    6    f=  1.90047D+00    |proj g|=  6.32107D-02

At iterate    7    f=  1.89974D+00    |proj g|=  8.90732D-02

At iterate    8    f=  1.89946D+00    |proj g|=  2.85686D-02
                       
 Bad direction in the line search;
   refresh the lbfgs memory and restart the iteration.

           * * *

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
   22      9     52     15     0     3   2.857D-02   1.899D+00
  F =   1.8994646072387695     

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 9.766E-04 seconds.
 Subspace minimization time 0.000E+00 seconds.
 Line search           time 1.711E+03 seconds.

 Total User time 2.877E+03 seconds.

(1.8994646072387695, [1.009595253028495, 0.9860747982321448, 1.024930509111039, 1.0092265975292285, 1.0022622835432713, 0.9992057879987838, 1.0312890104934747, 1.0116723774845957, 0.9956429678046005, 0.999731686681122  …  1.003628551133322, 1.024811478903042, 0.9857643800974769, 1.0002285319273014, 0.9990209439587879, 1.001541702201964, 1.0013937950134277, 0.9867546882998849, 0.9986523666502582, 1.016650543809241])
2

Without a MWE for us to play with, it’s difficult to help. Would you be able to provide one ?

Besides, is there a reason you use LBFGSB.jl instead of Optimization.jl (from which you may choose from LBFGSB.jl but also Optim.jl) ? If the issue lies with the linesearch, you could also explore different algorithms implemented in LineSearches.jl with Optim.LBFGS.

3

Thanks for the reply!
But what is the line search in LBFGS? I thought it’s just a gradient-based climbing hill downside or upside…
for the reason of not using Optim.Fbox and Optim.LBFGS, it’s because I found the optimizer always hit the bounds of Fbox then Optim tries to reduce the parameter miu to restart the LBFGS…

4

Line search is usually backtracking line search or some such. It’s used to automatically tune the learning rate in gradient-based algorithms. AFAIK it’s most often applied to Newton-like algorithms, including (L)BFGS.