Exercise 3.3 (Feasibility conditions)

Proof. Let $x\in P$ be arbitrary, i.e., $\mathrm{Ax}=b$ and $x\ge 0$.

$⟹$

Suppose that $d\in {\Re }^n$ is feasible at $x$, i.e., by Definition 3.1, there exists a $𝜃>0$ such that $x+𝜃d\in P$. Then, we must have $A(x+𝜃d)=b$. Since $Ax=b$, we obtain $Ad=(b-Ax)∕𝜃=0$. This covers the first assertion. Furthermore, $x+𝜃d$ is nonnegative, i.e., $x+𝜃d\ge 0$. At any index $i$ such that $x_i=0$, we have $x_i+𝜃d_i=𝜃d_i\ge 0$. Dividing by the positive $𝜃>0$, we get $d_i\ge 0$, as desired.

$⟸$

Now suppose that we have a direction $d\in {\Re }^n$ such that $\mathrm{Ad}=0$ with $d_i=0$ for every $i$ such that $x_i=0$. We must find $𝜃>0$ such that $x+𝜃d\ge 0$. We make the following observation:

$$i=1,\dots ,n:x_i+𝜃d_i\ge 0⟸\{\begin{array}{cc}{d}_i<0,\hfill & \text{then }𝜃\le -\frac{x_i}{d_i}\hfill \\ \\ d_i\ge 0,\hfill & \text{then no restriction}\hfill \end{array}$$

Inspired by this observation, choose an arbitrary $𝜃$ with the property (cf. page 88, Eq. 3.2):

$$0<𝜃<\min <!--\; FUNCTION\; APPLICATION\; -->\left\{-\frac{x_i}{d_i}|d_i<0\right\}.$$

(1)

(Notice that $d_i\ne 0$ implies $x_i\ne 0$.) We now justify the above argument rigorously. For any $x_i$, $1\le i\le n$, we have the following cases:

• $x_i=0$, then $d_i\ge 0$ by assumption, and we obtain $x_i+𝜃d_i=𝜃d_i\ge 0$.
• $x_i>0$, then we have two more cases. If $d_i\ge 0$, then $x_i+𝜃d_i>0$. If, however, $d_i<0$, then $𝜃\le -x_i∕d_i$ and thus $𝜃d_i\ge -x_i$, as desired.

Thus, by choosing $𝜃$ as in (1), we ensure that $x+𝜃d\ge 0$. Furthermore,

$$A\left(x+𝜃d\right)=\mathrm{Ax}+𝜃\mathrm{Ad}=b+0=b.$$

We conclude that $d$ is a feasible direction at $x$.