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.

I've attached an image of my book (Theorem 4.4.1 is at the bottom of the image). I need help understanding what this book is saying.

In the first sentence on p.113:

"If (I) holds, then the primal is feasible, and its optimal objective is obviously zero",

They are talking about the scalar value resulting from taking the dot product of the zero vector and $x$, right? That's obviously zero. Because if they're talking about $x$ itself, then it makes no sense. Okay.

Next sentence:

"By applying the weak duality result (Theorem 4.4.1), we have that any dual feasible vector $u$ (that is, one which satisfies $A'u \ge 0$) must have $b'u \ge 0$."

I don't understand this sentence. How is the weak duality result being applied? I can see that $Ax = b, x \ge 0$ matches up with $Ax \ge b, x \ge 0$, but I don't see where $b'u \ge 0$ comes from. I would think that the only thing you could conclude from Theorem 4.4.1 is that $b'u \le 0$ since p = 0 in that problem.

Thanks in advance.

Proof of Farkas Lemma

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

From weak duality, we know that the dual objective evaluated at $u$ is less than or equal to the primal objective evaluated at $x$. But then we can also consider the "dual of the dual" (i.e. the primal). So we can consider the primal problem to be the dual problem and the dual problem to be the primal problem. So $bu' \geq 0x = 0$ but we know that $bu' <0$ from (ii). Hence both inequalities cannot hold. In other words, if $\textbf{x}$ is feasible for the primal and $\textbf{y}$ is feasible for the dual, then the objective function of the primal evaluated at $\textbf{x}$ is less than or equal to the objective function of the dual evaluated at $\textbf{y}$. So to sum up, the weak duality theorem really has two forms:

  • If the primal is a minimization problem and $\textbf{x}$ is feasible, then the dual is a maximization problem (and suppose $\textbf{y}$ is feasible for the dual). So from weak duality, the primal evaluated at $\textbf{x}$ will be greater than or equal to the dual evaluated at $\textbf{y}$.

  • If the primal is a maximization problem and $\textbf{x}$ is feasible then the dual is a minimization problem(and suppose $\textbf{y}$ is feasible for the dual). So from weak duality, the primal evaluated at $\textbf{x}$ will be less than or equal to the dual evaluated at $\textbf{y}$.

In this case, the primal is a maximization problem and the dual is a minimization problem. So the second case holds and hence the result.

share|improve this answer
    
Thank you, that is very helpful! –  Matt Gregory Mar 27 '11 at 8:59
add comment

Your Answer

 
discard

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.