Dual of Unbounded Linear Program

Question

For an LP of the form \begin{equation*} \begin{aligned} & \underset{\textbf{x}}{\text{minimize}} & & \textbf{c}^T \textbf{x} \\ & \text{subject to} & & \textbf{A} \textbf{x} \geq \textbf{b} \\ & && \textbf{x} \geq 0 \end{aligned} \end{equation*} the dual is \begin{equation*} \begin{aligned} & \underset{\textbf{y}}{\text{maximize}} & & \textbf{y}^T \textbf{b} \\ & \text{subject to} & & \textbf{y}^T \textbf{A} \leq \textbf{c}^T \\ & && \textbf{y} \geq 0 \end{aligned} \end{equation*} My question is, what is the dual if we remove the $\textbf{x} \geq 0$ constraint from the primal problem? In other words, what is the dual of \begin{equation*} \begin{aligned} & \underset{\textbf{x}}{\text{minimize}} & & \textbf{c}^T \textbf{x} \\ & \text{subject to} & & \textbf{A} \textbf{x} \geq \textbf{b} \end{aligned} \end{equation*}

Answer 1

You can look at the table below and see how to transform a primal problem into a dual problem. You have a $\color{blue}{\texttt{Min}}$-problem. Therefore you read the table from right to left. In your case you go to the 6 th row. Here you can read, if the primal Min-problem has free variables the corresponding constraints are equalities.

Consequently the dual of your second problem is

\begin{equation*} \begin{aligned} & \underset{\textbf{y}}{\text{maximize}} & & \textbf{y}^T \textbf{b} \\ & \text{subject to} & & \textbf{y}^T \textbf{A} =\textbf{c}^T \\ & && \textbf{y} \geq 0 \end{aligned} \end{equation*}