Exercise 4.8

Question

Consider the linear programming problem of minimizing $\mathbf{c}^{\prime} \mathbf{x}$ subject to $\mathbf{A x}=\mathbf{b}, \mathbf{x} \geq \mathbf{0}$. Let $\mathbf{x}^{*}$ be an optimal solution, assumed to exist, and let $\mathbf{p}^{*}$ be an optimal solution to the dual.
\begin{enumerate}[label=(\alph*)]
\item Let $	ilde{\mathbf{x}}$ be an optimal solution to the primal, when $\mathbf{c}$ is replaced by some $	ilde{\mathbf{c}}$. Show that $(	ilde{\mathbf{c}}-\mathbf{c})^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight) \leq 0$.

\item Let the cost vector be fixed at $\mathbf{c}$, but suppose that we now change $\mathbf{b}$ to $	ilde{\mathbf{b}}$, and let $	ilde{\mathbf{x}}$ be a corresponding optimal solution to the primal. Prove that $\left(\mathbf{p}^{*}ight)^{\prime}(	ilde{\mathbf{b}}-\mathbf{b}) \leq \mathbf{c}^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight).$
\end{enumerate}

Elu Thingol · Accepted Answer

\begin{enumerate}[label=(\alph*)]
\item \begin{proof} On one hand, $\mathbf{x}^*$ is an optimal solution with respect to the cost $\mathbf{c}$, i.e., $\mathbf{c}^{\prime}\mathbf{x}^* \leq \mathbf{c}^{\prime}\mathbf{x}$ for all feasible $\mathbf{x}$. In particular, $\mathbf{c}^{\prime}\mathbf{x}^* \leq \mathbf{c}^{\prime}	ilde{\mathbf{x}}$.
ewline
  On the other hand, $	ilde{\mathbf{x}}$ is an optimal solution with respect to the cost $	ilde{\mathbf{c}}$, i.e., $	ilde{\mathbf{c}}^{\prime}	ilde{\mathbf{x}} \leq 	ilde{\mathbf{c}}^{\prime}\mathbf{x}$ for all feasible $\mathbf{x}$. In particular, $	ilde{\mathbf{c}}^{\prime}	ilde{\mathbf{x}} \leq 	ilde{\mathbf{c}}^{\prime}\mathbf{x}^*$.
  Combining both facts, we obtain
  \begin{align*}
    (	ilde{\mathbf{c}}-\mathbf{c})^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight) &= 	ilde{\mathbf{c}}^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight)  - \mathbf{c}^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight)\
                                                                                           &= \left(	ilde{\mathbf{c}}^{\prime}	ilde{\mathbf{x}}-	ilde{\mathbf{c}}^{\prime}\mathbf{x}^{*}ight)  - \left(\mathbf{c}^{\prime}	ilde{\mathbf{x}}-\mathbf{c}^{\prime}\mathbf{x}^{*}ight)\
                                                                                           &\leq 0.
  \end{align*}
  \end{proof}
  
\item \begin{proof} Let $\mathbf{p}^*$ and denote the optimal solutions of the duals of the original and the modified primal problems respectively.
ewline
    On one hand, by strong duality (Theorem 4.4), we have $\mathbf{c}^{\prime}\mathbf{x}^* = (\mathbf{p}^*)^{\prime}\mathbf{b}$.
ewline
    On the other hand, for an optimal solution $	ilde{\mathbf{p}}^{*}$ of the dual of the modified problem, by strong duality, we have $\mathbf{c}^{\prime}	ilde{\mathbf{x}} = (	ilde{\mathbf{p}}^*)^{\prime}	ilde{\mathbf{b}}$. In particular, $\mathbf{p}^*$ is also feasible for the dual of the modified problem; thus, $(\mathbf{p}^{*})^{\prime}	ilde{\mathbf{b}} \leq (	ilde{\mathbf{p}}^*)^{\prime}	ilde{\mathbf{b}} = \mathbf{c}^{\prime}	ilde{\mathbf{x}}$. We thus obtain:
    \begin{align*}
      \left(\mathbf{p}^{*}ight)^{\prime}(	ilde{\mathbf{b}}-\mathbf{b}) - \mathbf{c}^{\prime}\left(	ilde{\mathbf{x}}-\mathbf{x}^{*}ight) &= \left((\mathbf{p}^{*})^{\prime}	ilde{\mathbf{b}}-(\mathbf{p}^{*})^{\prime}\mathbf{b}ight) - \mathbf{c}^{\prime}	ilde{\mathbf{x}} + \mathbf{c}^{\prime}\mathbf{x}^{*}\
                                                                                                                                              &= \left((\mathbf{p}^{*})^{\prime}	ilde{\mathbf{b}}- \mathbf{c}^{\prime}	ilde{\mathbf{x}}ight) - \left((\mathbf{p}^{*})^{\prime}\mathbf{b} -  \mathbf{c}^{\prime}\mathbf{x}^{*}ight)\
      &\leq 0.
    \end{align*}
  \end{proof}
\end{enumerate}

Exercise 4.8

Answers

Comments

Exercise 4.8

Answers

Comments

Add answer