Exercise 3.9 (Necessary and sufficient conditions for a unique optimum)

Question

Consider a linear programming problem in standard form and suppose that $\mathrm{x}^{*}$ is an optimal basic feasible solution. Consider an optimal basis associated with $\mathrm{x}^{*}$. Let $B$ and $N$ be the set of basic and nonbasic indices, respectively. Let $I$ be the set of nonbasic indices $i$ for which the corresponding reduced costs $\bar{c}_{i}$ are zero.
\begin{enumerate}[label=(\alph*)]
\item Show that if $I$ is empty, then $\mathrm{x}^{*}$ is the only optimal solution.
\item Show that $\mathbf{x}^{*}$ is the unique optimal solution if and only if the following linear programming problem has an optimal value of zero:
\begin{equation}
\begin{array}{ll}
\text{maximize}\quad &\displaystyle\sum_{i \in I} x_{i}\[3pt]
\text{subject to}\quad &\mathbf{A x}=\mathbf{b}\
&{x}_{i}=0, & i \in N\setminus I,\
&x_{i} \geq 0, & i \in B \cup I
\end{array}
\label{opt:sum}
\end{equation}
\end{enumerate}

Elu Thingol · Accepted Answer

extbf{Part (a).} \begin{proof}
  Suppose that $I$ is empty, and suppose for the sake of contradiction that $\mathbf{x}^*$ is not unique, i.e., there exists another feasible solution $\mathbf{y}^*$ such that $\mathbf{c}^{\prime}\mathbf{x}^* = \mathbf{c}^{\prime}\mathbf{y}^*$. Define a feasible direction $\mathbf{d} := \mathbf{y}^* - \mathbf{x}^*$ and consider the cost change $\mathbf{c}^{\prime}\mathbf{d}$ in terms of the reduced costs $\bar{c}_i$, $i \in N$ (cf. proof of Theorem 3.1):
  \begin{equation*}
    \mathbf{c}^{\prime}\mathbf{d} = \sum_{i \in N} \bar{c}_i d_i.
  \end{equation*}
  Using the same line of argumentation as in \href{./exercise_3-6}{Exercise 3.6}, we see that $d_i \geq 0$ for all $i \in N$, and that there must be at least one $k \in N$ such that $d_k > 0$. Furthermore, since $I$ is empty by the exercise assumption, every reduced cost $\bar{c}_i$ of $i \in N \setminus I = N$ is positive. Thus, we obtain
  \begin{equation*}
    \mathbf{c}^{\prime}\mathbf{d} = \sum_{i \in N} \bar{c}_i d_i \geq \bar{c}_k d_k > 0
  \end{equation*}
  - a contradiction to $\mathbf{c}^{\prime}\mathbf{x}^* = \mathbf{c}^{\prime}\mathbf{y}^*$.
\end{proof}

extbf{Part (b).} \begin{proof}
  \begin{description}
  \item[$\impliedby$] Suppose that $\mathbf{z}$ is an optimal solution of the linear optimization problem given in (b) with an optimal cost of $\mathbf{c}^{\prime}\mathbf{z} = 0$. Suppose for the sake of contradiction that $\mathbf{x}^*$ is not unique, i.e., there exists another feasible solution $\mathbf{y}^*$ such that $\mathbf{c}^{\prime}\mathbf{x}^* = \mathbf{c}^{\prime}\mathbf{y}^*$. Define a feasible direction $\mathbf{d} := \mathbf{y}^* - \mathbf{x}^*$. To arrive at a contradiction, we establish two following facts.
    \begin{enumerate}
    \item 	extit{$\mathbf{y}^{*}$ is a feasible solution for (1).}
