how do I find the dual when a variable has an upper bound?

Question

What is the dual of this primal LP? $$ max~c^Tx $$ $$ s.t.~Ax=0 $$ $$ 0 \leq x \leq d,~d \in \mathbb{R}_+^n $$

Hint: for purposes of deriving the dual, rewrite the bound as an explicit constraint. — RobPratt, Sep 15 at 15:45

RobPratt · Accepted Answer · 2023-09-15 19:47:24Z

1

You can imagine the upper bound for the variable is another constraint.

$\max: c^Tx$

$\text{s.t.}$

$Ax = 0$ --> $π_1$

$x ≤ d$ --> $π_2$

$0 ≤ x$

Therefore, you will obtain the following dual form. (Assume $A$ is $m \times n$ matrix)

$\min: d^Tπ_2 $

$\text{s.t.}$

$π_1A + π_2 ≥ c$

$π_1 \in \mathbb{R}^m$

$0 ≤ π_2$

RobPratt

30.4k1 gold badge43 silver badges83 bronze badges

answered Sep 15 at 16:03

ytsao

3281 silver badge7 bronze badges

2

$\begingroup$ Equality constraints have free duals. $\endgroup$
– RobPratt
Sep 15 at 16:41
$\begingroup$ @RobPratt Thanks for correcting my typo $\endgroup$
– ytsao
Sep 15 at 17:18

Add a comment |

1 Answer 1