Revised simplex method

In mathematical optimization, the revised simplex method is a variant of George Dantzig's simplex method for linear programming.

The revised simplex method is mathematically equivalent to the standard simplex method but differs in implementation. Instead of maintaining a tableau which explicitly represents the constraints adjusted to a set of basic variables, it maintains a representation of a basis of the matrix representing the constraints. The matrix-oriented approach allows for greater computational efficiency by enabling sparse matrix operations.[1]

Problem formulation

For the rest of the discussion, it is assumed that a linear programming problem has been converted into the following standard form:

{\begin{array}{rl}{\text{minimize}}&{\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}}\\{\text{subject to}}&{\boldsymbol {Ax}}={\boldsymbol {b}},{\boldsymbol {x}}\geq {\boldsymbol {0}}\end{array}}

where $A \in R m \times n$ . Without loss of generality, it is assumed that the constraint matrix $A$ has full row rank and that the problem is feasible, i.e., there is at least one $x \geq 0$ such that $Ax = b$ . If $A$ is rank-deficient, either there are redundant constraints, or the problem is infeasible. Both situations can be handled by a presolve step.

Algorithmic description

Optimality conditions

For linear programming, the Karush–Kuhn–Tucker conditions are both necessary and sufficient for optimality. The KKT conditions of a linear programming problem in the standard form is

{\begin{aligned}{\boldsymbol {Ax}}&={\boldsymbol {b}},\\{\boldsymbol {A}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s}}&={\boldsymbol {c}},\\{\boldsymbol {x}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}&\geq {\boldsymbol {0}},\\{\boldsymbol {s}}^{\mathrm {T} }{\boldsymbol {x}}&=0\end{aligned}}

where $λ$ and $s$ are the Lagrange multipliers associated with the constraints $Ax = b$ and $x \geq 0$ , respectively.[2] The last condition, which is equivalent to $s i x i = 0$ for all $1 < i < n$ , is called the complementary slackness condition.

By what is sometimes known as the fundamental theorem of linear programming, a vertex $x$ of the feasible polytope can be identified by being a basis $B$ of $A$ chosen from the latter's columns.[lower-alpha 1] Since $A$ has full rank, $B$ is nonsingular. Without loss of generality, assume that $A = [B N]$ . Then $x$ is given by

{\boldsymbol {x}}={\begin{bmatrix}{\boldsymbol {x_{B}}}\\{\boldsymbol {x_{N}}}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {B}}^{-1}{\boldsymbol {b}}\\{\boldsymbol {0}}\end{bmatrix}}

where $x B \geq 0$ . Partition $c$ and $s$ accordingly into

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}{\boldsymbol {c_{B}}}\\{\boldsymbol {c_{N}}}\end{bmatrix}},\\{\boldsymbol {s}}&={\begin{bmatrix}{\boldsymbol {s_{B}}}\\{\boldsymbol {s_{N}}}\end{bmatrix}}.\end{aligned}}

To satisfy the complementary slackness condition, let $s B = 0$ . It follows that

{\begin{aligned}{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {\lambda }}&={\boldsymbol {c_{B}}},\\{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}+{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}},\end{aligned}}

which implies that

{\begin{aligned}{\boldsymbol {\lambda }}&=({\boldsymbol {B}}^{\mathrm {T} })^{-1}{\boldsymbol {c_{B}}},\\{\boldsymbol {s_{N}}}&={\boldsymbol {c_{N}}}-{\boldsymbol {N}}^{\mathrm {T} }{\boldsymbol {\lambda }}.\end{aligned}}

If $s N \geq 0$ at this point, the KKT conditions are satisfied, and thus $x$ is optimal.

Pivot operation

If the KKT conditions are violated, a pivot operation consisting of introducing a column of $N$ into the basis at the expense of an existing column in $B$ is performed. In the absence of degeneracy, a pivot operation always results in a strict decrease in $c T x$ . Therefore, if the problem is bounded, the revised simplex method must terminate at an optimal vertex after repeated pivot operations because there are only a finite number of vertices.[4]

Select an index $m < q \leq n$ such that $s q < 0$ as the entering index. The corresponding column of $A$ , $A q$ , will be moved into the basis, and $x q$ will be allowed to increase from zero. It can be shown that

{\frac {\partial ({\boldsymbol {c}}^{\mathrm {T} }{\boldsymbol {x}})}{\partial x_{q}}}=s_{q},

i.e., every unit increase in $x q$ results in a decrease by $- s q$ in $c T x$ .[5] Since

{\boldsymbol {Bx_{B}}}+{\boldsymbol {A}}_{q}x_{q}={\boldsymbol {b}},

$x B$ must be correspondingly decreased by $Δ x B = B -1 A q x q$ subject to $x B - Δ x B \geq 0$ . Let $d = B -1 A q$ . If $d \leq 0$ , no matter how much $x q$ is increased, $x B - Δ x B$ will stay nonnegative. Hence, $c T x$ can be arbitrarily decreased, and thus the problem is unbounded. Otherwise, select an index $p = argmin 1\leq i \leq m {x i / d i | d i > 0}$ as the leaving index. This choice effectively increases $x q$ from zero until $x p$ is reduced to zero while maintaining feasibility. The pivot operation concludes with replacing $A p$ with $A q$ in the basis.

