Q-SUPERLINEAR CONVERGENCE OF PRIMAL-DUAL INTERIOR POINT QUASI-NEWTON METHODS FOR CONSTRAINED OPTIMIZATION

概要

論文の詳細を見る
This paper analyzes local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. For this purpose, we first discuss modified Newton methods and modified quasi-Newton methods for solving a nonlinear system of equations, and show local and Q-quadratic/Q-superlinear convergence of these methods. These methods are characterized by a perturbation of the right-hand side of the Newton equation applied to the system, an approximation of the Jacobian matrix by some matrix, and component-wise dampings of the step. By applying these convergence results for the nonlinear system of equations to the primal-dual interior point methods for nonlinear optimization, we obtain convergence results of the primal-dual interior point Newton and quasi-Newton methods. A necessary and sufficient condition for Q-superlinear convergence of the latter methods corresponds to the Dennis-More condition. Furthermore, we present some quasi-Newton updating formulae. Finally, we give an analysis of the Q-rate in a part of variables for the primal-dual interior point quasi-Newton methods, and obtain a necessary and sufficient condition for the Q-rate. This condition is a generalization of the result given by Martinez, Parada and Tapia (1995), which was done independently.
社団法人日本オペレーションズ・リサーチ学会の論文