Abstract
To generalize the descent methods of unconstrained optimization to the constrained case, we define intrinsically the gradient field of the objective function on the constraint manifold and analyze descent methods along geodesics, including the gradient projection and reduced gradient methods for special choices of coordinate systems. In particular, we generalize the quasi-Newton methods and establish their superlinear convergence; we show that they only require the updating of a reduced size matrix. In practice, the geodesic search is approximated by a tangent step followed by a constraints restoration or by a simple arc search again followed by a restoration step.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Gabay, D., andLuenberger, D. G.,Efficiently Converging Minimization Methods Based on the Reduced Gradient, SIAM Journal on Control and Optimization, Vol. 14, pp. 42–61, 1976.
Luenberger, D. G.,The Gradient Projection Method along Geodesics, Management Science, Vol. 18, pp. 620–631, 1972.
Rosen, J. B.,The Gradient Projection Method for Nonlinear Programming: Part II, Nonlinear Constraints, SIAM Journal on Applied Mathematics, Vol. 9, pp. 514–522, 1961.
Lichnewsky, A.,Minimisation de Fonctionnelles Définies sur une Variété par la Méthode du Gradient Conjugué, Thèse de Doctorat d'Etat, Université de Paris-Sud, Paris, France, 1979.
Abadie, J., andGuigou, J.,Numerical Experiments with the GRG Method, Integer and Nonlinear Programming, Edited by J. Abadie, North-Holland Publishing Company, Amsterdam, Holland, pp. 529–536, 1970.
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.
Milnor, J. W.,Topology from the Differential Viewpoint, University Press of Virginia, Charlottesville, Virginia, 1965.
Stewart, G. W.,Introduction to Matrix Computations, Academic Press, New York, New York, 1973.
Guillemin, V., andPollack, A.,Differential Topology, Prentice-Hall, Englewood Cliffs, New Jersey, 1974.
Milnor, J. W.,Morse Theory, Princeton University Press, Princeton, New Jersey, 1969.
Hicks, N. J.,Notes on Differential Geometry, Van Nostrand Publishing Company, Princeton, New Jersey, 1965.
Bishop, R. L., andCrittenden, R. J.,Geometry of Manifolds, Academic Press, New York, New York, 1964.
Luenberger, D. G.,Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company, Reading, Massachusetts, 1973.
Hirsch, M. W.,Differential Topology, Springer, New York, New York, 1976.
Golubitsky, M., andGuillemin, V.,Stable Mapping and Their Singularities, Springer, New York, New York, 1973.
Hestenes, M. R.,Optimization Theory, The Finite Dimensional Case, John Wiley and Sons, New York, New York, 1975.
Polak, E.,Computational Methods in Optimization, A Unified Approach, Academic Press, New York, New York, 1971.
Ortega, J. M., andRheinboldt, N. C.,Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.
McCormick, G. P.,A Modification of Armijo's Stepsize Rule for Negative Curvature, Mathematical Programming, Vol. 13, pp. 111–115, 1977.
Moré, J. J., andSorensen, D. C.,On the Use of Directions of Negative Curvature in a Modified Newton Method, Mathematical Programming, Vol. 16, pp. 1–20, 1979.
Dennis, J. E., andMoré, J. J.,Quasi-Newton Methods, Motivation and Theory, SIAM Review, Vol. 19, pp. 46–89, 1977.
Powell, M. J. D.,Some Global Convergence Properties of a Variable Metric Algorithm for Minimization without Exact Line Searches, Paper Presented at the AMS/SIAM Symposium on Nonlinear Programming, New York, New York, 1976.
Dennis, J. E., andMoré, J. J.,A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods, Mathematics of Computation, Vol. 28, pp. 549–560, 1974.
Gabay, D.,Efficient Convergence of Implementable Gradient Algorithms and Stepsize Selection Procedures for Constrained Minimization, International Computing Symposium 1975, Edited by E. Gelenbe and D. Potier, North-Holland Publishing Company, Amsterdam, Holland, pp. 37–43, 1975.
Gill, P. E., andMurray, W.,Quasi-Newton Methods for Unconstrained Optimization, Journal of the Institute of Mathematics and Applications, Vol. 9, pp. 91–108, 1972.
Gill, P. E., andMurray, W.,Quasi-Newton Methods for Linearly Constrained Optimization, Numerical Methods for Constrained Optimization, Edited by P. E. Gill and W. Murray, Academic Press, New York, London, 1974.
Goldfarb, D.,Extension of Davidon's Variable Metric Method to Maximization under Linear Inequality and Equality Constraints, SIAM Journal on Applied Mathematics, Vol. 17, pp. 739–764, 1969.
Mukai, H., andPolak, E.,On the Use of Approximations in Algorithms for Optimization Problems with Equality and Inequality Constraints, SIAM Journal on Numerical Analysis, Vol. 13, pp. 674–693, 1978.
Tanabe, K.,A Geometric Method in Nonlinear Programming, Journal of Optimization Theory and Applications, Vol. 30, pp. 181–210, 1980.
Tanabe, K.,Differential Geometry Approach to Extended GRG Methods with Enforced Feasibility in Nonlinear Programming: Global Analysis, Recent Applications of Generalized Inverses, Edited by M. Z. Nashed, Pitman, London (to appear).
Gabay, D.,Reduced Quasi-Newton Methods with Feasibility Improvement for Nonlinearly Constrained Optimization, Mathematical Programming Studies (to appear).
Author information
Authors and Affiliations
Additional information
Communicated by D. G. Luenberger
Rights and permissions
About this article
Cite this article
Gabay, D. Minimizing a differentiable function over a differential manifold. J Optim Theory Appl 37, 177–219 (1982). https://doi.org/10.1007/BF00934767
Issue Date:
DOI: https://doi.org/10.1007/BF00934767