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

[Andrew Makhorin]

Hi Robbie,

> In reference to the following [help-glpk] thread and
> GLPK wikibook page:
> 
>   GLPK wikibook : newish solution information page
>   http://lists.gnu.org/archive/html/help-glpk/2011-05/msg00022.html
>   http://en.wikibooks.org/wiki/GLPK/Solution_information
> 
> I drafted a paragraph on optimality conditions which
> is sitting on the associated wikibook discussion page:
> 
>   http://en.wikibooks.org/wiki/Talk:GLPK/Solution_information
> 
> 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)
        problems.
        
Best regards,

Andrew Makhorin