Exercise 4.13* (Degeneracy and uniqueness - II)

Question

Consider the following pair of problems that are duals of each other:

\begin{equation*}
\begin{array}{ll}
  	ext{minimize}   \quad & \mathbf{c}^{\prime}\mathbf{x}\
  	ext{subject to} \quad & \mathbf{A}\mathbf{x} = \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}.\
                          & 
\end{array}
\end{equation*}

\begin{enumerate}[label=(\alph*)]
\item Prove that if one problem has a nondegenerate and unique optimal solution, so does the other.

\item Suppose that we have a nondegenerate optimal basis for the primal and that the reduced cost for one of the basic variables is zero. What does the result of part (a) imply? Is it true that there must exist another optimal basis?
\end{enumerate}

Armaan · Accepted Answer

\begin{itemize}
\item We can note that for the basic indices, non-negativity constraints cannot be tight as we will have a degenerate solution if they were. Hence, using complimentary slackness, for the basic variables $c’- p’B = 0$, note we have exactly $m$ tight constraints at this dual feasible solution hence by definition it is  non-degenerate dual basic feasible solution. 
\item The result from (a) doesn’t hold here.
\end{itemize}

Exercise 4.13* (Degeneracy and uniqueness - II)

Answers

Comments

Exercise 4.13* (Degeneracy and uniqueness - II)

Answers

Comments

Add answer