{"action":"created","issue":{"url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/4","labels_url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/4/labels{/name}","comments_url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/4/comments","events_url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/4/events","html_url":"https://github.com/PatWie/CppNumericalSolvers/issues/4","id":55949019,"number":4,"title":"Bfgs terminates at nan ","user":{"login":"tosttost","id":9272432,"avatar_url":"https://avatars.githubusercontent.com/u/9272432?v=3","gravatar_id":"","url":"https://api.github.com/users/tosttost","html_url":"https://github.com/tosttost","followers_url":"https://api.github.com/users/tosttost/followers","following_url":"https://api.github.com/users/tosttost/following{/other_user}","gists_url":"https://api.github.com/users/tosttost/gists{/gist_id}","starred_url":"https://api.github.com/users/tosttost/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tosttost/subscriptions","organizations_url":"https://api.github.com/users/tosttost/orgs","repos_url":"https://api.github.com/users/tosttost/repos","events_url":"https://api.github.com/users/tosttost/events{/privacy}","received_events_url":"https://api.github.com/users/tosttost/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/labels/bug","name":"bug","color":"fc2929"}],"state":"closed","locked":false,"assignee":{"login":"PatWie","id":6756603,"avatar_url":"https://avatars.githubusercontent.com/u/6756603?v=3","gravatar_id":"","url":"https://api.github.com/users/PatWie","html_url":"https://github.com/PatWie","followers_url":"https://api.github.com/users/PatWie/followers","following_url":"https://api.github.com/users/PatWie/following{/other_user}","gists_url":"https://api.github.com/users/PatWie/gists{/gist_id}","starred_url":"https://api.github.com/users/PatWie/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/PatWie/subscriptions","organizations_url":"https://api.github.com/users/PatWie/orgs","repos_url":"https://api.github.com/users/PatWie/repos","events_url":"https://api.github.com/users/PatWie/events{/privacy}","received_events_url":"https://api.github.com/users/PatWie/received_events","type":"User","site_admin":false},"milestone":null,"comments":5,"created_at":"2015-01-29T20:02:42Z","updated_at":"2015-02-13T16:04:08Z","closed_at":"2015-02-12T18:38:18Z","body":"The BFGS solver fails to solve the Rosenbrock problem for x0 = (-1.2, 1): it returns (NaN, NaN). This starting point is used in Rosenbrock's paper ( http://comjnl.oxfordjournals.org/content/3/3/175.full.pdf+html ) and makes the optimization more difficult than x0=(1,2) which is proposed in the README. \r\n\r\nI suspect this is caused by the used line search (seems to be the Armijo rule). As far as I know the Armijo rule is not suitable for BFGS because the approximation of the inversed Hessian does not need to stay positive definite. \r\n\r\nTest case:\r\n\r\n auto rosenbrock = [] (const Vector &x) -> double {\r\n        const double t1 = (1-x[0]);\r\n        const double t2 = (x[1]-x[0]*x[0]);\r\n        return   t1*t1 + 100*t2*t2;\r\n    };\r\n\r\n    // create derivative of function\r\n    auto Drosenbrock = [] (const Vector x, Vector &grad) -> void {\r\n        grad[0]  = -2*(1-x[0])+200*(x[1]-x[0]*x[0])*(-2*x[0]);\r\n        grad[1]  = 200*(x[1]-x[0]*x[0]);\r\n    };\r\n\r\n    // initial guess\r\n    Vector x0(2);x0 << -1.2,1;\r\n    // get derivative\r\n    Vector dx0(2);\r\n    Drosenbrock(x0,dx0);\r\n    // verify gradient by finite differences\r\n    checkGradient(rosenbrock,x0,dx0);\r\n\r\n    BfgsSolver g;\r\n    g.solve(x0,rosenbrock,Drosenbrock);\r\n\r\n// prints      -nan -nan\r\n    std::cout << std::endl<<std::endl<< x0.transpose();\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/comments/74277011","html_url":"https://github.com/PatWie/CppNumericalSolvers/issues/4#issuecomment-74277011","issue_url":"https://api.github.com/repos/PatWie/CppNumericalSolvers/issues/4","id":74277011,"user":{"login":"tosttost","id":9272432,"avatar_url":"https://avatars.githubusercontent.com/u/9272432?v=3","gravatar_id":"","url":"https://api.github.com/users/tosttost","html_url":"https://github.com/tosttost","followers_url":"https://api.github.com/users/tosttost/followers","following_url":"https://api.github.com/users/tosttost/following{/other_user}","gists_url":"https://api.github.com/users/tosttost/gists{/gist_id}","starred_url":"https://api.github.com/users/tosttost/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tosttost/subscriptions","organizations_url":"https://api.github.com/users/tosttost/orgs","repos_url":"https://api.github.com/users/tosttost/repos","events_url":"https://api.github.com/users/tosttost/events{/privacy}","received_events_url":"https://api.github.com/users/tosttost/received_events","type":"User","site_admin":false},"created_at":"2015-02-13T16:04:08Z","updated_at":"2015-02-13T16:04:08Z","body":"\"My intension was to use a better approximation (2nd order instead of 1st order) for the line search.\"\r\nAs far as I see neither armijo rule nor your fix does not use any approximation of the function in the search direction to find the stepwidth. You only modified the acceptance criterion based on H. Note that H in BFGS is not the hessian but converges against the inverse of the hessian. The acceptance criterion uses the slope of f in the search direction (and with the fix, H) to ensure sufficient reduction of the function value. This alone is not sufficient for BFGS. \r\nFor BFGS the (strong) Wolfe conditions work well:\r\n1. f(x + t*d) <= f(x) + t*constparam*f'(x)   // satisfied with the armijo rule \r\n2. |f'(x + t*d)| <= -sigma*f'(x)    // not satisfied with the armijo rule\r\nwith\r\nsigma < 1 and f'(*) = d.transpose*grad_f(*)\r\n\r\nI do not know about  lbfgs.c linesearch but a the wolfe conditions are mention in the docs, so it probably works.\r\n\r\n\"THE PERFORMANCE OF A MODIFIED ARMIJO LINE SEARCH RULE IN BFGS OPTIMIZATION METHOD\" \r\nI am not sure that is a good paper. I take a quick look at reference [9] where the new linesearch is presented. BFGS is not mentioned at all and the BFGS would have to work with B=H.inverse() in order to have an approximation of the hessian. This requires to solve a set of linear linear equations (or to invert a matrix) in order to calculate the search direction (and use the BFGS update formula for B).\r\n\r\nMy implementation of Flechter's linesearch needs a lot of refactoring and it still evaluates the function more often than reported by Fletcher. The algorithm is much longer than the Armijo rule. At the moment it exists only on my disk and needs some work before it can be published on github. I have a lot of other work, so it could take some time. \r\n\r\nMay the GSL implementation (written in C) helps - it is based on the same description:\r\n- http://www.gnu.org/software/gsl/\r\n- Download version 1.16 sourcecode \r\n- the linesearch is the \"minimize\" function in gsl-1.16/multimin/linear_minimize.c\r\n\r\nPull request / fork: not a real option, because for my purpose it is best to have no C++ code (in special, no C++ templates) at all. Additionally my knowledge of C++ is quite limited - sorry!"}}