Exercise 4.35 (Separation of disjoint polyhedra)

Question

Consider two noempty polyhedra $P = \{ \mathbf{x} \in \mathfrak{R}^n \mid \mathbf{Ax} \leq \mathbf{b} \}$ and $Q = \{ \mathbf{x} \in \mathfrak{R}^n \mid \mathbf{Dx} \leq \mathbf{d} \}$. We are interested in finding out whether the two polyhedra have a point in common.

(a) Devise a linear programming problem such that: if $P \cap Q$ is nonempty, it returns a point in $P \cap Q$; if $P \cap Q$ is empty, the linear programming problem is infeasible.

(b) Suppose that $P \cap Q$ is empty. Use the dual of the problem you have constructed in part (a) to show that there exists a vector $\mathbf{c}$ such that $\mathbf{c'x} < \mathbf{c'y}$ for all $\mathbf{x} \in P$ and $\mathbf{y} \in Q$.

Igor · Accepted Answer

(a)
\begin{align*}
			\max \; &  \mathbf{0'x} \
			\mbox{s.t.}\; & \mathbf{Ax} \leq \mathbf{b} \
			& \mathbf{Dx} \leq \mathbf{d} \
			& \mathbf{x} \mbox{ is free}.
		\end{align*}

(b)
The dual (D) is given by:
\begin{align*}
	\min \; &  \mathbf{p'b} + \mathbf{q'd} \
	\mbox{s.t.}\; & \mathbf{p'A} + \mathbf{q'D} = \mathbf{0} \
	& \mathbf{p} \geq \mathbf{0}, \mathbf{q} \geq \mathbf{0}.
\end{align*}

If $P \cap Q = \emptyset$, then either (D) is infeasible or unbounded. Since $\mathbf{p} = \mathbf{0}$ and $\mathbf{q} = \mathbf{0}$ produces a feasible solution, then (D) is unbounded.
			
Morevoer, assuming $\mathbf{p} = \mathbf{0}$ and $\mathbf{q} = \mathbf{0}$ and since (D) is unbouded, then $\mathbf{p'b} + \mathbf{q'd} < 0$. We can describe $P$ and $Q$ as follows:
\begin{align*}
	\mathbf{Ax} \leq \mathbf{b} \Leftrightarrow \mathbf{p'Ax} \leq \mathbf{p'b}, \mathbf{x} \geq \mathbf{0} \
	\mathbf{Dy} \leq \mathbf{d} \Leftrightarrow \mathbf{q'Dy} \leq \mathbf{q'd}, \mathbf{y} \geq \mathbf{0}.
\end{align*}
The constraints in (D) give us that $\mathbf{q'D} = - \mathbf{p'A}$. Thus, we can use it to obtain $-\mathbf{p'Ay}  \leq \mathbf{q'd}, \mathbf{y} \geq \mathbf{0}$. Next, we can sum up both inequalities:
$$
	\mathbf{p'Ax} - \mathbf{p'Ay} = \mathbf{p'A}(\mathbf{x} - \mathbf{y})  \leq \mathbf{p'b} + \mathbf{q'd} < 0.
$$
Let $\mathbf{c} = \mathbf{p'A}$, then it follows that $\mathbf{c'x} < \mathbf{c'y}$ for all $\mathbf{x} \in P$ and $\mathbf{y} \in Q$.

Exercise 4.35 (Separation of disjoint polyhedra)

Answers

Comments

Exercise 4.35 (Separation of disjoint polyhedra)

Answers

Comments

Add answer