The Simplex Method
Posted on
This note is based on Chapter 13 of Nocedal, J., & Wright, S. (2006). Numerical optimization. Springer Science & Business Media.
Consider
\[\begin{equation} \min\; c^Tx,\qquad \text{subject to }Ax=b,x\ge 0\,,\label{13.1} \end{equation}\]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
\[\cL(x,\lambda,s) = c^Tx-\lambda^T(Ax-b)-s^Tx\]and the KKT condition is
\[\begin{align*} A^T\lambda + s &=c\\ Ax&=b\\ x&\ge 0\\ s&\ge 0\\ x_is_i&=0,\;i=1,\ldots,n\,. \end{align*}\]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$.
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,
\[Ax = Bx_B+Nx_N=b\,,\]since we are dealing with basic feasible points, and know that $B$ is nonsingular and that $x_B\ge 0$, then we have
\[x_B=B^{-1}b,\qquad x_N=0\,.\]Choose $s$ to satisfy the complementarity condition by setting $s_B=0$, then
\[B^T\lambda = c_B,\qquad N^T\lambda+s_N=c_N\,,\]it follows that
\[\lambda = B^{-T}c_B\]and
\[s_N = c_N-N^T\lambda = c_N-(B^{-1}N)^Tc_B\,.\]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
\[Ax^+=Bx_B^++A_qx_q^+=Bx_B=Ax\,,\]thus
\[x_B^+=x_B-B^{-1}A_qx_q^+\,,\]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
\[\begin{align*} c^Tx^+=c_B^Tx_B^++c_qx_q^+&=c_B^Tx_B-c_B^TB^{-1}A_qx_q^++c_qx_q^+\\ &=c_B^Tx_B-\lambda^TA_qx_q^++c_qx_q^+\\ &=c_B^Tx_B-(c_q-s_q)x_q^++c_qx_q^+\\ &=c^Tx+s_qx_q^+\,. \end{align*}\]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.
