Exercise 3.6 (Conditions for a unique optimum)

Question

Let $\mathbf{x}$ be a basic feasible solution associated with some basis matrix B. Prove the following:
\begin{enumerate}[label=(\alph*)]
\item If the reduced cost of every nonbasic variable is positive, then $\mathbf{x}$ is the unique optimal solution.
\item If $\mathbf{x}$ is the unique optimal solution and is nondegenerate, then the reduced cost of every nonbasic variable is positive.
\end{enumerate}

Elu Thingol · Accepted Answer

We implement some minor changes to the proof of Theorem 3.1. Accordingly, we denote the basic feasible solution by $\mathbf{x}$, the associated basis matrix by $\mathbf{B}$ and the corresponding vector of reduced costs by $\bar{\mathbf{c}}$.
  \begin{proof}
    \begin{enumerate}[label=(\alph*)]
    \item We assume that $\bar{\mathbf{c}} > 0$, we let $\mathbf{y} \in P: \mathbf{y} 
eq \mathbf{x}$ be an arbitrary feasible solution, and we define $\mathbf{d}=\mathbf{y}-\mathbf{x}$. Feasibility implies that $\mathbf{Ax} = \mathbf{Ay} = \mathbf{b}$ and, therefore, $\mathbf{Ad} = \mathbf{0}$. The latter equality can be rewritten in the form
      $$\mathbf{B}\mathbf{d}_B + \sum_{j \in N} \mathbf{A}_{j} d_{j} = 0,$$
      where $N$ is the set of indices corresponding to the nonbasic variables under the given basis. Since $\mathbf{B}$ is invertible, we obtain
      $$\mathbf{d}_B = - \mathbf{B}^{-1} \mathbf{A}_{j} d_{j},$$
      and
      \begin{equation*}
        \mathbf{c}^{\prime}\mathbf{d} = \mathbf{c}^{\prime}_B\mathbf{d}_B  + \sum_{j \in N} c_{j} d_{j} = \sum_{j \in N} (c_{j} - \mathbf{B}^{-1} \mathbf{A}_{j}) d_{j} = \sum_{j \in N} \bar{c}_j d_{j}.
      \end{equation*}
      For any nonbasic index $j \in N$, we must have $x_j = 0$; thus,
      \begin{equation*}
        \mathbf{c}^{\prime}\mathbf{d} = \sum_{j \in N} \bar{c}_j y_{j}.
      \end{equation*}
      Since $\mathbf{y}$ is feasible, we have $y_j \geq 0$. Suppose for the sake of contradiction that $y_j = 0$ for all nonbasic indices $j \in N$. Then $\mathbf{Ay} = \mathbf{By} = \mathbf{b}$ and thus $\mathbf{y}_B = -\mathbf{B}^{-1}\mathbf{b} = \mathbf{x}_B$. But this would imply that $\mathbf{y}$ and $\mathbf{x}$ agree both on basic and non-basic variables and are thus equal - a contradiction. Thus, there exists at least one $k 
otin B$ such that $y_{k} 
eq 0$ and thus
      \begin{equation*}
        \mathbf{c}^{\prime}\mathbf{d} = \sum_{j \in N} \bar{c}_j y_{j} \geq \bar{c}_k y_{k} > 0.
      \end{equation*}
      We conclude that $\mathbf{c}^\prime(\mathbf{y}-\mathbf{x}) = \mathbf{c}^\prime\mathbf{d} > 0$, and since $\mathbf{y}$ was an arbitrary feasible solution, $\mathbf{x}$ is the unique optimal solution.

\item Suppose that $\mathbf{x}$ is a nondegenerate basic feasible solution. Suppose for the sake of contradiction that $\bar{c}_k \leq 0$ for some $k$. Since the reduced cost of a basic variable is always zero, $x_k$ must be a nonbasic variable and $\bar{c}_k$ is the rate of cost change along the $k$th basic direction $\mathbf{d}$. We use $\mathbf{d}$ to construct a contradiction. Since $\mathbf{x}$ is nondegenerate, the $k$th basic direction $\mathbf{d}$ is a feasbile direction of cost decrease (cf. page 86); thus, there exists a $	heta > 0$ such that $\mathbf{x} + 	heta \mathbf{d} \in P$. We have
      $$ \mathbf{c}^{\prime}\mathbf{d} = \sum_{j \in N} \bar{c}_j d_{j} = \bar{c}_k 1 \leq 0,$$
      since $\mathbf{d}$ is everywhere zero for nonbasic indices except for $d_{k}=1$. But then we have
      $$ \mathbf{c}^{\prime}(\mathbf{x} + 	heta \mathbf{d}) = \mathbf{c}^{\prime}\mathbf{x} + 	heta \mathbf{c}^{\prime}\mathbf{d} \leq \mathbf{c}^{\prime}\mathbf{x}.$$
      In other words, we have constructed an element $\mathbf{x} + 	heta \mathbf{d}$ of $P$ whose costs are at most the costs of $\mathbf{x}$ - a contradiction to the fact that $\mathbf{x}$ is a unique opimal solution.
    \end{enumerate}
  \end{proof}

Exercise 3.6 (Conditions for a unique optimum)

Answers

Comments

Exercise 3.6 (Conditions for a unique optimum)

Answers

Comments

Add answer