Numerical example

Consider a linear program where

{\begin{aligned}{\boldsymbol {c}}&={\begin{bmatrix}-2&-3&-4&0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {A}}&={\begin{bmatrix}3&2&1&1&0\\2&5&3&0&1\end{bmatrix}},\\{\boldsymbol {b}}&={\begin{bmatrix}10\\15\end{bmatrix}}.\end{aligned}}

Let

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{4}&{\boldsymbol {A}}_{5}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{3}\end{bmatrix}}\end{aligned}}

initially, which corresponds to a feasible vertex $x = [0 0010 15] T$ . At this moment,

{\begin{aligned}{\boldsymbol {\lambda }}&={\begin{bmatrix}0&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}-2&-3&-4\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

Choose $q = 3$ as the entering index. Then $d = [1 3] T$ , which means a unit increase in $x 3$ results in $x 4$ and $x 5$ being decreased by $1$ and $3$ , respectively. Therefore, $x 3$ is increased to $5$ , at which point $x 5$ is reduced to zero, and $p = 5$ becomes the leaving index.

After the pivot operation,

{\begin{aligned}{\boldsymbol {B}}&={\begin{bmatrix}{\boldsymbol {A}}_{3}&{\boldsymbol {A}}_{4}\end{bmatrix}},\\{\boldsymbol {N}}&={\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {A}}_{2}&{\boldsymbol {A}}_{5}\end{bmatrix}}.\end{aligned}}

Correspondingly,

{\begin{aligned}{\boldsymbol {x}}&={\begin{bmatrix}0&0&5&5&0\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {\lambda }}&={\begin{bmatrix}0&-4/3\end{bmatrix}}^{\mathrm {T} },\\{\boldsymbol {s_{N}}}&={\begin{bmatrix}2/3&11/3&4/3\end{bmatrix}}^{\mathrm {T} }.\end{aligned}}

A positive $s N$ indicates that $x$ is now optimal.

Practical issues

Degeneracy

Because the revised simplex method is mathematically equivalent to the simplex method, it also suffers from degeneracy, where a pivot operation does not result in a decrease in $c T x$ , and a chain of pivot operations causes the basis to cycle. A perturbation or lexicographic strategy can be used to prevent cycling and guarantee termination.[6]

Basis representation

Two types of linear systems involving $B$ are present in the revised simplex method:

{\begin{aligned}{\boldsymbol {Bz}}&={\boldsymbol {y}},\\{\boldsymbol {B}}^{\mathrm {T} }{\boldsymbol {z}}&={\boldsymbol {y}}.\end{aligned}}

Instead of refactorizing $B$ , usually an LU factorization is directly updated after each pivot operation, for which purpose there exist several strategies such as the Forrest−Tomlin and Bartels−Golub methods. However, the amount of data representing the updates as well as numerical errors builds up over time and makes periodic refactorization necessary.[1][7]

Notes and references

Notes

The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.[3]

References

Morgan 1997, §2.
Nocedal & Wright 2006, p. 358, Eq. 13.4.
Nocedal & Wright 2006, p. 363, Theorem 13.2.
Nocedal & Wright 2006, p. 370, Theorem 13.4.
Nocedal & Wright 2006, p. 369, Eq. 13.24.
Nocedal & Wright 2006, p. 381, §13.5.
Nocedal & Wright 2006, p. 372, §13.4.

Bibliography

Morgan, S. S. (1997). A Comparison of Simplex Method Algorithms (MSc thesis). University of Florida. Archived from the original on 7 August 2011.CS1 maint: ref=harv (link)
Nocedal, J.; Wright, S. J. (2006). Mikosch, T. V.; Resnick, S. I.; Robinson, S. M. (eds.). Numerical Optimization. Springer Series in Operations Research and Financial Engineering (2nd ed.). New York, NY, USA: Springer. ISBN 978-0-387-30303-1.CS1 maint: ref=harv (link)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[4] The same theorem also states that the feasible polytope has at least one vertex and that there is at least one vertex which is optimal.[3]

[FOOTNOTEMorgan1997§2-1] Morgan 1997, §2.

[FOOTNOTENocedalWright2006358Eq.&nbsp;13.4-2] Nocedal & Wright 2006, p. 358, Eq. 13.4.

[FOOTNOTENocedalWright2006363Theorem&nbsp;13.2-3] Nocedal & Wright 2006, p. 363, Theorem 13.2.

[FOOTNOTENocedalWright2006370Theorem&nbsp;13.4-5] Nocedal & Wright 2006, p. 370, Theorem 13.4.

[FOOTNOTENocedalWright2006369Eq.&nbsp;13.24-6] Nocedal & Wright 2006, p. 369, Eq. 13.24.

[FOOTNOTENocedalWright2006381§13.5-7] Nocedal & Wright 2006, p. 381, §13.5.

[FOOTNOTENocedalWright2006372§13.4-8] Nocedal & Wright 2006, p. 372, §13.4.

Complementarity problems and algorithms
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear(NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke