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 Answer 1

2
$\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*}

enter image description here

$\endgroup$
3
  • $\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
    Commented Mar 7, 2017 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$ Commented Mar 7, 2017 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$
    – user100463
    Commented Dec 23, 2017 at 2:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .