Linear programming: improving a basic feasible solution

 Recall our basic set up. We have a linear program

• Minimize $c\cdot x$ where $x$ and $c$ are $n$-vectors.
• subject to the constraints
• $Ax=b$ ($A$ is an $m\times n$ matrix.
• $x\geq 0$

and we have decided to look for basic feasible solutions, which correspond to partitioning the index set of columns of $A$ into the $B$ and $N$ indices. Somewhat abusing notation, $B$ and $N$ are also the submatrices of $A$ formed by these columns. $x$ is said to be a basic feasible solution if $x_N=0$, and $x_B=B^{-1}b\geq 0$.

In the last post we saw that if $x$ passes the test for optimality $c_N-c_BB^{-1}N\geq 0$, then it is optimal. In this post we consider what happens if our bfs fails the test. Our first step will be to find a direction $d$ along which the objective function decreases. For calculus aficionados, denoting the objective function by $f(x)=c\cdot x$, the directional derivative in the direction of $d$, is just given by $c\cdot d$. Hence we want to find a direction $d$ such that $c\cdot d<0$. (We also need the direction to point into the polytope.)

Theorem: If $x$ is a bfs which fails the test for optimality, let $j$ be an $N$-index  such that $1\leq j\leq n-m$ and $(c_N-c_BB^{-1}N)_j<0$. Let $d=(d_B,d_N)=(-B^{-1}N_{\cdot j},I_{\cdot j})$, where $I$ is the $(n-m)\times(n-m)$ identity matrix. Then $c\cdot d<0$.

Proof:

$$c\cdot d = c_Bd_B+c_Nd_N=-c_BB^{-1}N_{\cdot j}+c_NI_{\cdot j}$$

$$\hspace 4em = (c_N-c_BB^{-1}N)_j<0$$

$\Box$

So we have a direction $d$, possibly several. Let $j^*$ be some choice of index such that $(c_N-c_BB^{-1}N)_j<0$ which gives us this direction. Next we must determine how far to go in the direction $d.$ That is, if we have a bfs $x$, and a direction $d$, how big can we make $t$ so that $x+td$ remains in our feasible polytope. One nice thing is that the equality constraints $Ax=b$ remain true along the entire line if $d$ is of the special form $(-B^{-1}N_{\cdot j},I_{\cdot j})$.

Lemma: Suppose $x=(x_B,x_N)=(B^{-1}b,0)$ is a bfs for $Ax=b$ and $d=(d_B,d_N)=(-B^{-1}N_{\cdot j},I_{\cdot j})$ for some $j$, then for all $t$ $A(x+td)=b$.

Proof:

It suffices to show that $Ad=0$. 

$$Ad=Bd_B+Nd_N=B(-B^{-1}N_{\cdot j})+NI_{\cdot j}=N_{\cdot j}-N_{\cdot j}=0.$$

$\Box$

So we need to find the maximal $t$ so that the nonnegativity constraints $x\geq 0$ are satisfied.

Lemma: Suppose $x\geq 0$ is a solution for $Ax=b$ and $d$ is a direction having at least one negative component, then

$$t^* = \min\{-x_i/d_i\,|\, 1\leq i\leq n\text{ and } d_i<0\}$$ has the property that $x+t^*d\geq 0$. In particular, if $x,d$ are as in the previous lemma, then $x+t^*d$ is feasible.

If $d\geq 0$, the LP is unbounded: the entire ray $x+td, t\geq 0$ lies in the feasible region and $f$ is decreasing along it.

Proof of lemma: 

By the previous lemma, we just need to satisfy the inequality constraints $x\geq 0$. Let us check for each coordinate $x_i$. If $d_i\geq 0$, then $(x+td)_i = x_i+td_i\geq 0$ for all $t>0$. Otherwise suppose $d_i<0$. Then $(x+t^*d)_i = x_i+t^*d_i$, and we know $t^*\leq -x_i/d_i$ by definition, so $t^*d_i\geq -x_i$ and $x_i+t^*d_i\geq x_i-x_i=0$.

$\Box$

In summary, we have chosen a direction along which the objective function decreases that lies in the affine subspace $Ax=b$. Then we have calculated the maximum distance one can travel along this ray and stay in the positive orthant. 

In the next post we will reinterpret this operation combinatorially and show that $x+t^*d$ is also a bfs.