×

zbMATH — the first resource for mathematics

On the formulation and theory of the Newton interior-point method for nonlinear programming. (English) Zbl 0851.90115
Summary: We first study in detail the formulation of the primal-dual interior-point method for linear programming. We show that, contrary to popular belief, it cannot be viewed as a damped Newton method applied to the Karush-Kuhn-Tucker conditions for the logarithmic barrier function problem. Next, we extend the formulation to general nonlinear programming, and then validate this extension by demonstrating that this algorithm can be implemented so that it is locally and \(Q\)-quadratically convergent under only the standard Newton method assumptions. We also establish a global convergence theory for this algorithm and include promising numerical experimentation.

MSC:
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
90C05 Linear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Lustig, J., Marsten, R. E., andShanno, D. F.,On Implementing Mehrotra’s Predictor-Corrector Interior-Point Method for Linear Programming, SIAM Journal on Optimization, Vol. 2, pp. 435–449, 1992. · Zbl 0771.90066 · doi:10.1137/0802022
[2] Wright, M. H.,Interior Methods for Constrained Optimization, Numerical Analysis Manuscript 91-10, ATT Bell Laboratories, Murray Hill, New Jersey, 1991.
[3] Nash, S. G., andSofer, A.,A Barrier Method for Large-Scale Constrained Optimization, Technical Report 91-10, Department of Operations Research and Applied Statistics, George Mason University, Fairfax, Virginia, 1991.
[4] Wright, S. J.,A Superlinear Infeasible-Interior-Point Algorithm for Monotone Nonlinear Complementarity Problems, Technical Report MCS-P344-1292, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois, 1992.
[5] Monteiro, R. C., Pang, J., andWang, T.,A Positive Algorithm for the Nonlinear Complementarity Problem, Technical Report, Department of Systems and Industrial Engineering, University of Arizona, Tucson, Arizona, 1992.
[6] Wright, S. J.,An Interior-Point Algorithm for Linearly Constrained Optimization, SIAM Journal on Optimization, Vol. 2, pp. 450–473, 1992. · Zbl 0755.65063 · doi:10.1137/0802023
[7] Lasdon, L., Yu, G., andPlummer, J.,An Interior-Point Algorithm for Solving General Nonlinear Programming Problems, Paper Presented at the SIAM Conference on Optimization, Chicago, Illinois, 1992.
[8] Yamashita, H.,A Globally Convergent Primal-Dual Interior Point Method for Constrained Optimization, Technical Report, Mathematical Systems Institute, Tokyo, Japan, 1992.
[9] McCormick, G. P.,The Superlinear Convergence of a Nonlinear Primal-Dual Algorithm, Technical Report T-550/91, School of Engineering and Applied Science, George Washington University, Washington, DC, 1991.
[10] Anstreicher, K. M., andVial, J.,On the Convergence of an Infeasible Primal-Dual Interior-Point Method for Convex Programming, Optimizations Methods and Software, (to appear).
[11] Kojima, M., Megiddo, N., andNoma, N.,Homotopy Continuation Methods for Nonlinear Complementarity Problems, Mathematics of Operations Research, Vol. 16, pp. 754–774, 1991. · Zbl 0744.90087 · doi:10.1287/moor.16.4.754
[12] Monteiro, R. C., andWright, S. J.,A Globally and Superlinearly Convergent Potential Reduction Interior-Point Method for Convex Programming, Unpublished Manuscript, 1992.
[13] Kojima, M., Mizuno, S., andYoshise, A.,A Primal-Dual Interior-Point Method for Linear Programming, Progress in Mathematical Programming, Interior-Point and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, New York, 1989. · Zbl 0708.90049
[14] Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Technique, John Wiley and Sons, New York, New York, 1968. · Zbl 0193.18805
[15] Megiddo, N.,Pathways to the Optimal Set in Linear Programming, Progress in Mathematical Programming, Interior-Point and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, New York, 1989. · Zbl 0687.90056
[16] Hestenes, M. R.,Multiplier and Gradient Methods, Journal of Optimization Theory and Applications, Vol. 4, pp. 303–329, 1969. · Zbl 0174.20705 · doi:10.1007/BF00927673
[17] Tapia, R. A.,On the Role of Slack Variables in Quasi-Newton Methods for Constrained Optimization, Numerical Optimization of Dynamic Systems; Edited by L. C. W. Dixon and G. P. Szegö, North Holland, Amsterdam, Holland, 1980. · Zbl 0457.90070
[18] El-Bakry, A. S., Tapia, R. A., andZhang, Y.,A Study of Indicators for Identifying Zero Variables in Interior-Point Methods, SIAM Review, Vol. 36, pp. 45–72, 1994. · Zbl 0801.65056 · doi:10.1137/1036003
[19] Zhang, Y., Tapia, R. A., andDennis, J. E., Jr.,On the Superlinear and Quadratic Convergence of Primal-Dual Interior-Point Linear Programming Algorithms, SIAM Journal on Optimization, Vol. 2, pp. 304–324, 1992. · Zbl 0763.90066 · doi:10.1137/0802015
[20] Zhang, Y., andTapia, R. A.,Superlinear and Quadratic Convergence of Primal-Dual Interior-Point Algorithms for Linear Programming Revisited, Journal of Optimization Theory and Applications, Vol. 73, pp. 229–242, 1992. · Zbl 0792.90078 · doi:10.1007/BF00940179
[21] Dennis, J. E., Jr., andSchnabel, R. B.,Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1983.
[22] Ortega, J. M., andRheinboldt, W. C.,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970. · Zbl 0241.65046
[23] Byrd, R. H., andNocedal, J.,A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Minimization, SIAM Journal on Numerical Analysis, Vol. 26, pp. 727–739, 1989. · Zbl 0676.65061 · doi:10.1137/0726042
[24] Hock, W., andSchittkowski, K.,Test Examples for Nonlinear Programming Codes, Springer Verlag, New York, New York, 1981. · Zbl 0452.90038
[25] Schittkowski, K.,More Test Examples for Nonlinear Programming Codes, Springer Verlag, New York, New York, 1987. · Zbl 0658.90060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.