This blog is talking about how to move to another basic feasible solution and how to judge the basic feasible solution is optimal.

Feasible direction

Def 3.1 Let $\bar{x}$ be an element of a polyhedron $P$ inside $\mathbb{R}^n$. A vector $d \in \mathbb{R}^n$ is said to be a feasible direction at $\bar{x}$ if there exists a positive scalar $\theta$ for which $\bar{x} + \theta \bar{d} \in P$

Basic feasible directions: how to move along edges of the feasible polyhedron?

Let $\bar{x}$ be a basic feasible solution $B(1), …, B(m)$ be the indices of the basic variables

$$ B = \begin{bmatrix} A_{B(1)} & A_{B(2)} & \dots & A_{B(m)} \end{bmatrix} $$

be the corresponding basis matrix.

Recall that $x_i = 0$ for $i \not\in \{B(1), …, B(m)\}$

$$ \bar{x}_B = \begin{bmatrix} x_{B(1)} \\ \vdots \\ x_{B(m)} \end{bmatrix} $$

is given by

$$ \bar{x}_B = B^{-1} \bar{b} $$

We want to move from $\bar{x}$ to $\bar{x} + \theta \bar{d}$ (with $\theta > 0$) in such a way that only one of the nonbasic variables, say $x_j$, increases.

This way, only one of the nonnegativity constraints active at the b.f.s. $\bar{x}$ is relaxed and no longer active at $\bar{x} + \theta \bar{d}$. This ensures that we travel along an edge of the feasible polyhedron.

Thus we choose $j \notin \{B(1), B(2), …, B(m)\}$, and we set

\[\begin{cases} d_j = 1 \\ d_i = 0, & \text{for all } i \notin \{B(1), B(2), ..., B(m)\} \text{ with } i \neq j \end{cases}\]

Since we want to move within the feasible region, we require that the equality constraints are still satisfied as we move, i.e., we require $A(\mathbf{x} + \theta \mathbf{d}) = \mathbf{b}$.

$$ \begin{aligned} &A(\bar{x} + \theta \bar{d}) = \bar{b}, A\bar{x} = \bar{b} \\ & \Rightarrow \theta \cdot A\bar{d} = \bar{0}, \theta > 0 \\ &\Rightarrow A\bar{d} = \bar{0}. \end{aligned} $$

Hence

\[\bar{0} = A\bar{d} = \sum_{i=1}^{n} \bar{A}_i d_i = \bar{A}_j \cdot \textbf{1} + \sum_{i=1}^{m} \bar{A}_{B(i)} d_{B(i)} = \bar{A}_j + B \cdot \bar{d}_B\]

Since the basis matrix $B$ is invertible, we obtain

\[\bar{A}_j + B \bar{d}_B = \bar{0}\] \[B \bar{d}_B = - \bar{A}_j\] \[\bar{d}_B = - B^{-1} \bar{A}_j\]

Basic feasible direction

The vector $\bar{d} = \begin{bmatrix} \bar{d}_B \ \bar{d}_N \end{bmatrix}$ with $\bar{d}_N = \begin{bmatrix} 0 & \cdots & 1 & \cdots & 0 \end{bmatrix}^\top$ (only ${ j^{\text{th}} }$ component as ${ 1 }$) and $\bar{d}_B = -B^{-1} \bar{A}_j$ (basic components) is called $j^{th}$ basic direction at the b.f.s. $\bar{x}$ with basis matrix $B$.

Since we want to move within the feasible region, we must also require that the nonnegativity constraints be satisfied as we move, i.e., we require $\bar{x} + \theta \bar{d} \geq \bar{0}$.

Clearly, $\bar{x}_N + \theta \cdot \bar{d}_N \geq \bar{0}$ is automatically satisfied since $\bar{x}_N = \bar{0}$, $\theta > 0$, and $\bar{d}_N = \begin{bmatrix} 0 & \cdots & 1 & \cdots & 0 \end{bmatrix}^\top$ (only ${ j^{\text{th}} }$ component as ${ 1 }$).

How about $\bar{x}_B + \theta \bar{d}_B$? We need to consider the following two cases

NONDEGENERATE CASE

The b.f.s. $\bar{x}$ is nondegenerate iff $\bar{x}_B > \bar{0}$.

In that case, we can pick the positive number $\theta$ sufficiently small, and guarantee that $\bar{x}_B + \theta \cdot \bar{d}_B \geq \bar{0}$. Hence $\bar{x} + \theta \cdot \bar{d}$ is feasible and $\bar{d}$ is a feasible direction at $\bar{x}$.

DEGENERATE CASE

The b.f.s. $\bar{x}$ is degenerate iff one of its basic components, say $\bar{x}_{B(j)}$, is zero.

In that case, it could happen that ${\bar{x}_{B(j)} + \theta \cdot \bar{d}_{B(j)} < 0}$ for all ${\theta > 0}$ if the component ${\bar{d}_{B(j)}}$ of ${\bar{d}_B = -B^{-1} \bar{A}_j}$ happens to be negative. In such a situation, the direction $\bar{d}$ would not be feasible at $\bar{x}$.

Reduce cost

How does the cost change as we move along an edge?

As we travel away from the corner / b.f.s. $\bar{x}$ along the $j^{th}$ basic feasible direction $\bar{x} + \theta \bar{d}$, the cost changes: $\theta \mapsto c^\top (\bar{x} + \theta \bar{d})$ at the rate $\bar{c}^\top \bar{d} = c_j \cdot 1 + \bar{c}_B^\top \bar{d}_B = (c_j - \bar{c}_B^\top B^{-1} \bar{A}_j)$.

Definition: Let $\bar{x}$ be a b.f.s. with associated basis matrix $B$. The number $\tilde{c}_j = c_j - \bar{c}_B^\top B^{-1} A_j$ is called the reduced cost of the variable $x_j$ at the b.f.s. $\bar{x}$.

The (row) vector $\bar{\tilde{c}}^\top := c^\top - \bar{c}_B^\top B^{-1} A$ is called the vector of reduced costs at the b.f.s. $\bar{x}$.

Claim:

The reduced cost of every basic variable is zero.

Proof:

Let’s consider the basis matrix $B$ and its associated columns from the matrix $A$:

$$ B = \begin{bmatrix} \bar{A}_{B(1)} \bar{A}_{B(2)} \cdots \bar{A}_{B(m)} \end{bmatrix} $$

Here, $e_i$ is the $i^{th}$ column of the identity matrix:

$$ B^{-1} \cdot B = B^{-1} \begin{bmatrix} \bar{A}_{B(1)} \bar{A}_{B(2)} \cdots \bar{A}_{B(m)} \end{bmatrix} = \begin{bmatrix} \bar{e}_1 & \bar{e}_2 & \cdots & \bar{e}_m \end{bmatrix} $$

From the above, we can deduce that:

$$ B^{-1} A_{B(i)} = e_i $$

Thus, for the reduced costs we get:

$$ \tilde{c}_{B(i)} = c_{B(i)} - \bar{c}_B^T B^{-1} A_{B(i)} = c_{B(i)} - \bar{c}_B^T e_i = c_{B(i)} - c_{B(i)} = 0 $$

Hence, the reduced cost of every basic variable is zero. $\square$

Optimal certification

Theorem: Let $\bar{x}$ be a b.f.s. of

$$ \begin{aligned} & \text{minimize} & c^\top \bar{x} \\ & \text{subject to} & A\bar{x} = b \\ & & \bar{x} \geq 0 \\ \end{aligned} $$

with associated basis matrix $B$ and corresponding vector of reduced cost $\bar{c}$.

1. If $\bar{\tilde{c}} \geq 0$, THEN $\bar{x}$ is an optimal solution.
2. If $\bar{x}$ is an optimal and nondegenerate b.f.s., THEN $\bar{\tilde{c}} \geq 0$.

Proof:

