WeiYa's Work Yard

A traveler with endless curiosity, who fell into the ocean of statistics, tries to write down his ideas and notes to save himself.

The Simplex Method

Posted on
Tags: Linear Programming

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$.
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,

\[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.


Published in categories Note