------------------------------------------------------------ To: Robbie Morrison <[email protected]>, GLPK help <[email protected]> Subject: RE: [Help-glpk] GLPK wikibook : newish solution information page Message-ID: <04B026E012A010408111AFE9C67000A122FE07AD0F@owgusdfwmbx03> From: "Meketon, Marc" <[email protected]> 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" <[email protected]> Subject: Re: [Help-glpk] GLPK wikibook : newish solution information page Message-ID: <1304621897.2950.12.camel@corvax> From: Andrew Makhorin <[email protected]> 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 > "KuhnTucker 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 "KarushKuhnTucker 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 glpsols report are related to the conditions (i), (ii), (iii), and (iv) of the KarushKuhn Tucker theorem 5.3.1. If the KarushKuhnTucker conditions are satisfied the values in the glpsols KarushKuhnTucker 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) : [email protected] Webmail (preferred) : [email protected] [from Webmail client] _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
