Abstract
A differential geometric approach to the constrained function maximization problem is presented. The continuous analogue of the Newton-Raphson method due to Branin for solving a system of nonlinear equations is extended to the case where the system is under-determined. The method is combined with the continuous analogue of the gradient-projection method to obtain a constrained maximization method with enforced constraint restoration. Detailed analysis of the global behavior of both methods is provided. It is shown that the conjugate-gradient algorithm can take advantage of the sparse structure of the problem in the computation of a vector field, which constitutes the main computational task in the methods.
Similar content being viewed by others
References
Zoutendijk, G.,Method of Feasible Directions, A Survey in Linear and Nonlinear Programming, American Elsevier Publishing Company, Amsterdam, Holland, 1960.
Rosen, J. B.,The Gradient Projection Method for Nonlinear Programming: Part II, Nonlinear Constraints, SIAM Journal on Applied Mathematics, Vol. 9, pp. 514–532, 1961.
Abadie, J., andCarpentier, J.,Generalization of the Wolfe Reduced Gradient Method to the Case of Nonlinear Constraints, Optimization, Edited by R. Fletcher, Academic Press, London, England, 1969.
Tanabe, K.,Algorithm for Constrained Maximization Technique for Nonlinear Programming, Proceedings of the Second Hawaii International Conference on System Sciences, pp. 487–490, Honolulu, Hawaii, 1969.
Tanabe, K.,An Algorithm for Constrained Maximization in Nonlinear Programming, Institute of Statistical Mathematics, Research Memorandum No. 31, 1969.
Tanabe, K.,An Algorithm for Constrained Maximization in Nonlinear Programming, Journal of the Operations Research Society of Japan, Vol. 17, pp. 184–201, 1974.
Gruver, W. A., andEngersbach, N. H.,A Variable-Metric Algorithm for Constrained Minimization Based on an Augmented Lagrangian, International Journal of Numerical Methods in Engineering, Vol. 10, pp. 1047–1056, 1976.
Carroll, C. W.,The Created Response Surface Technique for Optimizing Nonlinear Restricted Systems, Operations Research, Vol. 9, p. 169, 1961.
Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, New York, 1968.
Hestenes, M. R.,Multiplier and Gradient Methods, Journal of Optimization Theory and Applications, Vol. 4, pp. 303–320, 1969.
Powell, M. J. D.,A Method for Nonlinear Constraints in Minimization Problems, Optimization, Edited by R. Fletcher, Academic Press, London, England, 1969.
Fletcher, R.,A Class of Methods for Nonlinear Programming with Termination and Convergence Properties, Integer and Nonlinear Programming, Edited by J. Abadie, North Holland Publishing Company, Amsterdam, Holland, 1970.
Fletcher, R., andLill, S. A.,A Class of Methods for Nonlinear Programming: Part II, Computational Experience, Nonlinear Programming, Edited by J. B. Rosen et al., Academic Press, New York, New York, 1970.
Fletcher, R. A Class of Methods for Nonlinear Programming: Part III, Rate of Convergence, Numerical Methods for Nonlinear Optimization, Edited by F. A. Lootsma, Academic Press, London, England, 1972.
Fletcher, R.,An Exact Penalty Function for Nonlinear Programming with Inequalities, Mathematical Programming, Vol. 5, pp. 129–150, 1973.
Martensson, K.,A New Approach to Constrained Function Optimization, Journal of Optimization Theory and Applications, Vol. 12, pp. 531–554, 1973.
Rockafellar, R. T.,The Multiplier Method of Hestenes and Powell Applied to Convex Programming, Journal of Optimization Theory and Applications, Vol. 12, pp. 555–562, 1973.
Rupp, R. D.,On the Combination of the Multiplier Method of Hestenes and Powell with Newton's Method, Journal of Optimization Theory and Applications, Vol. 15, pp. 167–187, 1975.
Bertsekas, D. P.,Combined Primal-Dual Penalty Methods for Constrained Minimization, SIAM Journal on Control, Vol. 13, pp. 521–544, 1975.
Bertsekas, D. P.,Multiplier Methods: A Survey, Automatica, Vol. 12, pp. 133–145, 1976.
Tapia, R. A.,Diagonalized Multiplier Methods and Quasi-Newton Methods for Constrained Optimization (to appear).
Kelley, H. J., Denham, W. F., Johnson, I. L., andWheatley P. O.,An Accelerated Gradient Method for Parameter Optimization with Nonlinear Constraints, Journal of the Astronautical Sciences, Vol. 13, pp. 166–169, 1966.
Bard, Y., andGreenstadt, J. L.,A Modified Newton Method for Optimization with Equality Constraints, Optimization, Edited by R. Fletcher, Academic Press, London, England, 1968.
Kwakernaak, H., andStrijbos, R. C. W.,Extremization of Functions with Equality Constraints, Mathematical Programming, Vol. 2, pp. 279–295, 1972.
Huang, Y. H., andNaqvi, S.,Unconstrained Approach to the Extremization of Constrained Functions, Journal of Mathematical Analysis and Applications, Vol. 39, pp. 360–374, 1972.
Huang, H. Y., andAggarwal, A. K.,A Class of Quadratically Convergent Algorithms for Constrained Function Minimization, Journal of Optimization Theory and Applications, Vol. 16, pp. 447–485, 1975.
Dennis, J. E., andMore, J. J.,A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, pp. 549–560, 1974.
McCormick, G. P.,Penalty Function versus Nonpenalty Function Methods for Constrained Nonlinear Programmining Problems, Mathematical Programming, Vol. 1, 217–238, 1971.
Yamashita, H.,Differential Equation Approach to Nonlinear Programming, Computation and Analysis, Vol. 7, pp. 11–38, 1976.
Tanabe, K.,Analog-Type Nonlinear Programming (in Japanese), Mathematical Sciences, Vol. 157, pp. 45–51, 1976.
Branin, F. H.,Widely Convergent Method for Finding Multiple Solutions of Simultaneous Nonlinear Equations, IBM Journal of Research and Development, Vol. 16, pp. 504–521, 1972.
Auslander, L., andMacKenzie, R. E.,Introduction to Differentiable Manifolds, McGraw-Hill, Book Company, New York, New, York, 1963.
Matsushima, Y.,Differentiable Manifolds, Marcel Dekker, New York, New York, 1972.
Abraham, R., andRobbin, J.,Transversal Mapping and Flows, W. A. Benjamin, New York, 1967.
Bhatia, N. P., andSzegö, G. P.,Stability Theory of Dynamical Systems, Springer-Verlag, New York, New York, 1970.
Hancock, H.,Theory of Maxima and Minima, Dover Publications, New York, New York, 1960.
Lambert, J. D.,Compositional Methods in Ordinary Differential Equations, John Wiley and Sons, London, England, 1973.
Chao, K. S., Liu, D. K., andPan, C. T.,A Systematic Search Method for Obtaining Multiple Solutions of Simultaneous Nonlinear Equations, IEEE Transactions on Circuits and Systems, Vol. CAS-22, pp. 748–753, 1975.
Tanabe, K.,Continuous Newton-Raphson Method for Solving an Under-determined System of Nonlinear Equations, Nonlinear Analysis, Theory, Methods, and Applications, Vol. 3, pp. 495–503, 1979.
Tanabe, K.,Global Analysis of Continuous Analogues of the Levenberg-Marquardt and Newton-Raphson Methods for Solving Nonlinear Equations, Brookhaven National Laboratory, Report No. 24022, AMD-789, 1978.
Mangasarian, O. L.,Nonlinear Programming, McGraw-Hill Book Company, New York, New York, 1968.
Afriat, S. N.,Orthogonal and Oblique Projectors and the Characteristics of Pairs of Vector Spaces, Proceedings of the Cambridge Philosophical Society, Vol. 53, pp. 800–816, 1957.
Kammerer, W. J., andNashed, M. Z.,On the Convergence of the Gradient Method for Singular Linear Operator Equations, SIAM Journal on Numerical Analysis, Vol. 9, pp. 165–181, 1972.
Gill, P. E., Golub, G. H., Murray, W., andSaunders, M. A.,Methods for Modifying Matrix Factorizations, Mathematics of Computation, Vol. 28, pp. 505–535, 1974.
Tanabe, K.,A Geometric Method in Nonlinear Programming, Stanford University Computer Science Department, Report No. STAN-CS-643, 1977.
Boggs, P. T.,The Solution of Nonlinear Systems of Equations by A-Stable Integration Techniques, SIAM Journal on Numerical Analysis, Vol. 8, pp. 767–785, 1971.
Tanabe, K.,Differential Geometric Approach to Extended GRG Methods with Enforced Feasibility in Nonlinear Programming: Global Analysis, Brookhaven National Laboratory, Report No. 24497, AMD-797, 1978.
Tanabe, K.,Differential Geometric Methods in Nonlinear Programming, Applied Nonlinear Analysis, Edited by V. Lakshmikantham, Academic Press, New York, New York, 1979.
Tanabe, K.,Differential Geometric Methods for Solving Nonlinear Constrained Optimization Problems and a Related System of Nonlinear Equations: Global Analysis and Implementation, Proceedings of the International Congress on Numerical Methods for Engineering, Paris, France (to appear).
Tanabe, K.,A Unified Theory of Feasibility-Improving Gradient Acute Projection Methods for Nonlinear Constrained Optimization, Brookhaven National Laboratory (to appear).
Miele, A., Huang, H. Y., andHeideman, J. C.,Sequential Gradient-Restoration Algorithm for the Minimization of Constrained Functions, Ordinary and Conjugate Gradient Versions, Journal of Optimization Theory and Applications, Vol. 4, pp. 213–243, 1969.
Miele, A., Moseley, P. E., Levy, A. V., andCoggins, G. M.,On The Method of Multipliers for Mathematical Programming Problems, Journal of Optimization Theory and Applications, Vol. 10, pp. 1–33, 1972.
Author information
Authors and Affiliations
Additional information
Communicated by O. L. Mangasarian
This is part of a paper issued as Stanford University, Computer Science Department Report No. STAN-CS-77-643 (Ref. 45), which was presented at the Gatlinburg VII Conference, Asilomar, California, 1977. This work was supported in part by NSF Grant No. NAT BUR OF ECON RES/PO No. 4369 and by Department of Energy Contract No. EY-76-C-02-0016.
The main part of this work was presented at the Japan-France Seminar on Functional Analysis and Numerical Analysis, Tokyo, Japan, 1976. The paper was prepared in part while the author was a visitor at the Department of Mathematics, North Carolina State University, Raleigh, North Carolina, 1976–77, and was completed while he was a visitor at the Computer Science Department, Stanford University, Stanford, California, 1977. He acknowledges the hospitality and stimulating environment provided by Professor G. H. Golub, Stanford University, and Professors N. J. Rose and C. D. Meyer, North Carolina State University.
Rights and permissions
About this article
Cite this article
Tanabe, K. A geometric method in nonlinear programming. J Optim Theory Appl 30, 181–210 (1980). https://doi.org/10.1007/BF00934495
Issue Date:
DOI: https://doi.org/10.1007/BF00934495