Re: [Help-glpk] GLPK wikibook : newish solution information page

[Andrew Makhorin]

> 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