[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: Andrew Makhorin
Subject: Re: [Help-glpk] optimality conditions paragraph (KKT and LP formulations)
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
> I drafted a paragraph on optimality conditions which
> is sitting on the associated wikibook discussion page:
> 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)
Best regards,

Andrew Makhorin

reply via email to

[Prev in Thread] Current Thread [Next in Thread]