Talk:GLPK/Solution information

Draft paragraph on optimality conditions

Note: the following paragraph is provisional and will be transferred to the main document when a consensus is reached.

#1

Source: original contribution by Robbie Morrison

Some readers may not be familiar with the KKT formulation used by GLPK. Textbooks on linear programming often present the optimality conditions in terms of strong duality and complementary slackness. Strong duality is fulfilled when the primal $X$ and dual feasible $Y$ solutions both exist and yield the same objective value. Complementary slackness is fulfilled when, for any variable $x_{i}$ strictly between its lower and upper bounds, the slack in the corresponding dual constraint (equivalently, the variable's reduced cost) is zero. Complementary slackness is a special case of the KKT conditions for differentiable optimization. Moreover, in the case of linear programming, the KKT conditions alone are necessary and sufficient for a given optimum to be global. Hence the optima GLPK finds are always global.

Robbiemorrison (discuss • contribs) 13:07, 7 May 2011 (UTC)

#2

Source: 11 May 2011 posting by Andrew Makhorin, duly sub-edited

In the general case of nonlinear programming (NLP), the Karush-Kuhn-Tucker optimality conditions (KKT) provide the necessary first-order conditions for a solution to be locally optimal (together with some regularity conditions that also have to be satisfied). Linear programming (LP) is a special case of NLP in which both the feasible region and the objective function are convex. In this particular case, the KKT conditions alone are necessary and sufficient for the solution to be globally optimal. The KKT conditions can be applied to the basic and interior-point solutions from any LP problem, but may not be applied to the solutions from mixed-integer linear programming (MIP).

Robbiemorrison (discuss • contribs) 09:13, 11 May 2011 (UTC)

Karush-Kahn-Tucker theory

Source: this May 2011 posting by Andrew Makhorin.

Notes: (Robbie)

• the original material (the gray blocks) would be deleted on transfer, it is provided here to aid checking
• I suggest we make a new page entitled "Theory", move this material there, and then link back to it

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.

Take a primal LP problem in standard form: 

minimize	$z=\mathbf {c} ^{\top }\mathbf {x}$
subject to	${\begin{aligned}A\mathbf {x} &=\mathbf {b} \\\mathbf {x} &\geq \mathbf {0} \end{aligned}}$

where $\mathbf {x}$ is the 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.

The dual LP problem becomes:

maximize	$p=\mathbf {b} ^{\top }\pi \mathbf {0} ^{\top }\lambda$
subject to	${\begin{aligned}A^{\top }\mathbf {\pi } \lambda &=\mathbf {c} \\\mathbf {\lambda } &\geq \mathbf {0} \\\pi &\quad {\text{of any sign}}\end{aligned}}$

where $(\pi \,|\,\lambda )\,\!$ is a vector of dual variables, $\pi \,\!$ is a vector of Lagrange (or simplex) multipliers (shadow prices) for the equality constraint $A\mathbf {x} =\mathbf {b}$ and $\lambda \,\!$ is a vector of Lagrange multipliers (reduced costs) for the inequality constraint $\mathbf {x} \geq \mathbf {0}$.

KKT optimality conditions for LP consists of *all* constraints from both
the primal and dual problems plus the complementary 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 optimality conditions for an LP make use of all the constraints from the primal and dual formulations and include a complimentary slackness condition. The five KKT conditions are.

KTT.PE	$A\mathbf {x} =\mathbf {b}$
KTT.PB	$\mathbf {x} \geq \mathbf {0}$
KTT.DE	$A^{\top }\mathbf {\pi } \lambda =\mathbf {c}$
KTT.DB	$\lambda \geq \mathbf {0}$
KTT.CS	$x_{j}=0\ {\text{or}}\ \lambda _{j}=0\ {\text{for all}}\ j\ {\text{(or both)}}$

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.

The KKT.CS condition can be rewritten as $x_{j}\lambda _{j}=0\,\!$ or $\lambda ^{\top }\mathbf {x} =\mathbf {0}$ meaning vectors $\mathbf {x}$ and $\lambda \,\!$ must 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

The implementation of the KKT conditions within GLPK are a little more complicated because GLPK supports variables with lower $l_{j}\,\!$ and upper $u_{j}\,\!$ bounds, which also implies no bounds. In general:

minimize or maximize	$z=\mathbf {c} ^{\top }\mathbf {x}$
subject to	${\begin{aligned}&(I\;|\;-\!A)\mathbf {x} =\mathbf {0} \\&\mathbf {l} \leq \mathbf {x} \leq \mathbf {u} \end{aligned}}$

where $\mathbf {x}$ (as earlier) is the vector of structural and axillary variables and $I\,\!$ is an identity matrix. Nonetheless the conditions used in GLPK are equivalent to those shown above and have the same meaning.

(Robbie ...)

Finally, be aware that the KKT conditions KKT.PE and KTT.PB can be calculated for an MIP solution and GLPK will do this on request. In this case, these two conditions are described as "integer feasibility conditions" instead.

Robbiemorrison (discuss • contribs) 12:10, 12 May 2011 (UTC)