How to understand the reduced cost in simplex method?

Question

I’m reading a note on the simplex method. The author mentions a quantity called “reduced cost”, yet no interpretation of it is provided.

Here’s the setup: $c \in \mathbb{R}^n$ is the cost vector, $A \in \mathbb{R}^{m \times n}$ is the constraint matrix in our system of $m$ equations in $n$ variables, $I \in [n]$ the index set of non-basic variables, and $I^C$ its complement. We start at a vertex $v$ of the associated polyhedron and try to move along an “interesting” direction $d$ (defined below). The reduced cost is defined as:

$$c - ((c_{I^C})^T (A_{I^C})^{-1}A))^T$$

where $c_{I^C}$ and $A_{I^C}$ are $c$ and $A$ restricted to the columns with indices in the subscripts, respectively.

I have two questions concerning this notion.

1. What does this vector tell us?
2. A bit further down, in showing that the simplex method is correct, the author argues in the following way. Let $v$ be a vertex outputted by the simplex method. Then for any $I \subseteq [n]$ “related to $v$” (defined below), and for any $i^* \in I$:
     $\bullet$ either $(c - ((c_{I^C})^T (A_{I^C})^{-1}A))^T)_{i^*} \leq 0$, or
     $\bullet$ there exists index $j$ such that $(v_{I^C})_j = 0$ and $((-A_{I^C})^{-1}A_{i^*})_j < 0$, and so $t = 0$.
   The comment is that the first case corresponds to the situation where moving along the direction $d$ makes the objective function worse, and the second case the situation where doing so makes the solution infeasible.
   I hope to understand the former case by reading answers to question $1$ above. As for the latter, I’m confused as to why this case can even exist. From what I understand, moving along a direction $d$ from $v$ is actually the same thing as moving along a $1$-face of the associated polyhedron. Since we start moving from a vertex with $(v_{I^C})_j = 0$, $v$ should already be a point of the polyhedron with the smallest $j$-value. So how can a direction $d$ that leads to another vertex with even smaller (in fact, negative) $j$-value exist?

I should note that the notations that I’m reading are rather unconventional. The author actually doesn’t use the words “non-basic variables”, but specifies $I$ (and $d$) as follows:

Given a vertex $v$ of the polyhedral set $Ax=b, x \geq 0$, and a subset $J$ of size $n - m$ of $[n]$, such that $v$ is the unique solution of the system of equations $Ax = b, x_j = 0$ for $j \in J$, we find:
  $\bullet$ a subset $I$ of $[n]$ of size $n - m$,
  $\bullet$ an index $i^* \in I$,
  $\bullet$ and a direction $d$,
such that:
  (i) $v$ is the unique solution of $Ax=b, x_{i}=0$ for $i \in I$
  (ii) $A d=0, d_{i}=0$ for $i \in I \setminus \{i^*\}, d_{i^*} > 0$
  (iii) $c^Td>0$
  (iv) the solution $v+t d$ is a feasible solution for some $t>0$.

Answer 1

The fundamental idea is that when $A\mathbf x = \mathbf b$ holds, we can express the objective function $\mathbf c^{\mathsf T} \mathbf x$ in several equivalent ways. (For example, if $x_1 + x_2 = 1$ holds, we can express $2x_1 + x_2$ as $x_1 + (x_1 + x_2) = x_1 + 1$.)

In particular, if we're at a solution where only the basic variables indexed by $B \subseteq [n]$ are nonzero, and the nonbasic variables indexed by $N = [n] - B$ are all zero, it makes sense to express the objective function in terms of the nonbasic variables only. That will let us see which nonbasic variables are good to bring into the basis. To do this, solve $A\mathbf x = \mathbf b$ for $\mathbf x_B$ in terms of $\mathbf x_N$: $$ A \mathbf x = \mathbf b \implies A_B \mathbf x_B + A_N \mathbf x_N = \mathbf b \implies \mathbf x_B = A_B^{-1}(\mathbf b - A_N \mathbf x_N). $$ Then substitute this into the objective function $$ \mathbf c^{\mathsf T}\mathbf x = \mathbf c_B^{\mathsf T} \mathbf x_B + \mathbf c_N^{\mathsf T} \mathbf x_N = \mathbf c_B^{\mathsf T}A_B^{-1}(\mathbf b - A_N \mathbf x_N) + \mathbf c_N^{\mathsf T} \mathbf x_N. $$ This has a constant component $\mathbf c_B^{\mathsf T}A_B^{-1}\mathbf b$ (which is the value of the objective function at the current basic solution) and a variable component $(\mathbf c_N^{\mathsf T} - \mathbf c_B^{\mathsf T}A_B^{-1}A_N) \mathbf x_N$. We might as well extend the variable component to $(\mathbf c^{\mathsf T} - \mathbf c_B^{\mathsf T}A_B^{-1}A) \mathbf x$, which includes all variables (the basic variables are included with coefficient $0$).

The coefficient vector of $\mathbf x$ in the variable component is exactly the reduced cost. It is the cost vector, re-expressed in terms of the nonbasic variables only.

---

The vector $\mathbf v$ "related to $N$" is the basic solution with basic variables $B$: it has $\mathbf v_B = A_B^{-1} \mathbf b$ and $\mathbf v_N = \mathbf 0$.

We've expressed the cost function already as $\mathbf c_B^{\mathsf T}A_B^{-1}\mathbf b + (\mathbf c^{\mathsf T} - \mathbf c_B^{\mathsf T}A_B^{-1}A) \mathbf x$. Let $\mathbf r^{\mathsf T} = \mathbf c^{\mathsf T} - \mathbf c_B^{\mathsf T}A_B^{-1}A$ be the reduced cost, noting that $\mathbf r_B = \mathbf 0$. We spot that $\mathbf c_B^{\mathsf T}A_B^{-1}\mathbf b = \mathbf c_B^{\mathsf T} \mathbf v_B = \mathbf c^{\mathsf T} \mathbf v$, the objective value at $\mathbf v$.

So we can write the objective function at any point $\mathbf x$ as $$\mathbf c^{\mathsf T} \mathbf x = \mathbf c^{\mathsf T} \mathbf v + \mathbf r^{\mathsf T} \mathbf x.$$ In particular:

• Suppose $\mathbf r \le \mathbf 0$. Then because $\mathbf x \ge \mathbf 0$ for every feasible $\mathbf x$, we have $\mathbf r^{\mathsf T} \mathbf x \le 0$, so $\mathbf c^{\mathsf T} \mathbf x \le \mathbf c^{\mathsf T} \mathbf v$. In other words, $\mathbf v$ is optimal.
• Suppose $r_j > 0$ for some $j \in N$. If we can pivot to a solution $\mathbf x$ where $x_j > 0$, but still $x_k = 0$ for all $k \in N - \{j\}$, then its objective value will be $\mathbf c^{\mathsf T} \mathbf v + \mathbf r^{\mathsf T} \mathbf x = \mathbf c^{\mathsf T} \mathbf v + r_j x_j > \mathbf c^{\mathsf T} \mathbf v$. In other words, the objective value will increase.