[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Help-glpk] GLPK wikibook : newish solution information page
From: |
Andrew Makhorin |
Subject: |
Re: [Help-glpk] GLPK wikibook : newish solution information page |
Date: |
Fri, 06 May 2011 16:59:25 +0400 |
> 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