2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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



$\endgroup$
  • $\begingroup$ Thank you very much. May I ask, from what reference is the table that you posted? It seems to be quite thorough! $\endgroup$ – John Stash Mar 7 '17 at 13:51
  • $\begingroup$ 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. $\endgroup$ – callculus Mar 7 '17 at 15:02
  • $\begingroup$ @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/… $\endgroup$ – ALannister Dec 23 '17 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.