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

[Robbie Morrison]

------------------------------------------------------------
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_conditions
>
> 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]