[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: |
Meketon, Marc |
Subject: |
Re: [Help-glpk] GLPK wikibook : newish solution information page |
Date: |
Fri, 6 May 2011 08:02:21 -0500 |
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.