Given $A\in\mathbb{R}^{m\times n},\ B\in\mathbb{R}^{m\times m}, c\in\mathbb{R}^n, b, d\in\mathbb{R}^m$, $B$ nonsingular, I've been tasked with solving the following LP problem (denoted (P)): $$ \max_{x,u} c^\top x + d^\top u \\ \text{s.t. }\ Ax + Bu = b,\quad x\ge0,\quad u\ \text{ free} $$ First I eliminated the free variable by introducing $v, w\ge 0$ and writing $u = v - w$. Then I analyzed (P)'s dual problem (denoted (D)), which if I did everything correctly should be $$ \min_{y} b^\top y \\ \text{s.t. }\ A^\top y\le c,\quad B^\top y = d,\quad y\ge 0 $$ Since $B$ is nonsingular, the dual's feasible region is either a singleton or empty, depending on whether or not $A^\top (B^{-1})^\top d\le c$ respectively. If this condition is met, then the dual is feasible and bounded with optimal solution $y^* = (B^{-1})^\top d$.

On the other hand, looking at (P) again, for any given $x\ge 0$ there is precisely one $u$ satisfying the constraint $Ax + Bu = b$, and that's $u = B^{-1}(b - Ax)$. So we can really look at maximizing $c^\top x + d^\top(B^{-1}(b - Ax))$ subject to $x\ge 0$. This is equivalent to maximizing $(c^\top - d^\top B^{-1}A)x$ subject to $x\ge 0$.

Now, if $c^\top \ge d^\top B^{-1}A$, then clearly (P) is unbounded (since for any $x\ge 0$ and $r>1$, $(c^\top - d^\top B^{-1}A)(rx) \ge (c^\top - d^\top B^{-1}A)x$.

However, this is precisely the same condition as the one above which guaranteed that the dual was feasible and bounded. If $c \ge A^\top(B^\top)^{-1}d$, then from the discussion above the dual should be bounded and feasible, but we now also have that the primal is unbounded and thus the dual is infeasible. These two things cannot be true simultaneously.

What's gone wrong here? Is my dual (D) correct? I'll walk through the steps again to ensure everything is fine, though I'm fairly certain it's correct.


In the dual problem, the first constraint should be $\ge c$ instead of $\le c$, and $y$ should be free instead of $\ge 0$.


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.