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

[Andrew Makhorin]

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.