ИСТИНА

An important class of optimization problems consists of problems violating standard constraint qualifications. An interest to such problems is motivated by the serious theoretical and computational difficulties inherent in them and by related applications [1]. In particular, traditional Newton-type methods applied to such problems usually show low convergence rate. On the other hand, as was demonstrated in [2]–[4], the reason for the lack of superlinear convergence rate is a certain undesirable behavior of the dual sequences. Namely, theoretical and computational analysis demonstrates that dual sequences of Newton-type methods have a strong tendency to converge to the so-called critical multipliers which usually form a thin subset in the set of all Lagrange multipliers. In this presentation we analyze the influence of critical multipliers on another well-known optimization algorithm, Augmented Lagrangian method (or the multiplier method). This method underlies several successful solvers such as LANCELOT and ALGENCAN, and it has a number of very attractive properties, including a strong theory of local [5] and global [6] convergence on degenerate problems. In particular, no constraint qualifications are required for local superlinear convergence of the multiplier method. However, as in the case of Newton-type methods, the attraction of dual sequences to critical multipliers may result in the lack of superlinear convergence. In this presentation we examine how typical is the effect of attraction of the dual sequences to critical multipliers for the multiplier method. We also analyze the influence of this effect on the convergence rate of the multiplier method and on the efficiency of various techniques for accelerating the final stage of this method. References [1] Golishnikov M.M., Izmailov A.F. Newton-type Methods for Constrained Optimization with Nonregular Constraints // Comput. Math. Math. Phys. 2006. V. 46. P. 1299–1319. [2] Izmailov A.F., Solodov M.V. Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints // Comput. Optim. Appl. 2009. V. 42. N. 2. P. 231–264. [3] Izmailov A.F., Solodov M.V. On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions // Math. Program. 2009. V. 117. N. 1–2. P. 271–304. [4] Izmailov A.F., Solodov M.V. On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers // Math. Program. 2011. V. 128. N. 2. P. 231–257. [5] D. Fern´andez and M.V. Solodov. Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficient optimality condition // SIAM J. Optim. 2012. V. 22. P. 384–407. [6] Izmailov A.F., Solodov M.V., Uskov E.I. Augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints // SIAM J. Optim. 2012. V. 22. P. 1579–1606.