1
$\begingroup$

Let $A\in\mathbb{R}^{m\times n}, \ c\in \mathbb{R}^n, \ b\in\mathbb{R}^m$ and consider the linear program $$\max \{ c^Tx : Ax\le b\} \ (1)$$ Its dual is $$\min \{ b^Ty : A^Ty=c, \ y\ge 0\} \ (2)$$ The weak duality theorem states that for $x$ feasible for (1) and $y$ feasible for (2), then $$c^tx\le b^ty$$

The following statement is obviously false, but where is the flaw ?

It has been shown that the dual of (2) is equivalent to (1). Then if $x$ is feasible for (1) and $y$ is feasible for (2), we have $$c^tx\le b^ty$$ by the theorem applied to (1) and its dual (2) and $$b^ty\le c^tx$$ by the theorem applied to (2) and its dual (1). Hence $c^tx=b^ty$ for any $x$ and $y$ like above.

$\endgroup$
1
$\begingroup$

A dual pair includes a maximization problem and a minimization problem. Weak duality says that a feasible solution to the maximization problem has value at most the value of a feasible solution of the minimization problem. That is, it does not give you $b^T y \leq c^T x$.

If you like, you can turn the problem of maximizing $c^Tx$ to negative the minimum of $-c^Tx$, and derive a different looking dual which would then be a maximization problem (with its end result still multiplied by $-1$). If you apply weak duality to this pair and work through the algebra you will get something essentially equivalent to what weak duality gave you for the original problem because of the negative signs. You will not get $b^Ty \leq c^T x$.

$\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.