[Help-glpk] [Fwd: RE: optimality conditions paragraph (KKT and LP formulations)]

[Andrew Makhorin]

-------- Forwarded Message --------
From: Robert Fourer <address@hidden>
Reply-To: address@hidden
To: 'GLPK help' <address@hidden>
Cc: 'Andrew Makhorin' <address@hidden>, 'Robbie Morrison'
<address@hidden>
Subject: RE: [Help-glpk] optimality conditions paragraph (KKT and LP
formulations)
Date: Wed, 11 May 2011 09:09:29 -0500

I have been watching this thread and have grown concerned that some serious
errors are creeping in.  So as a start I have made several corrections that
I hope you will not mind.  In particular I would note that: (1) the
optimality condition for LP is strong duality, not weak duality; (2)
complementary slackness is the special case of the KKT conditions when
applied to linear programming, but strong duality is a different condition
that is specific to LP; (3) neither of these optimality conditions is
applicable to mixed-integer programming.

Bob Fourer
address@hidden


> -----Original Message-----
> From: address@hidden [mailto:help-
> address@hidden On Behalf Of Robbie
> Morrison
> Sent: Wednesday, May 11, 2011 4:24 AM
> To: Andrew Makhorin
> Cc: Robbie Morrison; GLPK help
> Subject: Re: [Help-glpk] optimality conditions paragraph (KKT and LP
> formulations)
> 
> 
> Hello Andrew
> 
> I sub-edited your KKT suggestion and is now here:
> 
>   http://en.wikibooks.org/wiki/Talk:GLPK/Solution_information#.232
> 
> Please feel free to revise it, best wishes, Robbie
> 
> ------------------------------------------------------------
> To:          Robbie Morrison <address@hidden>
> Subject:     Re: optimality conditions paragraph (KKT and LP
> formulations)
> Message-ID: <address@hidden>
> From:        Andrew Makhorin <address@hidden>
> Date:        Wed, 11 May 2011 11:37:42 +0400
> ------------------------------------------------------------
> 
> > Hi Robbie,
> >
> >> In reference to the following [help-glpk] thread and
> >> GLPK wikibook page:
> >>
> >>   GLPK wikibook : newish solution information page
> >>   http://lists.gnu.org/archive/html/help-glpk/2011-05/msg00022.html
> >>   http://en.wikibooks.org/wiki/GLPK/Solution_information
> >>
> >> I drafted a paragraph on optimality conditions which
> >> is sitting on the associated wikibook discussion page:
> >>
> >>   http://en.wikibooks.org/wiki/Talk:GLPK/Solution_information
> >>
> >> Please add comments and/or make changes there.  I will
> >> transfer this text over to the main page in a week or so.
> >>
> >
> > I attempted to rewrite the very first paragraph. But I think that a
> > reference to appropriate textbook would be better.
> >
> >     In general case of non-linear programming (NLP) problem the
> >     Karush-Kuhn-Tucker optimality conditions (KKT) are necessary
> >     conditions of the first order for a solution to be (locally)
> >     optimal (together with some regularity conditions that also have
> >     to be satisfied). Linear programming (LP) problem is a
> >     particular case of NLP, where the feasible region and the
> >     objective function are convex, and in this particular case the
> >     KKT conditions are necessary and sufficient conditions for a
> >     solution to be globally optimal. The KKT conditions can be
> >     applied to basic as well as interior-point solutions of any LP
> >     problem. Note, however, that the KKT conditions cannot be
> >     applied to solutions of mixed-integer linear programming (MIP)
> >     problems.
> >
> > Best regards,
> >
> > Andrew Makhorin
> 
> ---
> 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]
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk