A perfect example for the BFGS method

• 成果类型: Article
• 署名作者: Dai, Yu-Hong
• 署名单位: Chinese Academy of Sciences; Academy of Mathematics & System Sciences, CAS
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-012-0522-2
• 发表日期: 2013
• 页码: 501-530
• 关键词: quasi-newton methods; unconstrained optimization; GLOBAL CONVERGENCE

摘要

Consider the BFGS quasi-Newton method applied to a general non-convex function that has continuous second derivatives. This paper aims to construct a four-dimensional example such that the BFGS method need not converge. The example is perfect in the following sense: (a) All the stepsizes are exactly equal to one; the unit stepsize can also be accepted by various line searches including the Wolfe line search and the Arjimo line search; (b) The objective function is strongly convex along each search direction although it is not in itself. The unit stepsize is the unique minimizer of each line search function. Hence the example also applies to the global line search and the line search that always picks the first local minimizer; (c) The objective function is polynomial and hence is infinitely continuously differentiable. If relaxing the convexity requirement of the line search function; namely, (b) we are able to construct a relatively simple polynomial example.