ewline
      We have $\mathbf{Ay}^*=\mathbf{b}$ and $\mathbf{y}^{*} \geq \mathbf{0}$ by the conditions of the original optimization problem. Representing the assumption $\mathbf{c}^{\prime}\mathbf{x}^* = \mathbf{c}^{\prime}\mathbf{y}^*$ in terms of the reduced costs $\bar{c}_i$, $i \in N$ (cf. proof of Theorem 3.1), we obtain
      \begin{equation*}
        \mathbf{c}^{\prime}\mathbf{d} = \sum_{i \in N} \bar{c}_i d_i = \sum_{i \in N \setminus I} \bar{c}_i d_i = 0,
      \end{equation*}
      where the second equality follows from the fact that $\bar{c}_i = 0$ for $i \in I$. Furthermore, since $\bar{c}_i > 0$ for $i \in N \setminus I$, we obtain  $d_i = 0$ for $i \in N \setminus I$ and thus also $y^{*}_{i} = 0$ for $i \in N \setminus I$ (as $x^{*}_{i} = 0$ for $i \in N$).
      
    \item 	extit{$\displaystyle\sum_{i \in I} y^{*}_{i} > \displaystyle\sum_{i \in I} x^{*}_{i}$.}
ewline
      We have $\mathbf{y}^{*}_{I} \geq \mathbf{x}^{*}_{I} = \mathbf{0}$ as $I \subseteq N$. Suppose for the sake of contradiction that $\mathbf{y}^{*}_{I} = \mathbf{x}^{*}_{I}$, or in other words, $\mathbf{d}_I = \mathbf{0}$. From $\mathbf{d}_B = \sum_{i \in I} \mathbf{B}^{-1}\mathbf{A}_i d_i$ (cf. Theorem 3.1), we deduce that $\mathbf{d}_B = \mathbf{0}$ as well. From the preceding part, we see that $\mathbf{d}_{N \setminus I} = \mathbf{0}$. We therefore conclude that $\mathbf{x}^{*} = \mathbf{y}^{*}$ - a contradiction. Thus, there exists a $k \in I$ such that $y^*_k > x^*_k$ and thus $\sum_{i \in I} y^{*}_{i} > \sum_{i \in I} x^{*}_{i}$.
    \end{enumerate}
    The last assertion leads to the contradiction as we have obtained an objective value that exceeds the originally assumed maximum of $0$.
  \item[$\implies$] Suppose that $\mathbf{x}^{*}$ is the unique optimal solution. Suppose for the sake of contradiction that the optimal solution $\mathbf{z}$ of (1) yields an objective value of $\sum_{i \in I} z_i > 0$. Notice that $\mathbf{z}$ is also a feasible solution to the original optimization problem. Furthermore, from $\sum_{i \in I} z_i > 0$ we immediate that there is at least one $k \in I$ with $z_k > 0$. This fact immediately rules out the possibility for $\mathbf{z} = \mathbf{x}^*$ as $x_i = 0$ for $i \in I \subseteq N$. Using the standard procedure, set a feasible direction $\mathbf{d} := \mathbf{y}^* - \mathbf{x}^*$ and consider the cost change $\mathbf{c}^{\prime}\mathbf{d}$ along the feasible direction $\mathbf{d}$ in terms of the reduced costs $\bar{c}_i$, $i \in N$ (cf. proof of Theorem 3.1):
    \begin{equation*}
      \mathbf{c}^{\prime}\mathbf{d} = \sum_{i \in N} \bar{c}_i d_i = \sum_{i \in N \setminus I} \bar{c}_i d_i > 0,
    \end{equation*}
    where the the second equality follows from the fact that $\bar{c}_i = 0$ for $i \in I$ and the last inequality follows from the fact that $\mathbf{x}^*$ is the unique optimal solution by \href{./exercise_3-2}{Exercise 3.2}. From this inequality, we see that at least one $d_i$, $i \in N \setminus I$ should be nonzero $d_i > 0$. Since $x_i^* = 0$ for $i \in N$, this implies that $z_i > 0$ for some $i \in N \setminus I.$ But this is a contradiction to the fact that $\mathbf{z}$ is feasible for (1), as it violates the second equality constraint.
  \end{description}
  
\end{proof}

Exercise 3.9 (Necessary and sufficient conditions for a unique optimum)

Answers

Comments

Exercise 3.9 (Necessary and sufficient conditions for a unique optimum)

Answers

Comments

Add answer