Primal/Dual Proof.

Question

I have a test tomorrow in one of my classes and I am trying to solve a proof in the practice problems. I am unsure how to start or what methods to use.

Consider the primal/dual pair of LP's

(P):

max cx
Ax=b
x>=0

(D):

min yb
yA>=c
y is free

Suppose that (P) and (D) have primal/dual solutions x* and y* with objective value z*. Show that for any vector t, if we change the constraints in the (P) to (P'):

max cx
Ax=b+t
x>=0

then (P') is either infeasible or has an optimal solution x' with objective value z'<=z*+y*t.

Answer 1

If (P') is infeasible, then we have nothing to do.

Let $\mathbf{x'}$ be any feasible solution to the perturbed primal (P'), and $z=\mathbf{c}^T\mathbf{x'}$ be corresponding objective value. (For consistency of the notations, we denote $\mathbf{x'^{*}}$ and $z'^*$ the optimal solution and objective value for (P') respectively.)

Consider $\mathbf{y^*}^TA\mathbf{x'}$.

• $\mathbf{y^*}^TA\mathbf{x'} \ge \mathbf{c}^T\mathbf{x'}=z'$ since we have $A^T\mathbf{y^*} \ge \mathbf{c}$ (from which we take transpose: $\mathbf{y^*}^T A \ge \mathbf{c}^T$) and $\mathbf{x'} \ge 0$ from (P').
• $\mathbf{y^*}^TA\mathbf{x'} = z^* + \mathbf{y^*}^T\mathbf{t}$
  • $A\mathbf{x'}=\mathbf{b}+\mathbf{t}$ from (P').
  • Multiply $\mathbf{y^*}^T$ on both sides of the above equation. \begin{align} \mathbf{y^*}^T A\mathbf{x'} = \mathbf{y^*}^T (\mathbf{b}+\mathbf{t}) \end{align}
  • $z^*=\mathbf{y^*}^T\mathbf{b}$ as $\mathbf{y^*}$ is the optimal solution of (D).
  • The RHS of the desired inequality appears. \begin{align} \mathbf{y^*}^T A\mathbf{x'} = z^* + \mathbf{y^*}^T \mathbf{t} \end{align}

For any feasible solution $\mathbf{x'}$ to (P'), we have $$z' \le \mathbf{y^*}^T A\mathbf{x'} = z^* + \mathbf{y^*}^T \mathbf{t}.$$ It remains to show the existence of an optimal solution. We observe that (P') is bounded from the inequality we have just proved. Therefore, (P') has an optimal solution $\mathbf{x'^*}$.