1
$\begingroup$

I get the Primal LP in non-standard form

$$\begin{align} \operatorname{max} & \sum^{n}_{j = 1} {c_j x_j} \\ \operatorname{s. t.} & \sum^{n}_{j = 1} {a_{ij} x_j} = b_i & \forall i = 1, \cdots, m \\ & x_j \ge 0 & \forall j = 1, \cdots, n \end{align}$$

And I am asked to derive the Dual LP. So I standardize the Primal LP:

$$\begin{align} \operatorname{max} & \sum^{n}_{j = 1} {c_j x_j} \\ \operatorname{s. t.} & \sum^{n}_{j = 1} {a_{ij} x_j} \le b_i & \forall i = 1, \cdots, m \\ & -\sum^{n}_{j = 1} {a_{ij} x_j} \le -b_i & \forall i = 1, \cdots, m \\ & x_j \ge 0 & \forall j = 1, \cdots, n \end{align}$$

And now I use the transformation to the Dual LP:

$$\begin{align} \operatorname{min} & \sum^{m}_{i = 1} {b_i y_i} - \sum^{m}_{i = 1} {b_i y_i}\\ \operatorname{s. t.} & \sum^{m}_{i = 1} {a_{ji} y_i} - \sum^{m}_{i = 1} {a_{ji} y_i} \ge c_j & \forall j = 1, \cdots, n \\ & y_i \ge 0 & \forall i = 1, \cdots, m \end{align}$$

I don't know if I'm hallucinating or something but this to me can be simplified as

$$\begin{align} \operatorname{min} & \ \ 0\\ \operatorname{s. t.} & \ \ 0 \ge c_j & \forall j = 1, \cdots, n \\ \end{align}$$

Any help is greatly appreciated.

$\endgroup$
  • 2
    $\begingroup$ You have $2m$ inequality constraints so you need $2m$ (different!) dual variables. $\endgroup$ – Michal Adamaszek Jun 10 '18 at 18:46
  • 1
    $\begingroup$ You could also derive the dual without first transforming to the "standard" form by directly writing the Lagrangian and computing the dual function. This way you can quickly derive the dual of any problem, with various combinations of inequality and equality constraints without going through the standard representation. $\endgroup$ – Michal Adamaszek Jun 10 '18 at 18:49
2
$\begingroup$

Let's rewrite your problem as (P):

$$ \begin{aligned} & \text{max} & c^Tx \\ & \text{s.t.} & Ax = b, \\ && x \geq 0. \end{aligned} $$

The dual of this is simply (D):

$$ \begin{aligned} & \text{min} & w^T b \\ & \text{s.t.} & w A \geq c, \\ && w \text{ unrestricted}. \end{aligned} $$

The only place in the dual that we need to take the equality $Ax = b$ in the primal into consideration is in determining the sign of the entries in $w$.

To see this, rewrite the primal as you originally did, as problem (P'):

$$ \begin{align} & \text{max} & c^T x \\ & \text{s.t.} & Ax \leq b, \\ && -Ax \leq -b, \\ && x \geq 0. \end{align} $$

Let $w = [w_1 \ \ w_2]$ be the vector of decision variables for the dual to this problem, where $w_1$ corresponds the $b$ and $w_2$ corresponds to $-b$. We then have a new dual (D'):

$$ \begin{align} & \text{min} & (w_1 - w_2)^T b \\ & \text{s.t.} & (w_1 - w_2) A \geq c, \\ && w_1, w_2 \geq 0. \end{align} $$

Letting $w = w_1 - w_2$, we see that $w$ is unrestricted, so (D') is the same as (D). Notice that $w_1 = w^+$ and $w_2 = w^-$ are just the positive and negative parts of $w$.

$\endgroup$

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.