[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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-----
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.
- [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Robbie Morrison, 2011/05/11
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/11
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Robbie Morrison, 2011/05/11
- Message not available
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/11
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Robbie Morrison, 2011/05/11
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations),
Meketon, Marc <=
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Robbie Morrison, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Meketon, Marc, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Robbie Morrison, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Meketon, Marc, 2011/05/12
- Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations), Andrew Makhorin, 2011/05/12