Exercise 4.4

Question

Let A be a symmetric square matrix. Consider the linear programming problem
$$
\begin{array}{rl}
\operatorname{minimize} & \mathbf{c}^{\prime} \mathbf{x} \
	ext { subject to } & \mathbf{A x} \geq \mathbf{c} \
& \mathbf{x} \geq \mathbf{0}
\end{array}
$$
Prove that if $\mathbf{x}^{*}$ satisfies $\mathbf{A} \mathbf{x}^{*}=\mathbf{c}$ and $\mathbf{x}^{*} \geq \mathbf{0}$, then $\mathbf{x}^{*}$ is an optimal solution.

Elu Thingol · Accepted Answer

\begin{proof}
Consider the dual problem of the given primal problem:
\begin{equation*}
  \begin{array}{ll}
    	ext{minimize}\quad   &\mathbf{c}^{\prime}\mathbf{x}\
    	ext{subject to}\quad &\mathbf{A}\mathbf{x} \geq \mathbf{b}\
                           &\mathbf{x} \geq \mathbf{0},
  \end{array}
  \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*}

By the exercise assumption, the primal problem has a solution $\mathbf{x}^*$ which is feasible, i.e., $\mathbf{A}\mathbf{x}^*=\mathbf{c}$ and $\mathbf{x}^*\geq\mathbf{0}$, and is optimal with an objective value $\mathbf{c}^{\prime}\mathbf{x}^*$.\par

Since $\mathbf{A}$ is square, both problems have the sime dimension. Furthermore, notice that $\mathbf{p}^{\prime}\mathbf{A} \leq \mathbf{c}^{\prime}$ is equivalent to $\mathbf{A}^{\prime}\mathbf{p} \leq \mathbf{c}$. Since $\mathbf{A}$ is symmetric, we have $\mathbf{A}^{\prime}=\mathbf{A}$. Combining these two facts, we conclude that the condition $\mathbf{p}^{\prime}\mathbf{A} \leq \mathbf{c}^{\prime}$ in the dual problem is equivalent to $\mathbf{A}\mathbf{p}\leq\mathbf{c}$. Thus, if we set $\mathbf{p}^* := \mathbf{x}^*$, we see that $\mathbf{p}^*$ is feasible for the dual problem. Furthermore, two objective values, the primal $\mathbf{c}^{\prime}\mathbf{x}^{*}$ and the dual ${\mathbf{p}^*}^{\prime}\mathbf{c}$, obviously coincide. By the weak duality theorem (Corollary 4.2), $\mathbf{p}^*$ is also an optimal solution for the dual problem.
\end{proof}

Exercise 4.4

Answers

Comments

Exercise 4.4

Answers

Comments

Add answer