forum.alglib.net
http://forum.alglib.net/

Question about L-BFGS step
http://forum.alglib.net/viewtopic.php?f=2&t=3515		 Page 1 of 1
Author:  henkvandam [ Wed Jan 13, 2016 5:21 pm ]
Post subject:  Question about L-BFGS step
Dear alglib,

I have tried out the Python version of L-BFGS with numerical gradient for my maximum likelihood estimation. The algorithm performs well at the beginning, trying small steps. But in the later stage, it starts to try some parameters very far from the previous point, and leads to negative log likelihood going to infinity. Eventually the algorithm stops with the value that leads to -infinity. I have shown a snippet of the steps that switched from normal small step search to large step search below.

Is this happening because the gradient is too small for the algorithm to try something small? Does this mean this is near the optimum? How should I inform the algorithm that the step it is trying is not feasible and it should backtrack?

Thank you!
Henk

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[-9.58362034 -2.41123789 -2.36222228 -2.3671299 -4.88157934 -2.81564508
-3.20954561 -1.28837444 -3.36283337 -4.74479617 -5.01694472 -3.69086546
-5.76013634 -3.50911833 -9.2103 -1.92538441 -2.67018378 -9.2103
-9.2103 -9.2103 -5.80543116 -4.56404266 -3.17869566]
mu_gamma:
[ 1.66905736 -4.51448085 -0.66986931 -5.12043919 -3.1935538
-2.00441952 -10.14119433]

[Wed Jan 13 02:29:52 2016] Negative log likelihood: 382907.12427123089, Elapsed time: 0.0127031803131

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[-9.58362034 -2.41123789 -2.36222228 -2.3671299 -4.88157934 -2.81564508
-3.20954561 -1.28837444 -3.36283337 -4.74479617 -5.01694472 -3.69086546
-5.76013634 -3.50911833 -9.2103 -1.92538441 -2.67018378 -9.2103
-9.2103 -9.2103 -5.80543116 -4.56404266 -3.17869566]
mu_gamma:
[ 1.66905736 -4.51448085 -0.66986931 -5.12043919 -3.1935538
-2.00441952 -10.14119333]

[Wed Jan 13 02:29:52 2016] Negative log likelihood: 382907.12427041965, Elapsed time: 0.0131719112396

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[-9.58362034 -2.41123789 -2.36222228 -2.3671299 -4.88157934 -2.81564508
-3.20954561 -1.28837444 -3.36283337 -4.74479617 -5.01694472 -3.69086546
-5.76013634 -3.50911833 -9.2103 -1.92538441 -2.67018378 -9.2103
-9.2103 -9.2103 -5.80543116 -4.56404266 -3.17869566]
mu_gamma:
[ 1.66905736 -4.51448085 -0.66986931 -5.12043919 -3.1935538
-2.00441952 -10.14119283]

[Wed Jan 13 02:29:52 2016] Negative log likelihood: 382907.12427001412, Elapsed time: 0.012629032135

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[ 1213.79751302 -628.06688471 -2971.79368032 -2824.44542868 -15.01845319
-363.77978283 -230.9855427 -1131.82050822 -211.81809739 -122.89389138
-73.75904751 -277.33747764 -22.11033845 -36.7372429 -9.2103
-899.70579442 21.87460924 -9.2103 -9.2103 -9.2103
-12.52031543 3.8345176 -12.23877629]
mu_gamma:
[-22719.44879008 -184.51365897 -6175.16699133 -144.24854553
-403.43173915 2083.80874644 -9.32993425]

[Wed Jan 13 02:29:52 2016] Infeasible Parameters.

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[ 1213.79751202 -628.06688471 -2971.79368032 -2824.44542868 -15.01845319
-363.77978283 -230.9855427 -1131.82050822 -211.81809739 -122.89389138
-73.75904751 -277.33747764 -22.11033845 -36.7372429 -9.2103
-899.70579442 21.87460924 -9.2103 -9.2103 -9.2103
-12.52031543 3.8345176 -12.23877629]
mu_gamma:
[-22719.44879008 -184.51365897 -6175.16699133 -144.24854553
-403.43173915 2083.80874644 -9.32993425]

[Wed Jan 13 02:29:52 2016] Infeasible Parameters.

[Wed Jan 13 02:29:52 2016] Evaluating neg_llkd at:
mu_beta:
[ 1213.79751252 -628.06688471 -2971.79368032 -2824.44542868 -15.01845319
-363.77978283 -230.9855427 -1131.82050822 -211.81809739 -122.89389138
-73.75904751 -277.33747764 -22.11033845 -36.7372429 -9.2103
-899.70579442 21.87460924 -9.2103 -9.2103 -9.2103
-12.52031543 3.8345176 -12.23877629]
mu_gamma:
[-22719.44879008 -184.51365897 -6175.16699133 -144.24854553
-403.43173915 2083.80874644 -9.32993425]

[Wed Jan 13 02:29:52 2016] Infeasible Parameters.
Author:  Sergey.Bochkanov [ Thu Jan 14, 2016 12:05 pm ]
Post subject:  Re: Question about L-BFGS step
How exactly you determined that your function has "infeasible parameters"? I mean, what condition you used?

If your function has some kind of box constraint, some operation which relies on nonnegativity of its operands, etc, then optimizer may accidentally find this weak point and perform step deep into infeasible area. I see that after stepping far away, it performs small steps around "infeasible" point, so it still tries to optimize.

So, it may be optimizer problem - but may be problem with your function, some hidden instability. Say, like optimizing f=1/x+x^2. Everything is OK until you suddenly jump over x=0, and now you have problem which is unconstrained from below at x=0.
Author:  henkvandam [ Fri Jan 15, 2016 1:42 am ]
Post subject:  Re: Question about L-BFGS step
Dear Sergey,

Thank you for your reply! My parameters have sign constraints, so I need to exp the parameter before evaluating it in the likelihood function. By having the parameter value being around 2000, it is easy to detect infeasible parameter. I just tried to use 1e300 as the returned negative log likelihood, and it seems to have solved problem.

Best,
Henk
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/