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

[Meketon, Marc]

The issue is that many (I would argue most) users of linear programming know 
"weak duality", "strong duality" and "complementary slackness".  They do not 
know "KKT" conditions.

The wiki article should use terminology that everyone knows, at least it should 
use both sets of terminology.

-----Original Message-----
From: Andrew Makhorin [mailto:address@hidden
Sent: Friday, May 06, 2011 8:59 AM
To: Meketon, Marc
Cc: Robbie Morrison; GLPK help
Subject: RE: [Help-glpk] GLPK wikibook : newish solution information page

> 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




This e-mail and any attachments may be confidential or legally privileged. If 
you received this message in error or are not the intended recipient, you 
should destroy the e-mail message and any attachments or copies, and you are 
prohibited from retaining, distributing, disclosing or using any information 
contained herein.  Please inform us of the erroneous delivery by return e-mail. 
Thank you for your cooperation.