(1) We assume $\bar{\tilde{c}} \geq 0$. Pick any feasible solution $\tilde{y}$. We need to show that $c^T \bar{x} \leq c^T \tilde{y}$.

Let $\bar{d} = \bar{y} - \bar{x}$. Since $\bar{x}$ and $\tilde{y}$ are both feasible, we have $A\bar{d} = A(\bar{y} - \bar{x}) = A\bar{y} - A\bar{x} = \bar{b} - \bar{b} = \mathbf{0}$.

Let $N \subset {1, 2, …, n}$ denote the subset of indices corresponding to the nonbasic variables for the b.f.s. $\bar{x}$.

Then $\bar{0} = A\bar{d} = B \bar{d}_B + \sum_{i \in N} \bar{A}_i d_i$.

Since the basis matrix is invertible, we obtain

\[\bar{d}_B = - \sum_{i \in N} B^{-1} \bar{A}_i d_i\]

It follows that

\[\begin{equation} \begin{aligned} c^\top \bar{y} - c^\top \bar{x} &= c^T \bar{d} \\ &= \bar{c}_B^\top \bar{d}_B + \sum_{i \in N} c_i d_i \\ &= - \bar{c}_B^\top B^{-1} \sum_{i \in N} \bar{A}_i d_i + \sum_{i \in N} c_i d_i \\ &= \sum_{i \in N} (c_i - \bar{c}_B^\top B^{-1} \bar{A}_i) d_i \\ & = \sum_{i \in N} \tilde{c}_i d_i \end{aligned} \end{equation}\]

For all $i \in N$, we have

• $\bar{x}_i = 0$ (because the nonbasic components of a b.f.s. are zero) and

• $\tilde{y}_i \geq 0$ (because $\tilde{y}$ satisfies the nonnegativity constraints since $\tilde{y}$ is feasible)

Thus $d_i = \tilde{y}_i - \bar{x}_i \geq 0$.

Since both $\tilde{c}_i \geq 0$ and $d_i \geq 0$ for all $i \in N$, we have

$\bar{c}^\top \bar{y} - \bar{c}^\top \bar{x} = \sum_{i \in N} \tilde{c}_i d_i \geq 0$. :)

(2) Suppose ${\bar{x}}$ is a nondegenerate b.f.s. and that one of the reduced costs at ${\bar{x}}$ is negative, say ${\bar{c}_j < 0}$.

Since the reduced cost of a basic variable is necessarily 0, we know that the variable ${x_j}$ is nonbasic.

Since ${\bar{x}}$ is a nondegenerate b.f.s., the ${j^{th}}$ basic direction at ${\bar{x}}$ is feasible and, since ${\tilde{c}_j < 0}$, it is a feasible direction of cost decrease.

Moving away from ${\bar{x}}$ in that direction, we will get a feasible solution whose cost is less than that of ${\bar{x}}$. Hence ${\bar{x}}$ is not optimal. ${ \square }$

As a consequence of above theorem, we get the following simple criterion for figuring out whether a b.f.s. is optimal or not:

Given a basic solution ${\bar{x}}$.

IF ${\bar{x}}$ is feasible and the reduced costs at ${\bar{x}}$ are all nonnegative, THEN the b.f.s. ${\bar{x}}$ is optimal.

Definition: A basis matrix $B$ is said to be optimal if ${\bar{B}^{\top}b \geq 0}$ and ${\tilde{\bar{c}}^\top = \bar{c}^{\top} - \bar{c}_B^{\top}B^{-1}A \geq \bar{0}^\top}$

• ${\bar{B}^{\top}b \geq 0}$ ensures that the basic solution corresponding to the basis matrix $B$ is a basic feasible solution.

• ${\tilde{\bar{c}}^\top = \bar{c}^{\top} - \bar{c}_B^{\top}B^{-1}A \geq \bar{0}^\top}$ means all reduced cost being negative ensures that the b.f.s. corresponding to the basis matrix $B$ is optimal.

The basic solution corresponding to an optimal basis matrix is necessarily an optimal b.f.s.