> Most books on linear programming never refer to the KKT results; rather > they refer to weak and strong duality theorems and complementary > slackenss. > > On my shelf at work are only two books that refer to LP (others back > home, somewhere): > > The Nemhauser and Wolsey book on integer programming starts with linear > programming. On the second page of the linear programming section, > they give the weak duality, strong duality and complementary slackness > theorems, describe how to use them to test for optimality. Nowhere in > the book do they use KKT or anything like that (that I recall, > certainly not in the index), although around page 300 they introduce > Lagrangian relaxation. > > The other is Vanderbei's linear programming book. He introduces weak > and strong duality and complementary slackness as soon as he > introduces the dual program, around page 50. Much later, around page > 285, when he wants to discuss solution techniques to path-following > algorithms (aka interior point algorithms) he states that the primal, > dual and complementary slackness conditions are equivalent to the KKT > conditions. > > The book I used as a student (so long ago), by Gale, never discusses > KKT, which is interesting because Gale worked with Tucker (the "T" in > KKT) to develop the first proof of the strong duality concept. I > would not be surprised to learn that Kuhn and Tucker developed the KT > conditions (and rediscovered what Karush came up with 20 years > earlier) after they discovered strong duality for linear programming > and the use of the Farkas lemma (the separating hyperplane theorem) to > prove it. I haven't read Kuhn's survey paper published in 1976 on the > history of non-linear programming, but Vanderbei's book refers to it > and if someone else has read it I would be interested in finding out > if strong duality came before KT conditions. > > Anyone else care to give an opinion? >
I could refer to the "Encyclopedia of Optimization" by Floudas and Pardalos (Eds.), Springer, 2009. On pp. 1794-1798 of this huge book one can find the article "Kuhn-Tucker Optimality Conditions" by P.M.Pardalos, and also note that terms "KT conditions", "KT point", etc. are used thruout this book in many other articles. However, I don't see an issue to discuss. Andrew Makhorin _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
