# Dual of Unbounded Linear Program

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*}

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*}

• Thank you very much. May I ask, from what reference is the table that you posted? It seems to be quite thorough! Commented Mar 7, 2017 at 13:51
• The table is in my lecture notes (in german) from the university. I don´t have a reference like a book. But I can guarantee that it works for all cases. Commented Mar 7, 2017 at 15:02
• @callculus I have a problem on quadratic programming I've been working on for days. Once I get my Lagrangian no longer in terms of $x$, I can't figure out how to get the dual problem out of it. Can you please help? I have a 100 point bounty: math.stackexchange.com/questions/2571031/…
– user100463
Commented Dec 23, 2017 at 2:39