The Simplex Method

Posted on Jul 23, 2019
Tags: Linear Programming

This note is based on Chapter 13 of Nocedal, J., & Wright, S. (2006). Numerical optimization. Springer Science & Business Media.

Consider

where $c$ and $x$ are vectors in $\IR^n$, $b\in\IR_m$, and $A$ is an $m\times n$ matrix.

The Lagrangian function is

and the KKT condition is

Each iterate generated by the simplex method is a basic feasible point of \eqref{13.1}. A vector $x$ is a basic feasible point if it is feasible and if there exists a subset $\cB$ of the index set ${1,2,\ldots,n}$ such that

• $\cB$ contains exactly $m$ indices
• $i\not\in\cB\Rightarrow x_i=0$
• The $m\times m$ matrix $B$ defined by $B=[A_i]_{i\in\cB}$ is nonsingular, where $A_i$ is the $i$-th column of $A$.
All basic feasible points for \eqref{13.1} are vertices of the feasible polytope $\{x\mid Ax=b,x\ge 0\}$, and vice versa.

Let $\cN=\{1,2,\ldots,n\}\backslash\cB$ be the nonbasic index set, and partition the $n$-element vectors $x,s$ and $c$ according to the index sets $\cB$ and $\cN$.

By the KKT condition,

since we are dealing with basic feasible points, and know that $B$ is nonsingular and that $x_B\ge 0$, then we have

Choose $s$ to satisfy the complementarity condition by setting $s_B=0$, then

it follows that

and

The only KKT condition that not enforced explicitly is the nonnegativity conditions $s\ge 0$.

• If $s_N\ge 0$, terminate and declare success
• Choose onr of the indices $q\in\cN$ for which $s_q < 0$ to be the entering index.

The procedure for altering $\cB$ and changing $x$ and $s$ is as follows:

• allow $x_q$ to increase from zero during the next step
• fix all other components of $x_N$ at zero, and figure out the effect of increasing $x_q$ on the current basic vector $x_B$, given that staying feasible w.r.t. the equality constraints $Ax=b$.
• keep increasing $x_q$ until one of the components of $x_B$ ($x_p$, say) is driven to zero, or determining that no such component exists (the unbounded case)
• remove the leaving index $p$ from $\cB$ and replace it with the entering index $q$.

Since both the new iterate $x^+$ and the current iterate $x$ should satisfy $Ax=b$, and since $x_N=0$ and $x_i^+=0$ for $i\in\cN\backslash\{q\}$, we have

thus

which is usually a move along an edge of the feasible polytope that decrease $c^Tx$, and we continue to move along this edge until a new vertex is encountered.

Note that

Since $q$ was chosen to have $s_q < 0$, then the above step produces a decrease in the primal objective function $c^Tx$ whenever $x_q^+>0$.

It is possible that we can increase $x_q^+$ to $\infty$ without ever encountering a new vertex. When this happens, the linear program is unbounded. Published in categories Note