Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

More Thuente line search can find proper step #32

Closed
genmeblog opened this issue May 7, 2023 · 10 comments
Closed

More Thuente line search can find proper step #32

genmeblog opened this issue May 7, 2023 · 10 comments

Comments

@genmeblog
Copy link

Hi!

I've ported your fantastic library (L-BFGS-B only) to Java and starting to test against different cases. TBH, let's say, I understand most of the concepts but most of the stuff I copy&pasted without deeper understanding. Anyway, while testing my port and your library against number of targets - the results are consistent (successes and fails).

The case I work on now is the Bohachevsky 3 function .

 Scalar operator () (const Vector& in, Vector& grad) {
    Scalar x1 = in [0];
    Scalar x2 = in [1];

    grad [0] = 2*x1 + 0.3* std::sin (3.0*PI*x1 + 4.0*PI*x2)*3.0*PI;
    grad [1] = 4*x2 + 0.4* std::sin (3.0*PI*x1 + 4.0*PI*x2)*4.0*PI;
    
    return x1*x1+2.0*x2*x2-0.3*std::cos (3.0*PI*x1 + 4.0*PI*x2) + 0.3;
  }

lb is [-100,-100], ub is [100,100] and initial x is [-100,-100].

Line search algorithm fails to find proper step during sixth iteration (k=6) for x=[-1.17596, -1.02192], grad=[0.291111,0.61104] and drt=[-0.0207124, -0.0218626].

The step is getting lower and lower to reach either minimum step size or maximum number of iterations.

My investigation shows that at the beginning of line search, first wolfe condition is false, second is true, later second condition starts to be false, and much later first starts to be true, below is the debug from my java code (similar result is in your code).

So either More-Thuente search does something wrong, or Cauchy point is wrong, or something different. I can't figure it out unfortunately.

R optim works well for this case.

########## K = 6 ##########
---------- line search ----------
      xp: [   -1.175965   -1.021925]
       x: [   -1.175965   -1.021925]
      fx: 3.6649880842636957
    grad: [    0.291111    0.611040]
      dg: -0.019388518342929335
    step: 1.0
step_max: 4527.278072232203
     drt: [   -0.020712   -0.021863]
-> before wolfe and loop
test_decr: -1.9388518342929334E-6
test_curv: 0.017449666508636403
        x: [   -1.196677   -1.043787]
       fx: 3.6890159788215215
     grad: [   -0.491640   -0.794323]
       dg: 0.02754899968783143
wolfe cond 1: 3.6890159788215215 <= 3.6649861454118615 == false
wolfe cond 2: 0.02754899968783143 <= 0.017449666508636403 == false
-> entering loop
iter: 0
  ft: 0.02402983340966013
  gt: 0.027550938539665722
-- case 1, 0.02402983340966013 > 0.0
-- new_step: 0.1281449854770161
     x: [   -1.178619   -1.024726]
    fx: 3.666020639854685
  grad: [    0.220565    0.483856]
    dg: -0.015146782672016433
  wolfe cond 1: 3.666020639854685 <= 3.664987835809556 == false
  wolfe cond 2: 0.015146782672016433 <= 0.017449666508636403 == true
iter: 1
  ft: 0.0010328040451292847
  gt: -0.01514484382018214
-- case 1, 0.0010328040451292847 > 0.0
-- new_step: 0.018504805795125423
     x: [   -1.176348   -1.022329]
    fx: 3.6651090720284976
  grad: [    0.281510    0.593717]
    dg: -0.01881094795535289
  wolfe cond 1: 3.6651090720284976 <= 3.664988048385619 == false
  wolfe cond 2: 0.01881094795535289 <= 0.017449666508636403 == false
iter: 2
  ft: 1.2102364287850891E-4
  gt: -0.018809009103518595
-- case 1, 1.2102364287850891E-4 > 0.0
-- new_step: 0.002722426236016934
     x: [   -1.176021   -1.021984]
    fx: 3.6650053144570243
  grad: [    0.289711    0.608514]
    dg: -0.019304292377753038
  wolfe cond 1: 3.6650053144570243 <= 3.6649880789853144 == false
  wolfe cond 2: 0.019304292377753038 <= 0.017449666508636403 == false
iter: 3
  ft: 1.7235471709656006E-5
  gt: -0.019302353525918744
-- case 1, 1.7235471709656006E-5 > 0.0
-- new_step: 4.0163395100049855E-4
     x: [   -1.175973   -1.021933]
    fx: 3.664990613925348
  grad: [    0.290905    0.610668]
    dg: -0.01937610886411797
  wolfe cond 1: 3.664990613925348 <= 3.664988083484987 == false
  wolfe cond 2: 0.01937610886411797 <= 0.017449666508636403 == false
iter: 4
  ft: 2.5304403608734615E-6
  gt: -0.019374170012283677
-- case 1, 2.5304403608734615E-6 > 0.0
-- new_step: 5.927648068333564E-5
     x: [   -1.175966   -1.021926]
    fx: 3.66498845734526
  grad: [    0.291080    0.610985]
    dg: -0.019386687201646168
  wolfe cond 1: 3.66498845734526 <= 3.664988084148767 == false
  wolfe cond 2: 0.019386687201646168 <= 0.017449666508636403 == false
iter: 5
  ft: 3.731964926221225E-7
  gt: -0.019384748349811874
-- case 1, 3.731964926221225E-7 > 0.0
-- new_step: 8.749044727386978E-6
     x: [   -1.175965   -1.021925]
    fx: 3.6649881393236887
  grad: [    0.291106    0.611032]
    dg: -0.019388248079223333
  wolfe cond 1: 3.6649881393236887 <= 3.6649880842467324 == false
  wolfe cond 2: 0.019388248079223333 <= 0.017449666508636403 == false
iter: 6
  ft: 5.5076956110783376E-8
  gt: -0.01938630922738904
-- case 1, 5.5076956110783376E-8 > 0.0
-- new_step: 1.29134633845694E-6
     x: [   -1.175965   -1.021925]
    fx: 3.6649880923903435
  grad: [    0.291110    0.611039]
    dg: -0.019388478452564938
  wolfe cond 1: 3.6649880923903435 <= 3.664988084261192 == false
  wolfe cond 2: 0.019388478452564938 <= 0.017449666508636403 == false
iter: 7
  ft: 8.129151528361872E-9
  gt: -0.019386539600730644
-- case 1, 8.129151528361872E-9 > 0.0
-- new_step: 1.906011069354277E-7
     x: [   -1.175965   -1.021925]
    fx: 3.6649880854631744
  grad: [    0.291111    0.611040]
    dg: -0.019388512455164743
  wolfe cond 1: 3.6649880854631744 <= 3.6649880842633262 == false
  wolfe cond 2: 0.019388512455164743 <= 0.017449666508636403 == false
iter: 8
  ft: 1.1998482858618813E-9
  gt: -0.01938657360333045
-- case 1, 1.1998482858618813E-9 > 0.0
-- new_step: 2.813250173095632E-8
     x: [   -1.175965   -1.021925]
    fx: 3.664988084440737
  grad: [    0.291111    0.611040]
    dg: -0.019388517473902345
  wolfe cond 1: 3.664988084440737 <= 3.664988084263641 == false
  wolfe cond 2: 0.019388517473902345 <= 0.017449666508636403 == false
iter: 9
  ft: 1.7709603732982997E-10
  gt: -0.01938657862206805
-- case 1, 1.7709603732982997E-10 > 0.0
-- new_step: 4.152325452828433E-9
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842898264
  grad: [    0.291111    0.611040]
    dg: -0.019388518214661702
  wolfe cond 1: 3.6649880842898264 <= 3.6649880842636877 == false
  wolfe cond 2: 0.019388518214661702 <= 0.017449666508636403 == false
iter: 10
  ft: 2.6138703940608333E-11
  gt: -0.019386579362827408
-- case 1, 2.6138703940608333E-11 > 0.0
-- new_step: 6.128818099384239E-10
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842675513
  grad: [    0.291111    0.611040]
    dg: -0.019388518323996747
  wolfe cond 1: 3.6649880842675513 <= 3.6649880842636944 == false
  wolfe cond 2: 0.019388518323996747 <= 0.017449666508636403 == false
iter: 11
  ft: 3.8567708069396475E-12
  gt: -0.019386579472162453
-- case 1, 3.8567708069396475E-12 > 0.0
-- new_step: 9.047013223848551E-11
     x: [   -1.175965   -1.021925]
    fx: 3.664988084264264
  grad: [    0.291111    0.611040]
    dg: -0.0193885183401345
  wolfe cond 1: 3.664988084264264 <= 3.6649880842636957 == false
  wolfe cond 2: 0.0193885183401345 <= 0.017449666508636403 == false
iter: 12
  ft: 5.686095967899195E-13
  gt: -0.019386579488300207
-- case 1, 5.686095967899195E-13 > 0.0
-- new_step: 1.3359590455377545E-11
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842637788
  grad: [    0.291111    0.611040]
    dg: -0.019388518342516703
  wolfe cond 1: 3.6649880842637788 <= 3.6649880842636957 == false
  wolfe cond 2: 0.019388518342516703 <= 0.017449666508636403 == false
iter: 13
  ft: 8.307058450842152E-14
  gt: -0.01938657949068241
-- case 1, 8.307058450842152E-14 > 0.0
-- new_step: 1.9790395282910703E-12
     x: [   -1.175965   -1.021925]
    fx: 3.664988084263708
  grad: [    0.291111    0.611040]
    dg: -0.019388518342868165
  wolfe cond 1: 3.664988084263708 <= 3.6649880842636957 == false
  wolfe cond 2: 0.019388518342868165 <= 0.017449666508636403 == false
iter: 14
  ft: 1.2438334940221318E-14
  gt: -0.01938657949103387
-- case 1, 1.2438334940221318E-14 > 0.0
-- new_step: 2.92242071913514E-13
     x: [   -1.175965   -1.021925]
    fx: 3.664988084263697
  grad: [    0.291111    0.611040]
    dg: -0.019388518342920255
  wolfe cond 1: 3.664988084263697 <= 3.6649880842636957 == false
  wolfe cond 2: 0.019388518342920255 <= 0.017449666508636403 == false
iter: 15
  ft: 1.332834243627375E-15
  gt: -0.01938657949108596
-- case 1, 1.332834243627375E-15 > 0.0
-- new_step: 4.69847459607086E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 16
  ft: -4.439981133891729E-16
  gt: -0.01938657949109344
-- case 2, -0.0 > 0.0
-- new_step: 9.866796651748807E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342926087
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342926087 <= 0.017449666508636403 == false
iter: 17
  ft: -4.4389790728219423E-16
  gt: -0.019386579491091793
-- case 1, -4.4389790728219423E-16 > -4.439981133891729E-16
-- new_step: 5.79052036971028E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636957
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927485
  wolfe cond 1: 3.6649880842636957 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927485 <= 0.017449666508636403 == false
iter: 18
  ft: 1.122696104032337E-19
  gt: -0.01938657949109319
-- case 1, 1.122696104032337E-19 > -4.439981133891729E-16
-- new_step: 4.760785175092509E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 19
  ft: -4.439969052793686E-16
  gt: -0.01938657949109344
-- case 1, -4.439969052793686E-16 > -4.439981133891729E-16
-- new_step: 4.711640572134368E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 20
  ft: -4.439978581204045E-16
  gt: -0.01938657949109344
-- case 1, -4.439978581204045E-16 > -4.439981133891729E-16
-- new_step: 4.701256514140482E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 21
  ft: -4.439980594519034E-16
  gt: -0.01938657949109344
-- case 1, -4.439980594519034E-16 > -4.439981133891729E-16
-- new_step: 4.699062404232806E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 22
  ft: -4.439981019924436E-16
  gt: -0.01938657949109344
-- case 1, -4.439981019924436E-16 > -4.439981133891729E-16
-- new_step: 4.69859879756223E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 23
  ft: -4.4399811098109E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811098109E-16 > -4.439981133891729E-16
-- new_step: 4.698500839332691E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 24
  ft: -4.4399811288035497E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811288035497E-16 > -4.439981133891729E-16
-- new_step: 4.6984801410871304E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 25
  ft: -4.4399811328166325E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811328166325E-16 > -4.439981133891729E-16
-- new_step: 4.6984757674434593E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 26
  ft: -4.439981133664617E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133664617E-16 > -4.439981133891729E-16
-- new_step: 4.698474842357829E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 27
  ft: -4.439981133843978E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133843978E-16 > -4.439981133891729E-16
