Exercise 4.21* (Clark's theorem)

Question

Consider the following pair of linear programming problems:

\begin{equation*}
\begin{array}{ll}
  	ext{minimize}   \quad & \mathbf{c}^{\prime} \mathbf{x}\
  	ext{subject to} \quad & \mathbf{A x} \geq \mathbf{b}\
                          & \mathbf{x} \geq \mathbf{0},
\end{array}
\quad\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{c}^{\prime} \
                          & \mathbf{p} \geq \mathbf{0} .
\end{array}
\end{equation*}

Suppose that at least one of these two problems has a feasible solution. Prove that the set of feasible solutions to at least one of the two problems is unbounded. Hint: Interpret boundedness of a set in terms of the finiteness of the optimal cost of some linear programming problem.

Elu Thingol · Accepted Answer

By the exercise assumption, either the primal or the dual problem has a feasible solution. By Theorem 4.1, it does not matter which. Furthermore, the feasible set of the primal problem is either unbounded or bounded. In the former case, we are done. To sum up, it suffices to prove the exercise for the case when the primal problem has an optimal solution and its feasible set is bounded.

\begin{proof} If we manage to demonstrate that it is possible for the dual problem to have an unbounded objective value for some objective function $\mathbf{p}^{\prime}\bar{\mathbf{b}}$ of $\mathbf{p}$, then we can safely conclude that the feasible set of the dual problem is unbounded. One possibility is to show that the primal of such dual is infeasible (cf. Table 4.2). We follow up on this strategy.
ewline

Consider the original equality constraint $\mathbf{b}$. The trick is to enlarge it so that we can violate $\mathbf{A}\mathbf{x}\geq\mathbf{b}$. Since the primal problem has a bounded feasible set, there exists a scalar $M < \infty$ such that for any feasible $\mathbf{x}$ of the primal problem, the first row $\mathbf{a}_1^{\prime}\mathbf{x}$ of $\mathbf{A}\mathbf{x}$ is bounded by $M > \mathbf{a}_1 ^{\prime}\mathbf{x} \geq b_1$. We violate this condition by setting $\bar{b}_1 := M$ and $\bar{b}_i = b_i$ for the rest of the components. The new constraint $\bar{\mathbf{b}}$ results in the following modified primal and modified dual problems:
\begin{equation*}
\begin{array}{ll}
  	ext{minimize}   \quad & \mathbf{c}^{\prime} \mathbf{x}\
  	ext{subject to} \quad & \mathbf{A x} \geq \bar{\mathbf{b}}\
                          & \mathbf{x} \geq \mathbf{0},
\end{array}
\quad\quad\quad\quad
\begin{array}{ll}
  	ext{maximize}   \quad & \mathbf{p}^{\prime} \bar{\mathbf{b}} \
  	ext{subject to} \quad & \mathbf{p}^{\prime} \mathbf{A} \leq \mathbf{c}^{\prime} \
                          & \mathbf{p} \geq \mathbf{0} .
\end{array}
\end{equation*}

The modified primal problem above is infeasible by construction. By Table 4.2, the modified dual must be either infeasible or unbounded. The feasible set of the modified problem is, however, the same as the feasible set of the original dual problem. By the strong duality (Theorem 4.4), the feasible set of the original dual problem was nonempty since its primal had a bounded feasible set and therefore a finite cost. Thus, the latter case holds, i.e., the modified dual problem is unbounded, as is the feasible set of the original dual problem.
\end{proof}

Exercise 4.21* (Clark's theorem)

Answers

Comments

Exercise 4.21* (Clark's theorem)

Answers

Comments

Add answer