Harold W. Kuhn

From Wikimization

Revision as of 13:21, 27 July 2009 by Ranjelin (Talk | contribs)
Jump to: navigation, search

The Fermat Point LaTeX: - first appearance of Duality was a Euclidean distance problem

Re: [HM] On-line Article: Fermat Point
Harold W Kuhn (kuhn@math.Princeton.edu)
Fri, 24 Sep 1999 21:57:28 -0400 (EDT) 

Messages sorted by: [date][thread][subject][author] 
Next message: Antreas P. Hatzipolakis: "[HM] Four Euler Lines (was: On-line Article: Fermat Point)" 
Previous message: Alexander Zenkin: "[HM] Complete solution of the "liar" paradox" 
Re: [HM] On-line Article: Fermat Point
Harold W. Kuhn, ca.1961
Harold W. Kuhn, ca.1961

It is always a pleasure to chat with my colleague John Conway, if only by email. We talked a bit in the elevator of Fine Hall (the building housing the Mathematics Department of Princeton University) today but he was on his way to teach a class so this must continue the conversation in public.

John Conway wrote in HM-digest 195:

As in some better-known cases, the result was conjectured by Fermat rather than proved by him. The first recorded proof is by his student, Torricelli (the inventor of the barometer). I can't remember what this was, but might be able to find my notes about it. I do recall that I didn't regard it as a very good proof, so doubt that it was the type of proof you've obviously rediscovered, which is one of the standard ones. There are indeed many references, but I don't have them off by heart; you can ask me again if you don't find any recent ones from someone else (mine are all old ones, and might not be easily accessible to you).

My article, [Kuhn,] On a Pair of Dual Nonlinear Programs (Chapter III of "Nonlinear Programming", edited by J. Abadie, North-Holland Publishing Company, 1967, pp.37-54), contains a historical sketch, from which I shall quote:

"Our story starts with a problem rather casually posed by Fermat early in the 17th century. At the end of his celebrated essay on maxima and minima, in which he presented pre-calculus rules for finding tangents to a variety of curves, he threw out the challenge:

[Primal] Let he who does not approve of my method attempt the solution of the following problem: Given three points in the plane, find a fourth point such that the sum of its distances to the three given points is a minimum!

The problem may have travelled to Italy with Mersenne; it is known that before 1640 Torricelli had solved the problem. He asserted that the circles circumscribing the equilateral triangles constructed on the sides of and outside the given triangle intersect in the point that is sought. This point is called the Torricelli point. Also, in Cavalieri's "Exercitationes geometricae" of 1647, it is shown that the sides of the given triangle subtend angles of 120 degrees from the Torricelli point. Furthermore, Simpson asserted and proved in his "Doctrine and Application of Fluxions" (London, 1750) that the three lines joining the outside vertices of the equilateral triangles defined above to the opposite vertices of the given triangle intersect in the Torricelli point. These three lines are called Simpson lines."

For original sources, see the article by M. Zacharias in the Encyclopaedie der Mathematischen Wissenschaften, III AB 9.

My article then erroneously gives credit to a 19th century mathematician for the original formulation of the dual problem. Further search led to earlier sources. In a remarkable journal, not much read today, "The Ladies Diary or Woman's Almanack" (1755), the following problem is posed by a Mr. Tho. Moss (p.47):

[Dual 1] In the three Sides of an equiangular Field stand three Trees, at the Distances of 10, 12, and 16 Chains from one another; to find the Content of the Field, it being the greatest the Data will admit of.

While there seems to have been no explicit recognition of the connection with Fermat's problem in the Ladies Diary, the observation was not long in coming. In the Annales de Mathematiques Pures et Appliques, edited by J. D. Gergonne, Vol.I (1810-11), we find the following problem posed on p.384:

[Dual 2] Given any triangle, circumscribe the largest possible equilateral triangle about it.

In the solution proposed by Rochat, Fauguier, and Pilatte in Vol.II (1811-12), pp.88-93, the observation is made: "Thus the largest equilateral triangle circumscribing the given triangle has sides perpendicular to the lines joining the vertices of the given triangle to the point such that the sum of the distances to these vertices is a minimum [p.91]. One can conclude that the altitude of the largest equilateral triangle that can be circumscribed about a given triangle has a length that is equal to the sum of distances from the vertices of the given triangle to the point at which the sum of distances is a minimum. [p.92]" The credit for recognizing this duality appears to be due to Vecten, professor of mathematiques speciales at the Licee de Nimes.