-- new_step: 4.6984746085145E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 28
  ft: -4.4399811338893167E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338893167E-16 > -4.439981133891729E-16
-- new_step: 4.698474602292058E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 29
  ft: -4.4399811338905227E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338905227E-16 > -4.439981133891729E-16
-- new_step: 4.698474574428066E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 30
  ft: -4.4399811338959254E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474592818301E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 31
  ft: -4.4399811338923597E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338923597E-16 > -4.4399811338959254E-16
-- new_step: 4.6984745836227235E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 32
  ft: -4.4399811338941425E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338941425E-16 > -4.4399811338959254E-16
-- new_step: 4.698474579025165E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 33
  ft: -4.439981133895034E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133895034E-16 > -4.4399811338959254E-16
-- new_step: 4.698474576726386E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 34
  ft: -4.4399811338954797E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338954797E-16 > -4.4399811338959254E-16
-- new_step: 4.698474550823932E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 35
  ft: -4.439981133900502E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.6984745679195516E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 36
  ft: -4.439981133897187E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133897187E-16 > -4.439981133900502E-16
-- new_step: 4.698474559371315E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 37
  ft: -4.4399811338988447E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338988447E-16 > -4.439981133900502E-16
-- new_step: 4.6984745200910456E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 38
  ft: -4.4399811339064606E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474559371315E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 39
  ft: -4.4399811338988447E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811338988447E-16 > -4.4399811339064606E-16
-- new_step: 4.698474539729216E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 40
  ft: -4.439981133902653E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133902653E-16 > -4.4399811339064606E-16
-- new_step: 4.698474529909149E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 41
  ft: -4.439981133904557E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133904557E-16 > -4.4399811339064606E-16
-- new_step: 4.698474500246615E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 42
  ft: -4.439981133910308E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474529909149E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 43
  ft: -4.439981133904557E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133904557E-16 > -4.439981133910308E-16
-- new_step: 4.6984745150763994E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 44
  ft: -4.439981133907433E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133907433E-16 > -4.439981133910308E-16
-- new_step: 4.6984745076611366E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 45
  ft: -4.4399811339088706E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339088706E-16 > -4.439981133910308E-16
-- new_step: 4.698474479200454E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 46
  ft: -4.4399811339143887E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.6984745076611366E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 47
  ft: -4.4399811339088706E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339088706E-16 > -4.4399811339143887E-16
-- new_step: 4.698474493429372E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 48
  ft: -4.4399811339116296E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339116296E-16 > -4.4399811339143887E-16
-- new_step: 4.6984744863142014E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 49
  ft: -4.439981133913009E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133913009E-16 > -4.4399811339143887E-16
-- new_step: 4.698474447750787E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 50
  ft: -4.439981133920486E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.6984744863142014E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 51
  ft: -4.439981133913009E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133913009E-16 > -4.439981133920486E-16
-- new_step: 4.698474467030566E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 52
  ft: -4.439981133916748E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133916748E-16 > -4.439981133920486E-16
-- new_step: 4.6984744573897126E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 53
  ft: -4.4399811339186175E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339186175E-16 > -4.439981133920486E-16
-- new_step: 4.6984744525700085E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 54
  ft: -4.439981133919552E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133919552E-16 > -4.439981133920486E-16
-- new_step: 4.6984744501602776E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 55
  ft: -4.439981133920019E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920019E-16 > -4.439981133920486E-16
-- new_step: 4.698474448955472E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 56
  ft: -4.4399811339202524E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339202524E-16 > -4.439981133920486E-16
-- new_step: 4.698474448353099E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 57
  ft: -4.439981133920369E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920369E-16 > -4.439981133920486E-16
-- new_step: 4.698474448051928E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 58
  ft: -4.439981133920428E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920428E-16 > -4.439981133920486E-16
-- new_step: 4.6984744479013504E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 59
  ft: -4.439981133920457E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920457E-16 > -4.439981133920486E-16
-- new_step: 4.6984744478260615E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 60
  ft: -4.439981133920472E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920472E-16 > -4.439981133920486E-16
-- new_step: 4.698474447788421E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 61
  ft: -4.4399811339204787E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339204787E-16 > -4.439981133920486E-16
-- new_step: 4.698474447769602E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 62
  ft: -4.4399811339204826E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339204826E-16 > -4.439981133920486E-16
