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

[Meketon, Marc]

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?



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

------------------------------------------------------------
To:          Robbie Morrison <address@hidden>,
             GLPK help <address@hidden>
Subject:     RE: [Help-glpk] GLPK wikibook : newish solution information page
Message-ID: <address@hidden>
From:       "Meketon, Marc" <address@hidden>
Date:        Thu, 5 May 2011 11:45:39 -0500
------------------------------------------------------------

> In most linear programming textbooks, the optimality conditions are
> refered to differently.  They either use "weak duality" or
> "complementary slackness" when refering to the optimality conditions:
>
> (1) weak duality is when there is a primal feasible
>     solution, a dual feasible solution, and the primal
>     objective value equals to the dual objective value
>
> (2) complementary slackness is where there is a primal
>     feasible solution (x), a dual feasible solution
>     (y), and whenever x_i is strictly between it's
>     lower and upper bounds, the corresponding reduced
>     cost as calculated with y is zero.
>
> Both these conditions are equivalent to the KKT, and in the linear
> programming case are fairly trivial to prove.  But the textbooks don't
> usually call them KKT so I believe the wiki page entry should refer it
> as "Tests for Optimality" and then discuss the more precise
> calculations.
>
> -Marc

------------------------------------------------------------
To:         "Meketon, Marc" <address@hidden>
Subject:     Re: [Help-glpk] GLPK wikibook : newish solution information page
Message-ID: <address@hidden>
From:        Andrew Makhorin <address@hidden>
Date:        Thu, 05 May 2011 22:58:17 +0400
------------------------------------------------------------

>> Both these conditions are equivalent to the KKT, and in the linear
>> programming case are fairly trivial to prove.  But the textbooks
>> don't usually call them KKT
>
> Probably it depends on particular textbooks. The term "Kuhn-Tucker
> optimality conditions" is commonly used in most literature on
> mathematical programming; see:
>
> http://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_condit
> ions
>
> AFAIK, the term "Karush-Kuhn-Tucker conditions" is used only in case
> of linear programs.
>
>> so I believe the wiki page entry should refer it as "Tests for
>> Optimality" and then discuss the more precise calculations.

Hello all

I should say I have no special knowledge regarding optimality conditions, 
rather my academic focus is on modeling and programming.

The material on the new GLPK webpage on solution information was a summary of 
the relevant parts of the GLPK API manual, as best as I could make out.  I used 
no other source, except wikipedia (what else!) for the occasional background 
sentence.

I wrote the wiki page primarily because I have been struggling with poorly 
structured problems and needed to better understand scaling, sensitivity, and 
checks on precision.  And in the hope that this information would be generally 
useful.

During that process, I did look briefly at:

  Sottinen, Tommi.  2009.  Operations research with GNU
    Linear Programming Kit.  ORMS1020 course notes,
    Department of Mathematics and Statistics,
    University of Vaasa, Finland August 27.

    http://lipas.uwasa.fi/~tsottine/lecture_notes/or.pdf

Chapter 5 covers LP theory and on page 65 (literal) Sottinen observes:

 "5.3.2 Remark. The KKT.PE, KKT.PB, KKT.DE, and KKT.DB
  in the glpsol's report are related to the conditions
  (i), (ii), (iii), and (iv) of the Karush-Kuhn- Tucker
  theorem 5.3.1.  If the Karush-Kuhn-Tucker conditions
  are satisfied the values in the glpsol's
  Karush-Kuhn-Tucker section should all be zero."

Now that quote would lend credence to the view that the GLPK usage is 
acceptable, but not necessary universal.
Maybe this is a trans-Atlantic thing?

HTH, best wishes, Robbie

---
Robbie Morrison
PhD student -- policy-oriented energy system simulation Technical University of 
Berlin (TU-Berlin), Germany University email (redirected) : address@hidden
Webmail (preferred)           : address@hidden
[from Webmail client]




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.