I always wondered “Why would someone try to construct a dual problem?” When I was doing research for my past blog post “Forgotten Scientists“, I accidentally found my answer. Kuhn says that duality should have these two elements:
(a) a pair of optimization problems, one a maximum problem with objective function f
and the other a minimum problem with objective function h, based on the same data;
(b) for feasible solutions to the pair of problems, always h ≥ f;
(c) necessary and suﬃcient conditions for optimality are h = f.
Here is a problem posed by Fermat early in the seventeenth century:
“Given three points in the plane, ﬁnd a fourth point such that the sum of its distances to the three given points is a minimum.”
Here is the solution:
Here is another problem from 1755, published in The Ladies Diary (Woman’s Almanack). Mr. Tho. Moss (p. 47):
“In the three Sides of an equiangular Field stand three Trees, at the Distances of 10, 12, and 16 Chains from one another: To ﬁnd theContent of the Field, it being the greatest the Data will admit of?”
Another problem published “In the Annales de Math´ematiques Pures et Appliqu´ees”, edited by J. D. Gergonne, vol. I (1810-11) p. 384
“Given any triangle, circumscribe the largest possible equilateral triangle about it.”
In the solutions proposed by Rochat, Vecten, Fauguier, and Pilatte in vol. II (1811-12), pp. 88-93, the observation is made:
“Thus the largest equilateral triangle circumscribing a 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 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]”.
Kuhn concludes the section with this:
The credit for recognizing this duality, which has all of the elements listed above, appears to be due to Vecten, professor of math´ematiques speciales at the Lycee de Nismes. Until further evidence is discovered, this must stand as the ﬁrst instance of duality in nonlinear programming!
I could not find anything about Vecten other than his articles in Annales de Gergonne, mathematical journal published by Joseph Diaz Gergonne.
Soltan et al. in “Geometric Methods and Optimization Problems” write that it is correct to call this result Vecten-Fasbender duality, because E. Fasbender indepenently proved the same result in 1846.
Fasbender showed that the perpendiculars to the three lines connecting the Fermat-Torricelli point with the three given points are the elongated sides of the maximal equilateral triangle circumsribing these three points, and the altitude of this triangle equals to the minimal sum of distances from some point to the three given points. (Emphasis from original text)
Here is the figure from same book (page 333):
It was interesting to learn that a geometrical problem was crucial in the formation of duality concept.
Photo by Kristof Abrath
First Instance of Duality in Nonlinear Programming « OR Complete http://t.co/ZTQKBfwg #math #orms Interesting bit of historical research.
Nice post Ahmet, I wonder other usage of duality in various sectors/problems. Also, who used duality for optimization problems in the first place?