-- new_step: 4.6984744477601935E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 63
  ft: -4.439981133920484E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920484E-16 > -4.439981133920486E-16
-- new_step: 4.6984744477554907E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 64
  ft: -4.439981133920485E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133920485E-16 > -4.439981133920486E-16
-- new_step: 4.698474447753139E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 65
  ft: -4.4399811339204856E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339204856E-16 > -4.439981133920486E-16
-- new_step: 4.6984744127456E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 66
  ft: -4.439981133927273E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474447753139E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 67
  ft: -4.4399811339204856E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339204856E-16 > -4.439981133927273E-16
-- new_step: 4.698474430247619E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 68
  ft: -4.4399811339238796E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339238796E-16 > -4.439981133927273E-16
-- new_step: 4.698474421495734E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 69
  ft: -4.4399811339255767E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339255767E-16 > -4.439981133927273E-16
-- new_step: 4.698474392367211E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 70
  ft: -4.4399811339312244E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474421495734E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 71
  ft: -4.4399811339255767E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339255767E-16 > -4.4399811339312244E-16
-- new_step: 4.6984744069300165E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 72
  ft: -4.439981133928401E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133928401E-16 > -4.4399811339312244E-16
-- new_step: 4.69847439964825E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 73
  ft: -4.4399811339298124E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339298124E-16 > -4.4399811339312244E-16
-- new_step: 4.6984743960073664E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 74
  ft: -4.4399811339305184E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339305184E-16 > -4.4399811339312244E-16
-- new_step: 4.6984743941871064E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 75
  ft: -4.4399811339308714E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339308714E-16 > -4.4399811339312244E-16
-- new_step: 4.6984743932770677E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 76
  ft: -4.439981133931048E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133931048E-16 > -4.4399811339312244E-16
-- new_step: 4.6984743928221164E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 77
  ft: -4.439981133931136E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133931136E-16 > -4.4399811339312244E-16
-- new_step: 4.698474367841416E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 78
  ft: -4.4399811339359793E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474384328678E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 79
  ft: -4.439981133932783E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133932783E-16 > -4.4399811339359793E-16
-- new_step: 4.698474376084635E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 80
  ft: -4.4399811339343814E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339343814E-16 > -4.4399811339359793E-16
-- new_step: 4.698474347209583E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 81
  ft: -4.43998113393998E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.698474376084635E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 82
  ft: -4.4399811339343814E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339343814E-16 > -4.43998113393998E-16
-- new_step: 4.698474361645665E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 83
  ft: -4.439981133937181E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133937181E-16 > -4.43998113393998E-16
-- new_step: 4.6984743544269025E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 84
  ft: -4.43998113393858E-16
  gt: -0.01938657949109344
-- case 1, -4.43998113393858E-16 > -4.43998113393998E-16
-- new_step: 4.698474350817882E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 85
  ft: -4.43998113393928E-16
  gt: -0.01938657949109344
-- case 1, -4.43998113393928E-16 > -4.43998113393998E-16
-- new_step: 4.6984743242604065E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 86
  ft: -4.439981133944429E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.6984743417883404E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 87
  ft: -4.4399811339410305E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339410305E-16 > -4.439981133944429E-16
-- new_step: 4.6984743330239355E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 88
  ft: -4.43998113394273E-16
  gt: -0.01938657949109344
-- case 1, -4.43998113394273E-16 > -4.439981133944429E-16
-- new_step: 4.698474328641733E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 89
  ft: -4.4399811339435795E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339435795E-16 > -4.439981133944429E-16
-- new_step: 4.69847432645096E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 90
  ft: -4.4399811339440045E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339440045E-16 > -4.439981133944429E-16
-- new_step: 4.698474325355629E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 91
  ft: -4.439981133944217E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133944217E-16 > -4.439981133944429E-16
-- new_step: 4.69847432480799E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 92
  ft: -4.439981133944323E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133944323E-16 > -4.439981133944429E-16
-- new_step: 4.698474299780948E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 93
  ft: -4.4399811339491755E-16
  gt: -0.01938657949109344
-- case 3
-- new_step: 4.69847432480799E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 94
  ft: -4.439981133944323E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133944323E-16 > -4.4399811339491755E-16
