Attraction of Newton method to critical Lagrange multipliers: fully quadratic case

• 成果类型: Article
• 署名作者: Izmailov, A. F.; Uskov, E. I.
• 署名单位: Lomonosov Moscow State University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0777-x
• 发表日期: 2015
• 页码: 33-73
• 关键词: singular points; CONVERGENCE

摘要

In this paper we continue the studies of the persistent effect of attraction of Newton-type iterations for optimality systems to critical Lagrange multipliers. It appears very important to understand the nature of this striking phenomenon, in particular, because it is precisely the reason of slow convergence of such methods when applied to problems with degenerate constraints. All previously known results concerned with this effect were a posteriori by nature: they were showing that in case of convergence, the dual limit is in a sense unlikely to be noncritical. This paper suggests the first a priori result in this direction, showing that critical multipliers actually serve as attractors: for a fully quadratic optimization problem with equality constraints, under certain reasonable assumptions we establish actual local convergence of the Newton-Lagrange method to a critical multiplier starting from a dense set around a given critical multiplier. This is an important step forward in understanding the attraction phenomenon.