Exercise 4.19 (Null variables)

Question

Let $P=\left\{\mathbf{x} \in \Re^{n} \mid \mathbf{A x}=\mathbf{b}, \mathbf{x} \geq \mathbf{0}\right\}$ be a nonempty polyhedron, and let $m$ be the dimension of the vector $\mathbf{b}$. We call $x_{j}$ a null variable if $x_{j}=0$ whenever $\mathbf{x} \in P$.
\begin{enumerate}[label=(\alph*)]
\item Suppose that there exists some $\mathbf{p} \in \Re^{m}$ for which $\mathbf{p}^{\prime} \mathbf{A} \geq \mathbf{0}^{\prime}, \mathbf{p}^{\prime} \mathbf{b}=0$, and such that the $j$ th component of $\mathbf{p}^{\prime} \mathbf{A}$ is positive. Prove that $x_{j}$ is a null variable.

\item Prove the converse of (a): if $x_{j}$ is a null variable, then there exists some $\mathbf{p} \in \Re^{m}$ with the properties stated in part (a).

\item If $x_{j}$ is not a null variable, then by definition, there exists some $\mathbf{y} \in P$ for which $y_{j}>0$. Use the results in parts (a) and (b) to prove that there exist $\mathbf{x} \in P$ and $\mathbf{p} \in \Re^{m}$ such that:

$$
\mathbf{p}^{\prime} \mathbf{A} \geq \mathbf{0}^{\prime}, \quad \mathbf{p}^{\prime} \mathbf{b}=0, \quad \mathbf{x}+\mathbf{A}^{\prime} \mathbf{p}>\mathbf{0}.
$$
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item \begin{proof} Consider the following pair of problems that are duals of each other:
  \begin{equation}
\begin{array}{ll}
  	ext{minimize}   \quad & -x_j\
  	ext{subject to} \quad & \mathbf{A}\mathbf{x} \geq \mathbf{b}\
                          & \mathbf{x} \geq \mathbf{0},
\end{array}
\quad\quad\quad
\begin{array}{ll}
  	ext{maximize}   \quad & \mathbf{p}^{\prime}\mathbf{b}\
  	ext{subject to} \quad & \mathbf{p}^{\prime}\mathbf{A} \leq -\mathbf{e}_j^{\prime},\
                          &
\end{array}
\label{y:linopt}
\end{equation}
where $\mathbf{e}_j$ denotes the unit vector in $j$th direction. Let $c$ denote $\mathbf{p}^{\prime}\mathbf{A}$'s $j$th direction; by assumption, $c > 0$. Define $\mathbf{q} := -\frac{1}{c}\mathbf{p}$. Then it is obvious that $\mathbf{q}$ is feasible for the dual problem as well, and the corresponding cost is $\mathbf{q}^{\prime}\mathbf{b} = -\frac{1}{c} \mathbf{p}^{\prime}\mathbf{b} = 0$. By weak duality (Theorem 4.3), the optimal cost of the primal problem cannot go lower than $0$. But it cannot be positive either; thus, we conclude that $x_j$ will always be a null variable.\end{proof}

\item \begin{proof} Since $x_j$ is a null variable, the optimal cost of the primal problem in \eqref{y:linopt} will be $0$. By strong duality (Theorem 4.4), the optimal cost of the dual problem is $0$ as well. Let $\mathbf{q}$ denote the corresponding optimal solution. Then it is easy obvious that $\mathbf{p} := -\mathbf{q}$ satisfies $\mathbf{p}^{\prime}\mathbf{A} \geq \mathbf{e}_j^{\prime} \geq \mathbf{0}^{\prime}$, $\left(\mathbf{p}^{\prime}\mathbf{A}ight)_j \geq 1 > 0$ and $\mathbf{p}^{\prime}\mathbf{b} = \mathbf{0}$. \end{proof}
  
\item \begin{proof}Let $I$ denote the indices of non-null variables, and let $N$ denote the indices of null variables. 
ewline
    By definition, for each $j \in I$, we can find a vector $\mathbf{x}^{(j)}$ such that $x^{(j)}_j > 0$. By setting $\mathbf{x}:= \sum_{j \in I}\mathbf{x}^{(j)}$, we ensure that $\mathbf{x}$ is positive at all nonnull variables.
ewline
    Similarly, by part (a), for each $j \in N$, we can find a vector $\mathbf{p}^{(j)}$ such that its $j$th component $(\mathbf{p}^{(j)\prime}\mathbf{A})_j $ is positive. Setting $\mathbf{p} := \sum_{j \in N}\mathbf{p}^{(j)}$, we ensure that $\mathbf{p}^{\prime}\mathbf{A}$ is strictly positive at every null variable.
ewline
  Finally, since both $\mathbf{x}\geq \mathbf{0}$ and $\mathbf{p}^{\prime}\mathbf{A}\geq \mathbf{0}$, adding $\mathbf{x} + \mathbf{p}^{\prime}\mathbf{A}$ results in a strictly positive vector.\end{proof}
  
\end{enumerate}

Bin_Christian · Answer

c. I think it should be set $\boldsymbol{x}: =\frac{1}{|I|}\sum_{j\in I}{\boldsymbol{x}^{(j)}}$  to satisfy $\boldsymbol{Ax=b}$.

Exercise 4.19 (Null variables)

Answers

Comments

Comments

Exercise 4.19 (Null variables)

Answers

Comments

Comments

Add answer