-- new_step: 4.698474312293218E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 95
  ft: -4.439981133946749E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133946749E-16 > -4.4399811339491755E-16
-- new_step: 4.6984743060367704E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 96
  ft: -4.4399811339479626E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339479626E-16 > -4.4399811339491755E-16
-- new_step: 4.698474302908546E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 97
  ft: -4.439981133948569E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133948569E-16 > -4.4399811339491755E-16
-- new_step: 4.698474301344669E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 98
  ft: -4.439981133948872E-16
  gt: -0.01938657949109344
-- case 1, -4.439981133948872E-16 > -4.4399811339491755E-16
-- new_step: 4.69847430056277E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
iter: 99
  ft: -4.4399811339490236E-16
  gt: -0.01938657949109344
-- case 1, -4.4399811339490236E-16 > -4.4399811339491755E-16
-- new_step: 4.6984743001718395E-14
     x: [   -1.175965   -1.021925]
    fx: 3.6649880842636953
  grad: [    0.291111    0.611040]
    dg: -0.019388518342927735
  wolfe cond 1: 3.6649880842636953 <= 3.6649880842636957 == true
  wolfe cond 2: 0.019388518342927735 <= 0.017449666508636403 == false
org.generateme.lbfgsb.LBFGSBException: the line search routine reached the maximum number of iterations
	at org.generateme.lbfgsb.LineSearch.<init>(LineSearch.java:305)
	at org.generateme.lbfgsb.LBFGSB.minimize(LBFGSB.java:131)
	at org.generateme.lbfgsb.examples.Bohachevsky3.main(Bohachevsky3.java:34)
@genmeblog
Copy link
Author

As I understand More & Thuente paper, initial conditions (dg<0, continuous funcition) guarantess finding optimal step which is not the case in the example above. I'll read dig details soon but maybe you can figure out what is going on here earlier.

@genmeblog
Copy link
Author

Discovered, that R version shows details. Looks like after first iteration line search in R makes bigger step:

LINE SEARCH 1 times; norm of step = 141.28
X = -0.1 -0.1
G = -2.48744 -4.46656

while when using LBFGSpp (after 8 iterations)

step = 15.9374
x=-88.7305 -88.7305
m_grad=-176.472 -353.164

@genmeblog
Copy link
Author

Ok, I found the difference, original L-BFGS-B doesnt normalize drt https://github.com/yixuan/LBFGSpp/blob/master/include/LBFGSB.h#L164

Turning off normalization, I'm getting more accuarate and comparable results to the R optim.

@yixuan
Copy link
Owner

yixuan commented May 9, 2023

Yes, this is a known difference. Thanks for pointing out.
I normalized the initial direction since in some cases the first step is just too large, and a conservative seems more stable. I'll take a look at the problem later to see what happens after a few iterations.

@yixuan
Copy link
Owner

yixuan commented May 9, 2023

Yes, this is a known difference. Thanks for pointing out.
I normalized the initial direction since in some cases the first step is just too large, and a conservative one seems more stable. I'll take a look at the problem later to see what happens after a few iterations.

@genmeblog
Copy link
Author

Thanks! I hit quite often minimal step issue which is not the case for a version from original L-BFGS-B. So maybe something happens inside your version of line search.

@genmeblog
Copy link
Author

After more experiments I observe that limiting first step (by normalizing) causes more test functions to wrong convergence. I found that changing to weak Wolfe test helps in certain scenarios, it definitely makes steps shorter (resulting in slower convergence). Weak Wolfe helps also when function is not smooth.

@genmeblog genmeblog mentioned this issue May 10, 2023
Open
@yixuan
Copy link
Owner

yixuan commented May 14, 2023 •
edited
Loading

OK, so I finally figured out the problem -- The gradient computation is wrong. 😂

The second partial derivative should be

grad [1] = 4*x2 + 0.3* std::sin (3.0*PI*x1 + 4.0*PI*x2)*4.0*PI;

@genmeblog
Copy link
Author

Ooops... What a stupid mistake... sorry for that. I'll let you know if I find the other case (I'm pretty sure there was another, I hope with proper gradient :) ).

@yixuan
Copy link
Owner

yixuan commented May 25, 2023

Let me close this first, and feel free to reopen if further issues occur.

@yixuan yixuan closed this as completed May 25, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@yixuan @genmeblog