Exercise 3.5

Question

Let $P=\left\{\mathbf{x} \in \Re^{3} \mid x_{1}+x_{2}+x_{3}=1, \mathbf{x} \geq \mathbf{0}\right\}$ and consider the vector $\mathbf{x}=(0,0,1)$. Find the set of feasible directions at $\mathbf{x}$.

Elu Thingol · Accepted Answer

By Definition 3.1, a vector $\mathbf{d}\in\mathfrak{R}^n$ is feasible iff
\begin{equation}
\exists \theta > 0: \quad \mathbf{x}+\theta\mathbf{d} = \begin{bmatrix} 0 \ 0 \ 1 \end{bmatrix} + \theta \begin{bmatrix} d_1 \ d_2 \ d_3\end{bmatrix} = \begin{bmatrix} \theta d_1 \ \theta d_2 \ 1+\theta d_3\end{bmatrix} \in P.
\end{equation}

By construction of $P$, this is the same as

\begin{equation}
  \exists \theta > 0: \quad \left\{
  \begin{array}{rl}
    \theta d_1 + \theta d_2 + (1 + \theta d_3) &=1\
    \theta d_1 &\geq 0\
    \theta d_2 &\geq 0\
    1 + \theta d_3 &\geq 0.            
\end{array}\right.
\end{equation}

By canceling out $1$ in the first constraint and factoring out $\theta \neq 0$, we see that the three components of $\mathbf{d}$ must sum up to zero. Considering that $\theta > 0$, the second and the third constraints are equivalent to $\mathbf{d}_1 \geq 0$ and $\mathbf{d}_2 \geq 0$ respectively. The third constraint $\theta d_3 \geq -1$ is always satisfied by tweaking $\theta \approx 0$ when $d_3 \neq 0$ and is thus redundant (in an extreme case when $d_3=0$, we also must have $d_1,d_2 = 0$ and thus $\mathbf{d}=\mathbf{0}$ - any $\theta>0$ works in that case). We thus got rid of $\theta$ and are left with an equivalent formulation:

\begin{equation}
  \begin{array}{rl}
    d_1 + d_2 + d_3 &=0\
    d_1 &\geq 0\
    d_2 &\geq 0.
\end{array}
\end{equation}

The set of feasible directions at $\mathbf{x} \in P$ is thus

$$\left\{ \left. \begin{bmatrix} d_1 \ d_2 \ d_3 \end{bmatrix} \in \mathfrak{R}^3 \ \right| \ \begin{array}{l} d_3 = -d_1 - d_2 \[5pt] d_1,d_2 \geq 0\end{array} \right\}.$$

\begin{figure}
\includegraphics[width=0.6\textwidth]{bertsimas_linopt_exercise_3-5.png}
\caption{Feasible directions at $\mathbf{x}$.}
\end{figure}

Exercise 3.5

Answers

Comments

Exercise 3.5

Answers

Comments

Add answer