[Math] Directly from primal to dual when primal not in standard form

duality-theoremslinear programming

This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, I could simply convert it first to the standard, but in this case is required that I do it directly. I also know there's plenty of tables and explanations everywhere, but I would appreciate if someone could help me out with this specific case.

Given the primal problem (P):

$$
Primal =\begin{Bmatrix}
max \ \ \ \ 2x_1 – 2x_2 +x_3 + 4x_4 \\
s.t. \ \ \ \ x_1 – x_2 – x_3 \ge 3\\
\ \ \ \ \ \ \ \ -x_1 + x_2 + x_3 \ge -3\\
\ \ \ \ \ \ \ \ \ \ + x_3 + 3x_4 \le 2\\
\ -5x_1 + 5x_2 + 4x_3 + x_4 = 10\\
\ \ \ \ x_1, x_2, x_3 \geq 0\\
\end{Bmatrix}
$$

The dual problem (D) to (P) (my solution:

\begin{array}{rlrrrrr}
\min & 3y_1 & -3y_2&+2y_3&+10y_4 \\
\mbox{s.t.} & y_1 &-y_2 && -5y_4&\geq& 2\\
&-y_1&+y_2&&+5y_4&\geq& -2\\
&-y_1&+y_2&+y_3&+4y_4&\geq& 3\\
&&&3y_3&+y_4&=& 4\\
&y_1& &&&&free\\
& &y_2,&y_3,& y_4 &\ge& 0
\end{array}

Is this correct? What's the rationale here to say if some $y_i$ is free, $\ge$ or $\le$?

Thank you very much!

Best Answer

You're close. You should have $y_1 \leq 0$, $y_2 \leq 0$, $y_3 \geq 0$, and $y_4$ should be free. Everything else is correct.

One way to view the dual of a primal maximization problem is that it arises from attempting to find a tight upper bound on the optimal value of the primal problem.

Suppose we decide to take a linear combination of the four primal constraints to find an upper bound on the optimal primal value. Then we're looking for multipliers $y_1, y_2, y_3,$ and $y_4$ to force $$\begin{align} 2x_1 - 2x_2 + x_3 + 4x_4 &\leq y_1(x_1 - x_2 - x_3) + y_2(-x_1 + x_2 + x_3) + y_3(x_3 + 3x_4) \\&\:\:\:\:\:\:\:\:\:\:\:+ y_4(-5x_1 + 5x_2 + 4x_3 + x_4) \\&\leq 3y_1 -3y_2 + 2y_3 + 10y_4 .\end{align}$$ Now, we want the upper bound to be as tight as possible, so we want to minimize $3y_1 -3y_2 + 2y_3 + 10y_4$. That's where the dual objective comes from.

In order for the second inequality to hold, we've got to flip the direction of the first inequality constraint in the primal from $\geq$ to $\leq$. In other words, we've got $x_1 - x_2 - x_3 \geq 3$, but we want $y_1(x_1 - x_2 - x_3) \leq 3y_1$. So the multiplier $y_1$ must be negative or zero. The same logic dictates that $y_2$ be negative or zero and that $y_3$ be positive or zero. The fourth primal constraint is an equality, though. Since we don't have to worry about the sign on $y_4$ flipping the inequality in the wrong direction, we don't get any restrictions on $y_4$. Thus $y_4$ is free.

Similar logic yields the form of the constraints in the dual (i.e., $=$, $\leq$, or $\geq$), which you have correct.

For more details, see my answer to "Duality. Is this the correct Dual to this Primal LP?"