Compare two $a$ and $b$ LPP, and show that if $a$ has non empty feasible region the optimal value of $a$ is either equal to zero or $a$ is unbounded

Question

I have the following information with me consider two LPP $a$ and $b$.

$(b)$ is a standard non empty LPP : $(b)$ min (${c^{T} x, x \in P }$), $P=\{x \in \mathbb{R}^n: Ax=b, x \ge 0\}$where $A \in \mathbb{R}^{m×n}$, $b \in \mathbb{R}^m$ and $c \in \mathbb{R}^n$

let $\hat{x} \in P$ be an arbitary feasible solution. Let $B = (\{j = \{1,\ldots,n\} : x_j >0 \}$ and $N = \{j = \{1,\ldots,n\} : x_j =0 \}$.

Consider the LLP $(a)$ min ${c^{T}_B d_{B} + c^{T}_N d_{N}}$

s.t. $A_{B} d_{B} + A_{N} d_{N} = 0 $ and $d_{N} \ge 0$

where $c_{B} \in \mathbb{R}^{|B|} $, $c_{N} \in \mathbb{R}^{|N|} $ denote the sub vectors of $c \in \mathbb{R}^{n} $ corresponding to indices $B$ and $N$ and $d_{B}$ and $d_{N}$ are decision variables.

1. We need to show that $(a)$ has a nonempty feasible region and the optimal value of $(a)$ is either equal to 0 or it is unbounded.
2. x is an optimal solution of (b) if and only if optimal value of (a) is zero

My approach to this Question is to show that (a) has a finite optimal value(not able to show it is 0) or it is unbounded.

To prove that we would assume that $ x \in P$ has a rank $k < n$. We show that there exists y $\in$ P such that, $c^T y \le c^T x$. We let $I = \{i:a_i x = b\}$ where $a_i$ is the $i$-th row in A

We now choose a non zero d $\in R^n$ orthogonal to $a_i$, i $\in I$

We suppose that $c^T d <0$

We consider a half line for $k > 0 $ a scalar $ y = x + k d$. As all points on the half line satisfy $a^T x_i = b \implies a^T y_i = b, i \in I$

if the entire half space will be contained in $P$ then the optimal cost will be $- \infty $ ie unbounded.

This has what I have so far done, I cannot proof the if not unbounded, then the optimal value of (a) is equal to $0$

Answer 1

Clearly, a feasible solution for $(a)$ is let $d=0$ of which it means the optimal value is non-positive.

Hint to complete the argument:

• Verify this: If $d$ is a feasible solution of $(a)$ and $k>0$, show that $kd$ is also a feasible solution to $(a)$.
• Use the lemma above to show that if the optimal value is non-zero, then it is unbounded.

Further guide: if the objective function evaluated at $d$ is $y$, examine what is the objective function evaluated at $2d$, what about $kd$?

Remark: Description of $(b)$ is just meant to define $(a)$, focus on proving something simpler like:

"Prove that $\min c^Tx$ subject to $Ax=0$ either attain the optimal value of $0$ or it is unbounded."

---

Edit after attempt is shown:

We first prove that the $(a)$ is feasible. Note that $0$ is a feasible solution and hence the optimal value is non-positive.

Suppose there exists a $d$ such that it is feasible to $(a)$, then let $k>0$, then $kd$ remains feasible since $kd_n \ge 0$ and $A_B(kd_B)+A_N(kd_N)=k(A_Bd_B+A_Nd_N)=k0=0$.

Furthermore, $c^T(kd)=k(c^Td)$. Hence suppose there is a $d$ such that $c^Td < 0$, then $c^T(kd)=k(c^Td)$, that is the objective function get scaled by $k$. We can let $k$ be arbitarily large and hence if a negative value can be obtained, then it is unbounded. Otherwise the optimal value is $0$.

Comment about your attempt:

• What does it mean by $x$ has rank $k$? For $x$ to be feasible, clearly $I=\{1,\ldots, m\}$.
• What if $A$ is the identity matrix? In that case, you won't be able to construct your $d$.