Duality for other forms

In Duality we only define dual problems for problems of standard form where is of full row rank. Since this captures every linear optimization problem up to equivalence, we can deduce the dual problems of other forms.

First, we remove the constraint of being of full row rank. It turns out that the dual is identical to the case when is of full row rank.

Theorem

Consider a linear optimization problem in standard form, where is not necessarily of full row rank. Assuming there are solutions to , the dual problem of is for which weak and strong duality still hold.

Proof:
Let be distinct indices such that the corresponding rows of form a basis for the row space of , and let be the remaining indices. Let denote with rows selected. Since the rows of are linear combinations of rows of we have for some matrix , and since has solutions we must also have .
Then is equivalent to whose dual by definition is For we have and so by introducing we see that is free in , so reduces to which is exactly the dual we derived since . Since the cost function has not changed, weak and strong duality must still hold.

Now consider instead a problem of canonical form, i.e. Our initial idea of summing equalities now transfers nicely to summing inequalities: with the added constraint that to preserve the inequality direction. It then still holds that whenever i.e. , we get as a lower bound for the cost.

Theorem

Consider a linear optimization problem in canonical form, The dual problem of is for which weak and strong duality still hold.

Proof:
By adding slack variables for each constraint in we get a problem in standard form: where and . By the previous theorem its dual is Notice that the last constraints are simply . This is thus equivalent to which is precisely . By the previous theorem and since we haven't changed the cost function, weak and strong duality still hold.

Theorem: The complementary theorem

Consider a linear optimization problem in canonical form, and its dual . For every and we let Then and are feasible for and , respectively, if and only if Furthermore, and are optimal if and only if it also holds that or equivalently, for all suitable .

Proof:
The first equivalence is clear: and . For the second equivalence, notice that By strong duality we know are optimal if and only if i.e. Since this is equivalent to . The final equivalence also follows since .

Remark

In other words, are optimal iff for every , either or , and either or .