My own interest in Fermat's Problem originated in the computational aspects and its application to locational problems (see Kuhn, H. W., and Kuenne, R. E., J. Regional Sci. 4 (1962) 21-33, and the literature cited there). We present an efficient algorithm for solving "General Fermat Problems"; however, my paper of 1967 cited at the beginning of this note contains a proof of the duality theorem by elementary geometrical means, which may be more of interest to the students whose query started this exchange.

I cannot end this historical sketch without mention of the fact that the Fermat problem has been widely popularized by Courant and Robbins (in "What is Mathematics?") under the name of the "Steiner Problem". Although this gifted geometer of the 19th century can be counted among the dozens of mathematicians who have written on the subject, he does not seem to have contributed anything new, either to its formulation or its solution. As for the statement by Courant and Robbins that the generalization of the problem to more than three points is a sterile generalization, their answer is found in the recent literature, which has added new applications and understanding through this "sterile" extension of the problem.

See what happens, when you have a conversation in an elevator John?

Harold W Kuhn

Next message: Antreas P. Hatzipolakis: "[HM] Four Euler Lines (was: On-line Article: Fermat Point)" 
Previous message: Alexander Zenkin: "[HM] Complete solution of the "liar" paradox"

Reprinted from http://sunsite.utk.edu/math_archives/.http/hypermail/historia/sep99/0145.html


Dr. Harold W. Kuhn, Professor Emeritus of Mathematical Economics at Princeton University, was a member of two separate departments of instruction --- Mathematics and Economics. His fields of research include linear and nonlinear programming, theory of games, combinatorial problems, and the application of mathematical techniques to economics.

I was born in Santa Monica, California, on July 29, 1925. I married Estelle Henkin in 1949. We have three sons, six grandsons, and a granddaughter. I am a veteran of service with the U.S. Army from 1944-46. I trained in Japanese in the Army Language Program at Yale University.

After graduating with a B.S. degree in 1947 from the California Institute of Technology, I enrolled in Princeton's Graduate School where I received an M.A. in 1948 and Ph.D. in 1950. I was the Henry B. Fine Instructor in the Mathematics Department for academic year 1949-50.

During the academic year 1950-51, I studied in Paris as a Fulbright Research Scholar. I was a Lecturer in Mathematics at Princeton during the following year. In 1952, I began a seven-year association with Bryn Mawr College, attaining the rank of Associate Professor.

Following a year's study at the London School of Economics as a National Science Foundation Senior Postdoctoral Fellow (1958-59), I returned to Princeton as Associate Professor of Mathematical Economics. I was promoted to the rank of Professor in 1963. Since that time, I have spent leaves of absence at the University of Rome as a National Science Foundation Senior Postdoctoral Fellow (1965-66) and at the London School of Economics as a National Science Foundation Science Faculty Fellow (1971-72).

I have been a consultant to various government organizations and to several corporations, and was senior consultant and member of the Board of Directors for Mathematica Inc. a Princeton-based research firm (not Wolfram) from 1961 to 1983 when it was acquired by Martin-Marietta. In this capacity, I directed a number of projects, including safety and reliability of nuclear weapons for the Atomic Energy Commission, inspection systems and the methodology of utility theory for the Arms Control and Disarmament Agency, and aggregation for traffic assignment models for the Department of Transportation.

A former President (1954-55) of the Society for Industrial and Applied Mathematics, I am a member of the American Mathematical Society, the Mathematical Association of America, and a Fellow of the Econometric Society. I am a former Executive Secretary (1957-1960) of the Division of Mathematics of the National Research Council - National Academy of Sciences. I served for several years as a member. I was elected to the Council of the Association of American University Professors for the period 1959-62.

As a member of the Princeton University Advisory Committee on Policy (1967-71), I wrote the position paper "Students and the University" which led to broad changes in participation by students in governance of the University. During this period, I also served on the Committee on Structure of the University, the Council of Princeton University Community, and was the first Chair of its Committee on Rights and Rules.

