Accelerating Newton-type Methods in the Presence of Critical Solutions

• Applicant: Professor Dr. Andreas Fischer
• Subject Area: Mathematics
• Term: from 2019 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 409756759

• Final Report Year: 2023

Final Report Abstract

The project dealt with the design and analysis of Newton-type methods for the solution of systems of nonlinear equations and related problems under circumstances which are rather non-standard. This includes problems with particular singular (possibly nonisolated) solutions as well as those satisfying only reduced smoothness assumptions. Such circumstances usually cause difficulties related to the well-definedness, convergence, or convergence speed of Newton-type methods. The project aimed at theoretical and practical aspects to study ways to overcome such difficulties. In particular, a procedure for adjusting dual variables was constructed and analyzed which can prevent the convergence of primal-dual Newton type methods for smooth optimization problems to solutions with critical Lagrange multipliers and, thus, avoid slow convergence. Moreover, for systems of nonlinear equations having critical solutions, a linesearch globalization was studied. Based on the analysis of the convergence pattern, it could be shown that the unit steplength is asymptotically accepted under reasonable assumptions, in particular about the 2-regularity of a solution. Based on this, the use of acceleration schemes becomes possible. The influence of extrapolation and overrelaxation was tested numerically. Extrapolation significantly improved the efficiency. In addition, for problems with only piecewise smooth mappings, the analysis of the convergence pattern could be extended for a large class of perturbed Newton methods including the acceptance of the unit steplength of the piecewise Newton method. The project’s outcome is completed by new results on stability properties of singular and nonsingular solutions of a system of piecewise smooth nonlinear equations. Also, necessary and sufficient conditions for the existence of Lipschitzian local error bounds for constrained systems of equations with reduced smoothness were obtained.

Publications

• Accelerating convergence of the globalized Newton method to critical solutions of nonlinear equations. Computational Optimization and Applications, 78(1), 273-286.
  Fischer, A.; Izmailov, A. F. & Solodov, M. V.
  
• Adjusting Dual Iterates in the Presence of Critical Lagrange Multipliers. SIAM Journal on Optimization, 30(2), 1555-1581.
  Fischer, Andreas; Izmailov, Alexey F. & Scheck, Wladimir
  
• Unit stepsize for the Newton method close to critical solutions. Mathematical Programming, 187(1-2), 697-721.
  Fischer, A.; Izmailov, A. F. & Solodov, M. V.
  
• Newton-type methods near critical solutions of piecewise smooth nonlinear equations. Computational Optimization and Applications, 80(2), 587-615.
  Fischer, A.; Izmailov, A. F. & Jelitte, M.
  
• Stability of Singular Solutions of Nonlinear Equations with Restricted Smoothness Assumptions. Journal of Optimization Theory and Applications, 196(3), 1008-1035.
  Fischer, Andreas; Izmailov, Alexey F. & Jelitte, Mario