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

[Andrew Makhorin]

> Many books call the min c'x, s.t. Ax=b, x>=0 form the "canonical"
>  linear programming program.  The min c'x s.t. Ax >= b, x>=0 is often
>  called the "standard" form, because it has more symmetry with the dual
>  (which is max b'y s.t. A'y<=c, y>=0).  But I've never heard it call
>  the "augmented" form until I googled it and found it in the wikipedia.

Neither have I.

> 
> Googling "Canonical linear programming problem" brings up a number of
>  web-sites that agree with the min c'x, s.t. Ax=b, x>=0 form such as
>  
> http://web.williams.edu/go/math/sjmiller/public_html/399/handouts/LinearProgramming.pdf
> http://cis.poly.edu/POG/canon.pdf And some of the textbooks I have at
>  home also use "canonical" in that way.
> 
> However, some websites use the min c'x Ax >= b, x >=0 to be the
>  canonical form http://www.math.ucla.edu/~rfb/164.1.07s/midsol.pdf
> 
> And some websites use max c'x s.t. Ax <= b, x >= 0 to be the canonical
>  form http://www.cs.uiuc.edu/class/fa05/cs473g/lectures/17-lp.pdf
>  http://en.wikipedia.org/wiki/Linear_programming#Standard_form
>  (actually, this wikipedia article is misleading in that it calls this
>  form the "canonical form" at the beginning of the article, and the
>  "standard" form a few paragraphs below, where the only difference is
>  that the standard form has b>=0;)
> 
> The wikipedia article is where you probably picked up the "augmented"
>  which, while in equality form, is really referring to augmenting the
>  Ax<=b formulation with slack variables.  And it seems (I could be
>  wrong about this) that only the wikipedia article uses that word.
> 
> So, please change "augmented" to either "canonical" (which is my
>  preference) or "standard" (which is Andrew's preference).
> 

The terminology is not stable. The format

   minimize c'x
   s.t.     Ax = 0
            x >= 0

is often called "standard" (e.g. in Dantzig's books, in Murtagh's book,
in MPS and OSL documentation), because it is suitable for the "standard"
simplex method, while other formats needs introducing slacks or
performing some other transformations before the simplex can be applied.

LP in canonical format has the following statement:

   min/max c'x
   s.t. Ax >= 0

(note that in this format it is assumed that x >= 0 are included in 
Ax >= 0, i.e. A alwys includes identity submatrix). However, in the
literature there exist many variations of that that is called "canonical
format". 

I also would like to mention the generalized format, which, in
particular, is used in glpk frontend:

   min/max c'x + c0
   s.t.    L <= Ax <= U
           l <=  x <= u

(However, to transform general constraints L <= Ax <= U to equality
constraints in glpk there are used auxiliary variables, which, to my
opinion, are much more natural and convenient than slack / surplus /
artificial variables used in most LP packages.)


Andrew Makhorin