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

[Meketon, Marc]

I think this is an excellent addition.

-----Original Message-----
From: address@hidden [mailto:address@hidden On Behalf Of Andrew Makhorin
Sent: Thursday, May 12, 2011 4:08 AM
To: Robbie Morrison
Cc: address@hidden
Subject: Re: [Help-glpk] optimality conditions paragraph (KKT and LP 
formulations)

Hi Robbie,

> I now interrogate the 'LPXKKT' struct, with logic gleaned from the
> code in 'src/glpapi11.c'.  I was puzzled for quite a while as to why
> some GLPSOL reports offered all four KKT conditions and others only
> two.
> The latter were, of course, MIP instances. And on closer inspection,
> the reports are labeled differently:
>
>   Karush-Kuhn-Tucker optimality conditions:
>   Integer feasibility conditions:
>
> I quite agree about keeping the GLPK wikibook strictly interpretive.
> It should not unthinkingly replicate the GLPK manuals, nor it should
> provide theory much beyond the odd pointer for orientation.
>
> Let's wait a week or so and then I should return the editing the KKT
> section, using the above guidelines and the various contributions from
> this list.
>

Probably to make the glpk wikibook paragraph about the KKT conditions complete, 
the text following below could be included there (' means transposition).

Best regards,

Andrew Makhorin


Original (primal) LP problem in the standard format:

   minimize  z = c'x

   s.t.     Ax = b

             x >= 0

where x is a vector of primal variables.

Dual LP problem

   maximize  p = b'pi + 0'lambda

   s.t.     A'pi + lambda = c

            lambda >= 0, pi of any sign

where (pi, lambda) is a vector of dual variables, pi is a vector of Lagrange 
multipliers (simplex multipliers, shadow prices) for equality constraints Ax = 
b, lambda is a vector of Langrange multipliers (reduced
costs) for inequality constraints x >= 0.

KKT optimality conditions for LP consists of *all* constraints from both the 
primal and dual problems plus the complementarity slackness condition, i.e. in 
total we have the following five conditions:

   KKT.PE   Ax = b

   KKT.PB   x >= 0

   KKT.DE   A'pi + lambda = c

   KKT.DB   lambda >= 0

   KKT.CS   x[j] = 0 and/or lambda[j] = 0 for all j

The KKT.CS condition can be rewritten in equivalent form x[j] * lambda[j] = 0 
or simply lambda'x = 0, i.e. vectors x and lambda have to be orthogonal.

In GLPK the KKT conditions used are a bit more complicated in its format (but 
equivalent to the ones shown above having the same meaning), because in GLPK 
variables may have both lower and upper bounds as well as no bounds:

   min/max z = c'x

   s.t.    (I | -A)x = 0

           l <= x <= u

where x is a vector of all auxiliary and structural variables.


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