3
$\begingroup$

This is question 4.35 from Introduction to Linear Optimization by Bertsimas and Tsitsiklis.

The problem

Consider two non-empty polyhedra $P=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Ax}\leq\mathbf{b}\}$ and $Q=\{\mathbf{x}\in\mathbb{R}^n\ |\ \mathbf{Dx}\leq\mathbf{d}\}$.

(a) Devise a linear programming problem such that: if $P\cap Q\neq\varnothing$, it returns a point in $P\cap Q$; if $P\cap Q=\varnothing$, 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}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y}$ for all $\mathbf{x}\in P$ and $\mathbf{y}\in Q$.

Attempted solution

I think I have an answer for part (a): $$ \begin{array}{rl} \text{max}\quad&\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}\quad&\mathbf{Ax}\leq\mathbf{b} \\ & \mathbf{Dx}\leq\mathbf{d} \end{array} $$

This seems to accomplish the requirements of part (a). I am stuck on part (b). The dual of the above linear program is $$ \begin{array}{rl}\text{min}\quad&\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d}\\\text{s.t.}\quad&\mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T}\\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} $$ If we assume the primal is infeasible (i.e. $P\cap Q=\varnothing$), then the dual is either infeasible or unbounded. Since $\mathbf{p}_1=\mathbf{0}$, $\mathbf{p}_2=\mathbf{0}$ is feasible for the dual, it must be unbounded. I think this might be a useful fact, but I can't see exactly how.

Geometrically, this question is very straightforward. But I'm struggling to come up with the algebra to show the existence of this $\mathbf{c}$.

Similar question

The question found here is similar, but I'm not interested in computing the separating hyperplane, just proving its existence.

$\endgroup$
  • 1
    $\begingroup$ Before I proceed to help you answering the question, you should have a look at your "dual" LP. I don't think that it is correct. $\endgroup$ – Willem Hagemann Feb 16 '17 at 11:07
  • $\begingroup$ Ah, I seem to have flipped my inequalities on the bounds for $\mathbf{p}_1$ and $\mathbf{p}_2$. Is that what you were referring to? Thanks for tip! $\endgroup$ – David M. Feb 18 '17 at 19:13
  • $\begingroup$ There is still more. The transpose of $Ax \leq b, Dx \leq d$ is also incorrect. Try to fix that and you will see, I'm quite sure. $\endgroup$ – Willem Hagemann Feb 18 '17 at 19:48
  • $\begingroup$ Hint: The correct form of the dual LP is: minimize $p_1^Tb+p_2^Td$ s.t. $A^Tp_1 + D^Tp_2 = 0, p_1 \geq 0, p_2\geq 0$. $\endgroup$ – Willem Hagemann Feb 19 '17 at 0:06
  • $\begingroup$ Sorry for slow responses. I see why that dual is correct--each variable in the primal is a constraint in the dual, so we just want one constraint, corresponding to the primal variable $\mathbf{x}$. I feel like I now apply either Farkas' lemma or the separating hyperplane theorem, since that's the most obvious thing I can think of to give the existence of some $\mathbf{c}$. Am I headed in the right direction? $\endgroup$ – David M. Feb 21 '17 at 1:05
2
$\begingroup$

(a) The linear program

\begin{array}{rl} \max &\mathbf{0}^\text{T}\mathbf{x} \\ \text{s.t.}&\mathbf{Ax}\leq\mathbf{b} \tag{P}\label{P}\\ & \mathbf{Dx}\leq\mathbf{d} \end{array}

suggested by the OP responds to the problem.

(b) Since $P \cap Q = \varnothing$, each of these two points satisfies exactly one of the two constraints in \eqref{P} (from the definition of $P$ and $Q$).

The OP's deduction is correct:

The dual for \eqref{P} is \begin{array}{rl} \min & \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \\ \text{s.t.} & \mathbf{p}_1^\text{T}\mathbf{A}+\mathbf{p}_2^\text{T}\mathbf{D}=\mathbf{0}^\text{T} \tag{D} \label{D} \\ & \mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0} \end{array} The infeasibility of \eqref{P} and the feasibility of \eqref{D} (with $\mathbf{p}_1 = {\bf 0}, \mathbf{p}_2 = {\bf 0}$) implies that \eqref{D} is unbounded.

From the unboundedness of \eqref{D}, we deduce that for each $z \in \Bbb R$, there exists $\mathbf{p}_1,\mathbf{p}_2\geq\mathbf{0}$ such that $\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \le z$. In particular, we fix $\epsilon > 0$ and take $z = -\epsilon$, so that $$\mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} < 0 \tag{*} \label{*}.$$

For all ${\bf x} \in P$ and ${\bf y} \in Q$, we have (from the definition of $P$ and $Q$)

\begin{align} \mathbf{Ax} &\leq \mathbf{b} \tag{1}\label{1} \\ \mathbf{Dy} &\leq \mathbf{d} \tag{2}\label{2} \end{align}

Multiply $\mathbf{p}_1^\text{T}$ and $\mathbf{p}_2^\text{T}$ on both sides of \eqref{1} and \eqref{2} respectively. (We can do so since $\mathbf{p}_1 \ge {\bf 0}, \mathbf{p}_2 \ge {\bf 0}$.)

\begin{align} \mathbf{p}_1^\text{T}\mathbf{Ax} &\leq \mathbf{p}_1^\text{T}\mathbf{b} \tag{3}\label{3} \\ \mathbf{p}_2^\text{T}\mathbf{Dy} &\leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4}\label{4} \end{align}

Substitute the constraint in \eqref{D} into \eqref{4}.

$$(-\mathbf{p}_1^\text{T}\mathbf{A}){\bf y} \leq \mathbf{p}_2^\text{T}\mathbf{d} \tag{4'}\label{4'}$$

Add \eqref{3} and \eqref{4'}.

$$\mathbf{p}_1^\text{T}\mathbf{A} ({\bf x} - {\bf y}) \le \mathbf{p}_1^\text{T}\mathbf{b}+\mathbf{p}_2^\text{T}\mathbf{d} \stackrel{\eqref{*}}< 0 \tag{$\star$} \label{fin}$$

It's evident from \eqref{fin} that ${\bf c} = (\mathbf{p}_1^\text{T}\mathbf{A})^\text{T} = \mathbf{A}^\text{T} \mathbf{p}_1$ satisfies $$\mathbf{c}^\text{T}\mathbf{x}<\mathbf{c}^\text{T}\mathbf{y} \quad \forall \mathbf{x} \in P, \forall \mathbf{y} \in Q.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.