Skip to main content
SpringerLink
Log in

The polyadic structure of factorable function tensors with applications to high-order minimization techniques

  • Contributed Papers
  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

Factorable functions are shown to have arrays ofNth-order derivatives (tensors) which are naturally computed as sums of generalized outer product matrices (polyads). The computational implications of this for high-order minimization techniques (such as Halley's method of tangent hyperbolas) are investigated. A direct derivation of these high-order techniques is also given.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Jackson, R. H. F.,Tensors, Polyads, and High-Order Methods in Factorable Programming, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1983.

    Google Scholar 

  2. McCormick, G. P.,Nonlinear Programming: Theory, Algorithms, and Applications, John Wiley and Sons, New York, New York, 1983.

    Google Scholar 

  3. Ghaemi, A., andMcCormick, G. P.,Factorable Symbolic SUMT: What Is It? How Is It Used?, Technical Report No. T-402, Institute for Management Science and Engineering, George Washington University, Washington, DC, 1979.

    Google Scholar 

  4. Mylander, W. C., Holmes, R., andMcCormick, G. P.,A Guide to SUMT-Version 4: The Computer Program Implementing the Sequential Unconstrained Minimization Technique for Nonlinear Programming, Technical Report No. RAC-P-63, Research Analysis Corporation, McLean, Virginia, 1971.

    Google Scholar 

  5. Pugh, R. E.,A Language for Nonlinear Programming Problems, Mathematical Programming, Vol. 2, pp. 176–206, 1972.

    Google Scholar 

  6. Kedem, G.,Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software, Vol. 6, pp. 150–165, 1980.

    Google Scholar 

  7. Rall, L. B.,Applications of Software for Automatic Differentiation in Numerical Computations, Computing, Supplement, Vol. 2, pp. 141–156, 1980.

    Google Scholar 

  8. Wengert, R. E.,A Simple Automatic Derivative Evaluation Program, Communications of the Association for Computing Machinery, Vol. 7, pp. 463–464, 1964.

    Google Scholar 

  9. Reiter, A., andGray, J. H.,Compiler for Differentiable Expressions (CODEX) for the CDC 3600, MRC Technical Report No. 791, University of Wisconsin, Madison, Wisconsin, 1967.

    Google Scholar 

  10. Warner, D. D.,A Partial Derivative Generator, Computing Science Technical Report No. 28, Bell Telephone Laboratories, Murray Hill, New Jersey, 1975.

    Google Scholar 

  11. Shayan, M. E.,A Methodology for Comparing Algorithms and a Method for Computing mthOrder Directional Derivatives Based on Factorable Programming, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1978.

    Google Scholar 

  12. Miele, A., andGonzalez, S.,On the Comparative Evaluation of Algorithms for Mathematical Programming Problems, Nonlinear Programming 3, Edited by O. L. Mangasarianet al., Academic Press, New York, New York, pp. 337–359, 1978.

    Google Scholar 

  13. Emami, G.,Evaluating Strategies for Newton's Method Using a Numerically Stable Generalized Inverse Algorithm, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1978.

    Google Scholar 

  14. Ghotb, F.,Newton's Method for Linearly Constrained Optimization Problems, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1980.

    Google Scholar 

  15. Sofer, A.,Computationally Efficient Techniques for Generalized Inversion InNonlinear Programming, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1983.

    Google Scholar 

  16. DeSilva, A., andMcCormick, G. P.,Sensitivity Analysis InNonlinear Programming Using Factorable Symbolic Input, Technical Report No. T-365, Institute for Management Science and Engineering, George Washington University, Washington, DC, 1978.

    Google Scholar 

  17. Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, New York, 1968.

    Google Scholar 

  18. Schnabel, R. B., andFrank, P. D.,Tensor Methods for Nonlinear Equations, Technical Report No. CU-CS-243-83, Department of Computer Science, University of Colorado, Boulder, Colarado, 1983.

    Google Scholar 

  19. Kalaba, R., andTischler, A.,A Generalized Newton Algorithm Using Higher-Order Derivatives, Journal of Optimization Theory and Applications, Vol. 39, pp. 1–17, 1983.

    Google Scholar 

  20. Traub, J. F.,Iterative Methods for the Solution of Equations, Prentice-Hall, Englewood Cliffs, New Jersey, 1964.

    Google Scholar 

  21. Ortega, J. M., andRheinboldt, W. C.,Iterative Solutions of Nonlinear Equations in Several Variables, Academic Press, New York, New York, 1970.

    Google Scholar 

  22. Altman, M.,Iterative Methods of Higher Order, Bulletin de l'Academie Polonaise des Sciences, Serie des Sciences Mathematiques, Astronomiques, et Physiques, Vol. 9, pp. 63–68, 1961.

    Google Scholar 

  23. Doring, B.,Einige Satze uber das Verfahren der Tangierenden Hyperbeln in Banach-Raumen, Aplikace Matematiky, Vol. 15, pp. 418–464, 1970.

    Google Scholar 

  24. Halley, E.,Methodus Nova, Accurata & Facilis Inveniendi Radices Aequationum Quarumcumque Generaliter, Sine Praevia Reductione, Philosophical Transactions of the Royal Society of London, Vol. 18, pp. 136–148, 1694 (in Latin).

    Google Scholar 

  25. Alefeld, G.,On the Convergence of Halley's Method, American Mathematical Monthly, Vol. 88, pp. 530–536, 1981.

    Google Scholar 

  26. Salehov, S.,On the Convergence of the Process of Tangent Hyperbolas, Doklady Akademii Nauk, Vol. 82, pp. 515–528, 1952 (in Russian).

    Google Scholar 

  27. Schroder, E.,Ueber Unendlich Viele Algorithmen zur Auflosung der Gleichungen, Mathematische Annalen, Vol. 2, pp. 317–365, 1870.

    Google Scholar 

  28. Frame, J. S.,A Variation of Newton's Method, American Mathematical Monthly, Vol. 51, pp. 36–38, 1944.

    Google Scholar 

  29. Richmond, H. W.,On Certain Formulae for Numerical Approximation, Journal of the London Mathematical Society, Vol. 19, pp. 31–38, 1944.

    Google Scholar 

  30. Wall, H. S.,A Modification of Newton's Method, American Mathematical Monthly, Vol. 55, pp. 90–94, 1948.

    Google Scholar 

  31. Brown, G. H.,On Halley's Variation of Newton's Method, American Mathematical Monthly, Vol. 84, pp. 726–727, 1977.

    Google Scholar 

  32. Necepurenko, M. I.,On Tchebyshev's Method for Functional Equations, Uspekhi Matematicheskikh Nauk, Vol. 9, pp. 163–170, 1954 (in Russian).

    Google Scholar 

  33. Altman, M.,An Iterative Method of Solving Functional Equations, Bulletin de l'Academie Polonaise des Sciences, Serie des Sciences de Mathematiques, Astronomiques, et Physiques, Vol. 9, pp. 57–62, 1961.

    Google Scholar 

  34. Janko, B.,Sur les Methodes d'Iteration pour la Resolution des Equations Fonctionelles Nonlineaires Definies dans l'Espace de Banach, Revue Roumaine de Mathematiques Pures et Appliquées, Vol. 18, pp. 43–52, 1973.

    Google Scholar 

  35. Euler, L.,Institutionum Calculi Differentiales, Opera Postuma: Mathematica et Physica, Krauss Reprint, Berlin, West Germany, pp. 342–402, 1969.

  36. Chebyshev, P. L.,Ouevres (Publiées paree Soins de A. Markoff et N. Sonin) Chelsea, New York, New York, 1962.

    Google Scholar 

  37. Bodewig, E.,On Types of Convergence and on the Behavior of Approximations in the Neighborhood of a Multiple Root of an Equation, Quarterly of Applied Mathematics, Vol. 7, pp. 325–333, 1949.

    Google Scholar 

  38. Kronsjo, L. I.,Algorithms: Their Complexity and Efficiency, John Wiley and Sons, New York, New York, 1979.

    Google Scholar 

  39. Falk, J. E., andMcCormick, J. E.,Mathematical Structure of the International Coal Trade Model: Final Report, Technical Report No. DOE/NBB-0025, US Department of Energy, Washington, DC, 1982.

    Google Scholar 

  40. McCormick, G. P.,Global Solutions to Factorable Nonlinear Optimization Problems Using Separable Programming Techniques, NBS Technical Report No. NBS-IR85-3206, 1984.

  41. Falk, J. E., andSoland, R. M.,An Algorithm for Separable Nonconvex Programming Problems, Management Science, Vol. 15, pp. 550–569, 1969.

    Google Scholar 

  42. Falk, J. E.,Global Solutions of Signomial Problems, Technical Report No. T-274, Department of Operations Research, George Washington University, Washington, DC, 1973.

    Google Scholar 

  43. Hoffman, K. L.,NUGLOBAL—User Guide, Technical Report No. TM-64866, Department of Operations Research, George Washington University, Washington, DC, 1975.

    Google Scholar 

  44. McCormick, G. P.,Computability of Global Solutions to Factorable Nonconvex Programs: Part I—Convex Underestimating Problems, Mathematical Programming, Vol. 10, pp. 147–175, 1976.

    Google Scholar 

  45. Leaver, S. G.,Computing Global Maximum Likelihood Parameter Estimates for Product Models for Frequency Tables Involving Indirect Observation, Dissertation, Department of Operations Research, George Washington University, Washington, DC, 1984.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Applied Mathematics, National Bureau of Standards, Gaithersburg, Maryland

    R. H. F. Jackson (Mathematician)

  2. Department of Operations Research, George Washington University, Washington, DC

    G. P. McCormick (Professor of Applied Science)

Authors
  1. R. H. F. Jackson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. P. McCormick
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Communicated by O. L. Mangasarian

This research was sponsored in part by the Office of Naval Research under Contract No. N00014-82-K.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jackson, R.H.F., McCormick, G.P. The polyadic structure of factorable function tensors with applications to high-order minimization techniques. J Optim Theory Appl 51, 63–94 (1986). https://doi.org/10.1007/BF00938603

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00938603

Key Words

Search

Navigation