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

[Meketon, Marc]

Bob,

The concept of using weak or strong duality is somewhat semantics, so just for 
the record let me clean it up a bit.

Weak duality says that if we have primal and dual feasible solutions, and their 
objective functions are equal (or, equivalently, complementary slackness is 
met), then the solutions are optimal.

Strong duality says that if we have primal and dual feasible and optimal 
solutions, then the objective values are equal and equivalently complementary 
slackness is met.

The test for optimality uses weak duality - the algorithms (whether they are 
simplex or interior-point) check to see if primal feasibility is met, if dual 
feasibility is met, and if complementary slackness holds (and in all three 
cases, a certain small tolerance is allowed), and if so (using weak duality) 
declare they have reached optimality.

However, the fact that this test will always work (whenever primal and dual 
solutions exist) is only guaranteed by strong duality.  If strong duality did 
not hold, then there could have been a situation in which we had optimal 
solutions but the test failed.

-Marc

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Wednesday, May 11, 2011 11:21 AM
To: address@hidden
Subject: [Help-glpk] [Fwd: RE: optimality conditions paragraph (KKT and LP 
formulations)]

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




_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk

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.