Exercise 3.4

Question

Consider the problem of minimizing $\mathbf{c}^{\prime} \mathbf{x}$ over the set $P=\{\mathbf{x} \in$ $\left.\Re^{n} \mid \mathbf{A x}=\mathbf{b}, \mathbf{D x} \leq \mathbf{f}, \mathbf{E x} \leq \mathbf{g}\right\}$. Let $\mathbf{x}^{*}$ be an element of $P$ that satisfies $\mathbf{D x}^{*}=\mathbf{f}, \mathbf{E x}^{*}<\mathbf{g}$. Show that the set of feasible directions at the point $\mathbf{x}^{*}$ is the set
$$
\left\{\mathbf{d} \in \Re^{n} \mid \mathbf{A d}=\mathbf{0}, \mathbf{D d} \leq \mathbf{0}\right\}
$$

Elu Thingol · Accepted Answer

\begin{proof}
By Definition 3.1, for $\mathbf{d}$ to be a feasible direction at $\mathbf{x}^*$ is equivalent to
\begin{equation}
  \exists 	heta > 0: \quad \mathbf{x}^{*}+	heta\mathbf{d} \in P.
  \label{cond:equiv2}
\end{equation}

Considering constraints defining $P$, the above is the same as:
\begin{equation}
  \begin{array}{ll}
    \mathbf{A}(\mathbf{x}^{*}+	heta\mathbf{d}) &= \mathbf{b}\
    \mathbf{D}(\mathbf{x}^{*}+	heta\mathbf{d}) &\leq \mathbf{f}\
    \mathbf{E}(\mathbf{x}^{*}+	heta\mathbf{d}) &\leq  \mathbf{g}.
  \end{array}
  \label{cond:equiv3}
\end{equation}

By theorem assumption $\mathbf{A}\mathbf{x}^* = \mathbf{b}$, and so the first condition turns into $\mathbf{A}\mathbf{d} = \mathbf{0}$. Furthermore, $\mathbf{D}\mathbf{x}^*=\mathbf{f}$; thus, the second condition becomes the same as $\mathbf{D}\mathbf{d} \leq \mathbf{0}$. Finally, $\mathbf{E}\mathbf{x}^{*} < \mathbf{g}$; thus, the third condition can be always achieved by taking $	heta$ very small and is thus redundant. To sum up, considering assumptions made on $\mathbf{x}^*$, \eqref{cond:equiv3} is equivalent to
\begin{equation}
  \begin{array}{ll}
    \mathbf{A}\mathbf{d} = \mathbf{b}\
    \mathbf{D}\mathbf{d} \leq \mathbf{0}.
  \end{array}
  \label{cond:equiv4}
\end{equation}

This is exactly the condition defining the set in question, and we are done.
\end{proof}

Exercise 3.4

Answers

Comments

Exercise 3.4

Answers

Comments

Add answer