Exercise 3.22 (Standard form optimization problem with one constraint)

Feasibility test. We implement the following test which breaks down the parameter configuration into three mutually disjoint cases.

• $b=0$.
  The problem is always feasible as $x=0$ belongs the to the set of feasible solutions.
• $b>0$.
  The problem is feasible if and only if there is a $1\le j\le n$ such that $a_j>0$. The only if part is obvious. For the reverse statement, simply take the point $x^{\text{∗}}=\frac{b}{a_j}{e}_j$ as an example for a feasible solution (in other words, $x^{\text{∗}}$ is zero everywhere except for $j$, and $x_j=\frac{b}{a_j}\ge 0$).
• $b<0$.
  Similarly, the problem is feasible if and only if there is a $1\le j\le n$ such that $a_j<0$. With one direction being obvious, the other one follows using the feasible point $x^{\text{∗}}=\frac{b}{a_j}{e}_j$ where $\frac{b}{a_j}\ge 0$.

Simplified solution strategy. Since the problem is assumed to have a finite optimal cost, by Theorem 2.7, there exists an optimal solution which is a basic feasible solution. Consider the following mutually exclusive cases.

• $b=0$.
  We argue that $0$ is the optimal cost. Suppose for the sake of contradiction that there exists another basic feasible solution $x^{\text{∗}}$ such that $c^{\prime }{x}^{\text{∗}}<0$. Since $x^{\text{∗}}$ is a basic feasible solution, it has at most one nonzero component (Theorem 2.4 for $m=1$). But $c^{\prime }x<0$; thus, $x^{\text{∗}}$ has at least one nonzero component. Call it $x_k^{\text{∗}}>0$; we have $a_k{x}_k^{\text{∗}}=0$ (i.e., $a_k=0$) and $c_k{x}_k^{\text{∗}}<0$ (i.e., $c_k<0$). Now consider the $k$th unit vector $e_k$. For any $\alpha >0$, the scaled unit vector $\alpha \cdot e_k$ is a feasible solution for our linear program as $a^{\prime }{e}_k=0$ and $e_k\ge 0$. Furthermore, for $\alpha >0$ large enough, the optimal cost $c^{\prime }[\alpha \cdot e_k]=\alpha c_k$ of $\alpha e_k$ is unbounded from below - a contradiction to the fact that this linear program has a finite optimal cost.

• $b>0$.
  Since every basic feasible solution will have at most one nonzero component (Theorem 2.4 for $m=1$), and since $b\ne 0$, every basic feasible solution for this linear optimization problem will have exactly one nonzero component. Set

  $$k:=\underset{i=1,\dots <!--\; FUNCTION\; APPLICATION\; -->,n}{\mathrm{argmin}<!--\; FUNCTION\; APPLICATION\; -->}\left\{\frac{c_{i}b}{a_i}\mid a_i>0\right\}.$$

  Let $x^{\text{∗}}\in {\Re }^n$ be such that $x^{\text{∗}}=\frac{b}{a_k}{e}_k$, i.e., $x_k=\frac{b}{a_k}$ and $x_i=0$ for $i\ne k$. Then, $x^{\text{∗}}$ is a feasible solution, and it minimizes the objective function $c^{\prime }x$ by construction.

• $b<0$.
  Follows similarly by defining

  $$k:=\underset{i=1,\dots <!--\; FUNCTION\; APPLICATION\; -->,n}{\mathrm{argmin}<!--\; FUNCTION\; APPLICATION\; -->}\left\{\frac{c_{i}b}{a_i}\mid a_i<0\right\}.$$