Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.