Abstract
This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.P. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982).
C.G. Broyden, J.E. Dennis, Jr. and J.J. Moré, “On the local and superlinear convergence of quasi-Newton methods”,Journal of the Institute of Mathematics andits Applications 12 (1973) 223–245.
J.E. Dennis, Jr. and J.J. Moré, “A characterization of superlinear convergence and its application to quasi-Newton methods”,Mathematics of Computation 28 (1974) 549–560
A.S. El-Bakry, R.A. Tapia, T. Tsuchiya and Y. Zhang, “On the formulation and theory of the primal-dual Newton interior-point method for nonlinear programming”, TR92-40, Department of Computational and Applied Mathematics, Rice University, TX, USA, 1992.
A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (SIAM, Philadelphia, PA, 1990).
R. Fletcher,Practical Methods of Optimization (2nd ed., Wiley, New York, 1987).
D.M. Gay, “Electronic mail distribution of linear programming test problems”,Mathematical Programming Society COAL Newsletter 13 (1985) 10–12.
W. Hock and K. Schittkowski,Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, Vol. 187 (Springer-Verlag, Berlin, 1981).
M. Kojima, N. Megiddo and S. Mizuno, “A primal-dual infeasible-interior-point algorithm for linear programming”,Mathematical Programming 61 (1993) 263–280.
M. Kojima, S. Mizuno and A. Yoshise, “A primal-dual interior-point algorithm for linear programming”, in: N. Megiddo, ed.,Progress in Mathematical Programming, Interior-Point and Related Methods (Springer-Verlag, New York, 1989) pp. 29–47.
L.S. Lasdon, J. Plummer and G. Yu, “Primal-dual and primal interior point algorithms for general nonlinear programs,’ Manuscript, 1993.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “Computational experience with a primal-dual interior point method for linear programming”.Linear Algebra and its Applications 152 (1991) 191–222.
G.P. McCormick, “Resolving the shell dual with a nonlinear primal-dual algorithm”, Report GWU/OR/Serial T-545/91. Department of Operations Research, The George Washington University, Washington, DC, USA, 1991.
G.P. McCormick and J.E. Falk, “The superlinear convergence of a nonlinear primal-dual algorithm”, Report GWU/OR/Serial T-550/91, Department of Operations Research, The George Washington University, Washington DC, USA, 1991.
K.A. McShane, C.L. Monma and D.F. Shanno, “An implementation of a primal-dual interior point method for linear programming,”ORSA Journal on Computing 1 (1989) 70–83.
S. Mizuno, M.J. Todd and Y. Ye, “On adaptive step primal-dual interior-point algorithms for linear programming,”Mathematics of Operations Research 18 (1993) 964–981.
J.M. Ortega and W.C. Rheinboldt,Iterative Solution of Nonlinear Equations in Several Variables (Academic Press, New York, 1970).
J-P. Vial, “Computational experience with a primal-dual interior-point method for smooth convex programming”,Optimization Methods and Software 3 (1994) 285–310.
H. Yamashita, “A globally convergent primal-dual interior point method for constrained optimization”, Technical Report, Mathematical Systems Institute, Inc., Tokyo, Japan, 1992.
Y. Zhang, “On the convergence of a class of infeasible interior-point algorithms for the horizontal linear complementarity problem”,SIAM Journal on Optimization 4 (1994) 208–227.
Y. Zhang and R.A. Tapia, “Superlinear and quadratic convergence of primal-dual interior point methods for linear programming revisited,”Journal of Optimization Theory and Applications 73 (1992) 229–242.
Y. Zhang, R.A. Tapia and J.E. Dennis, Jr., “On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms,”SIAM Journal on Optimization 2 (1992) 304–324.
Y. Zhang, R.A. Tapia and F. Potra, “On the superlinear convergence of interior point algorithms for a general class of problems”, Technical Report TR90-9, Department of Mathematical Sciences, Rice University, TX, USA, 1990.
Author information
Authors and Affiliations
Additional information
A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.
Rights and permissions
About this article
Cite this article
Yamashita, H., Yabe, H. Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization. Mathematical Programming 75, 377–397 (1996). https://doi.org/10.1007/BF02592190
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02592190