As an economist, I have taught undergraduate courses in price theory and managerial economics, and graduate courses in micro-economics, trade theory, and mathematical economics which was cross-listed in the graduate program for the Department of Mathematics where I also taught an undergraduate course in linear and nonlinear programming.

Among my publications, specially noteworthy is my work on nonlinear programming (jointly with A. W. Tucker, 1950), extensive games (1950), the Hungarian Method for the Assignment Problem (1955), an algorithm for Nash equilibria of bimatrix games (1959), extensions of Sperner's Lemma (1960), approximations of fixed points by simplicial subdivisions (1968), and an algorithm for the zeros of polynomials (1974). I also edited the first two volumes of Contributions to the Theory of Games and Linear Inequalities and Related Systems in the series Annals of Mathematics Studies with Dr. Albert W. Tucker of Princeton's Department of Mathematics. As co-director of NATO International Summer Schools with Dr. G. P. Szego, I edited proceedings on Mathematical Systems Theory and Economics (Springer-Verlag) and Differential Games (North-Holland). I also edited the Proceedings of the Princeton Symposium on Mathematical Programming; this was the sixth in a distinguished series of international symposia, held at Princeton in 1967. In 1980, I was awarded the John von Neumann Theory Prize of the Operations Research Society of America (jointly with David Gale and A. W. Tucker). In 1982, I received a Guggenheim Fellowship. In 1992, I was elected as a Fellow of the American Academy of Arts and Sciences, and I received an honorary life membership to the Hungarian Operations Research Society. In 2000, I received a Founders Award in recognition of "fundamental contributions to mathematical programming during its formative years" at the 17th International Symposium of the Mathematical Programming Society. In 2002, I received a Fellows Award from the Institute for Operations Research and Management Sciences (INFORMS).

My recent activities have been centered on game theory. In June 1987, I directed a NATO Advanced Study Institute on "Games with Incomplete Information and Bounded Rationality" held in Capri, Italy. In 1991, in a return to a problem I first studied in 1953, a complete set of facets was found for the asymmetric 6-city traveling salesman problem; this was joint work with Hale Trotter. At the Nobel Awards ceremonies in Stockholm in 1994, I chaired a seminar on the work of John Nash in Game Theory. A transcript was published in Les Prix Nobel 1994 published by the Nobel Foundation. This seminar has been republished by the Journal of Economic Theory and the Duke Mathematical Journal in 1996. A volume of basic papers in game theory that I edited, entitled Classics in Game Theory, was published by the Princeton University Press in 1997. In 2002, I coedited The Essential John Nash with Sylvia Nasar; also published by the Princeton University Press. The Press has also published my "Lectures on Game Theory" in March 2003. The Society for Industrial and Applied Mathematics is preparing a DVD with accompanying transcript and notes for a series of lectures that I recorded at the Audiovisual Centre of London University in the spring of 1972 entitled Foundations of Mathematical Programming.

On November 14, 2000, I was awarded an Honorary Doctoral Degree in Economics by the University of Bergamo, Italy. The Lectio Magistralis, entitled "Al Posto Giusto Nel Momento Giusto," has been translated and is published as "Being in the Right Place at the Right Time" in the 50th Anniversary Issue of the journal Operations Research (50, Jan/Feb 2002, pp.132-4).

In 2004, the scientific journal Naval Research Logistics established an annual "best paper" award. In creating that award, the publishers and editors of the journal sought the paper best representing the journal since its founding in 1954; they selected my paper "The Hungarian Method for the Assignment Problem.” According to the journal's citation, "This pioneering paper set a style for both the content and exposition of many other algorithms in combinatorial optimization and also directly inspired the primal-dual algorithm for more general linear optimization problems."

Professor Kuhn retired in July 1995 becoming Professor of Mathematical Economics Emeritus at Princeton University. Since 2005 he has resided in New York City. In May 2009 Professor Kuhn was elected to the Inaugural Group of Fellows of the Society for Industrial and Applied Mathematics (SIAM) for seminal contributions to game theory and to linear and nonlinear programming, and for leadership of SIAM in its early years.

External Links

57 Years of Close Encounters with George

Presented at the George B. Dantzig Memorial Paper Cluster, INFORMS Annual Meeting, Washington DC, October 14, 2008

Personal tools