Exercise 4.26

Question

Let $\mathbf{A}$ be a given matrix. Show that exactly one of the following alternatives must hold.
\begin{enumerate}[label=(\alph*)]
\item There exists some $\mathbf{x} 
eq \mathbf{0}$ such that $\mathbf{A x}=\mathbf{0}, \mathbf{x} \geq \mathbf{0}$.
\item There exists some $\mathbf{p}$ such that $\mathbf{p}^{\prime} \mathbf{A}>\mathbf{0}^{\prime}$.
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{remark} Note that the existence of a vector $\mathbf{p}$ such that $\mathbf{p}^{\prime}\mathbf{A} > \mathbf{0}$ is equivalent to the existence of a vector $\mathbf{p}$ such that $\mathbf{p}^{\prime}\mathbf{A} > \mathbf{e}$, where $\mathbf{e}$ is the vector with all components equal to 1, since we can always rescale the former using a scalar large enough so that all of the components of $\mathbf{p}^{\prime}\mathbf{A} > \mathbf{0}$ become larger than $1$.
\end{remark}

\begin{proof}
The trick is to consider the following pair of problems that are duals of each other:
\begin{equation}
  \begin{array}{ll}
    	ext{minimize}   \quad & \mathbf{p}^{\prime}\mathbf{0}\
    	ext{subject to} \quad & \mathbf{p}^{\prime}\mathbf{A} \geq \mathbf{e}_j^\prime,\
                            &
  \end{array}
  \quad\quad\quad
  \begin{array}{ll}
    	ext{maximize}   \quad & \mathbf{e}^{\prime}\mathbf{x}\
    	ext{subject to} \quad & \mathbf{A}\mathbf{x} = \mathbf{0}\
                            & \mathbf{x} \geq \mathbf{0}.
  \end{array}
  \label{y:linopt}
\end{equation}

\begin{itemize}
\item Suppose that (b) holds. Then the primal problem in \eqref{y:linopt} is feasible with the optimal cost $0$. By strong duality (Theorem 4.4), the dual problem has an optimal cost of $0$ as well. Suppose that there exists a $\mathbf{x}
eq 0$ with $\mathbf{A}\mathbf{x} = \mathbf{0}$ and $\mathbf{x} \geq 0$. Then $\mathbf{x}$ is feasible for the dual problem in \eqref{y:linopt}, and its cost is $\mathbf{e}^{\prime}\mathbf{x} > 0$ - a contradiction. Thus, only (b) holds.
\item Suppose that (b) does not hold. Then the primal problem in \eqref{y:linopt} is infeasible. From Table 4.2 we know that the dual problem must then be either infeasible or unbounded. The former case does not hold since the zero vector $\mathbf{0}$ is always feasible for the dual problem in \eqref{y:linopt}. Thus, the dual is unbounded. In other words, $\mathbf{e}^{\prime}\mathbf{x} > 0$ is achievable for some $\mathbf{x}$ with $\mathbf{A}\mathbf{x} = \mathbf{0}$ and $\mathbf{x} \geq \mathbf{0}$ - implying that $\mathbf{x} 
eq \mathbf{0}$. In other words, (a) holds.
\end{itemize}
\end{proof}

Exercise 4.26

Answers

Comments

Exercise 4.26

Answers

Comments

Add answer