help-glpk
[Top][All Lists]

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

 From: Meketon, Marc Subject: Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations) Date: Thu, 12 May 2011 07:08:22 -0500

```I think this is an excellent addition.

-----Original Message-----
Sent: Thursday, May 12, 2011 4:08 AM
To: Robbie Morrison
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
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.