Talk:Farkas' lemma

From Wikipedia, the free encyclopedia

Contents

[edit] English Translation

This theorem say that either b is a linear combination of the columns of A or there exists a y such that ATy has no negative components, and b^T \cdot y i is negative? —Preceding unsigned comment added by 24.62.5.177 (talk) 20:50, 28 May 2008 (UTC)

Well, the way I look at it is a little different. The equation Ax=b; x\succeq0 is the one we are interested in and can (usually) solve, the other equation identifies the pathological condition where the interesting equation has no solution.
To see what can go wrong consider the (special) one-row case. For example the "matrix" A could be [2 0 3] and the vector b could be [-1]. The problem is to find x\succeq0 such that Ax = b. The non-zero coefficients we have on the left hand side are positive (2 and 3), so when we take a positive linear combination 2 * x1 + 0 * x2 + 3 * x3 we will always end up with a positive number, so no matter how we choose the x's we will never be able to equal the right hand side, which is -1. Clearly the problem has no solution, because of what I would call a sign-incompatibility between A and b.
The Farkas Lemma tells us that this is true in the general case as well: "Either the equation Ax = b has a positive solution, or there is a linear combination of the rows (using y as the weights) that evidences a sign-incompatibility between the left and right side". So we have reduced the n row case to the 1 row case. ATy is a combination of the rows of A that gives a positive left hand side row; when we apply the same linear combination to the right hand side we get bty, if this is a negative number then (as in the previous example) the problem we are interested in has no solution. —Preceding unsigned comment added by Encyclops (talk • contribs) 01:56, 29 May 2008 (UTC)

[edit] Proof Bogus?

This proof just puts the "work" of proving Farkas's lemma one step back. The second line needs to be justified, and one of the traditional justifications goes via Farkas's lemma, which would certainly not be honest here.

Re: Farkas's or Farkas' --- Google Strunk and White s's

I sympathize with this point of view on the proof. This is certainly not the proof that we had when I was in school. Encyclops 22:35, 1 September 2007 (UTC)

[edit] Tautology

Dual cone does not require Farkas' lemma for its derivation. (See Rockafellar, Convex Analysis, ch.22, for example.) An option remains whether to derive the dual cone formula here. Its derivation appears in the citations. --Dattorro 10:33, 5 October 2007 (UTC)

[edit] spelling question

In English, words ending in S do not take 'S as a suffix, but just '. Shouldn't this therefore be Farkas' lemma? Encyclops 03:28, 16 January 2006 (UTC)

According to Apostrophe (mark)#Things to note, English is not that simple. -- Jitse Niesen (talk) 08:32, 16 January 2006 (UTC)

[edit] notation question

I'm uncertain about the notation used, particularly this line:

  • Ax=b\, for some x\geq 0; or

How does one determine if a vector is greater than zero? Or if that is the zero vector, then how does one do inequalities with vectors?

I believe \geq 0 applies componentwise, i.e. each element xi of the vector x is nonnegative. Encyclops 19:51, 12 August 2006 (UTC)

[edit] proof

the proof is unrederenced. per WP:NOR it cannot be in wikipeida article. wikipedia is not in a position to verify mathematical proofs. `'Míkka 22:09, 10 October 2007 (UTC)