generalized Farkas lemma


Farkas’ Lemma of convex optimization and linear programming can be formulated for topological vector spacesMathworldPlanetmath.

The more abstract version of Farkas’ Lemma is useful for understanding the essence of the usual version of the lemma proven for matrices, and of course, for solving optimization problems in infinite-dimensional spaces.

The key insight is that the notion of linear inequalities in a finite number of real variables can be generalized to abstract linear spaces by the concept of a cone.

0.1 Formal statements

Farkas’ Lemma may be stated in the several equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath ways. Theorem 1 is conceptually the simplest, but Theorem 2 and 3 are more convenient for applications.

Theorem 1.

Let X be a real vector spaces, and X be a subspacePlanetmathPlanetmath of linear functionalsMathworldPlanetmathPlanetmath on X that separate points. Impose on X the weak topology generated by X.

Given xX, and a weakly-closed convex cone KX, the following are equivalent:

  1. (a)

    xK.

  2. (b)

    If ϕX satisfies ϕ(y)0 for all yK, then ϕ(x)0.

  3. (c)

    ϕ(x)0 for all ϕK+ (anti-cone of K with respect to X).

Proof.

The equivalence of conditions (a) and (c) is a fundamental property of the anti-cone, while condition (b) is merely a rephrasal of condition (c). ∎

Theorem 2 is a version of Theorem 1 where the vector space and its dual spaceMathworldPlanetmathPlanetmathPlanetmath switch roles.

Theorem 2.

Let X be a real vector space, and X be a subspace of linear functionals on X that separate points. Impose on X the weak-* topology generated by X.

Given a functionalMathworldPlanetmathPlanetmath fX, and a weak-* closed convex cone KX, the following are equivalent:

  1. (a)

    fK.

  2. (b)

    {xX:f(x)0}ϕK{xX:ϕ(x)0}.

Proof.

Make the substitutions XX, XX, xf and KK in Theorem 1. ∎

Theorem 3 incorporates inequalitiesMathworldPlanetmath defined by linear mappings; such linear mappings are the analogues to the matrices involved in the finite-dimensional version of Farkas’ Lemma.

Theorem 3.

Let X and Y be real vector spaces, with corresponding spaces of linear functionals X and Y that separate points. Have X and Y generate the weak topology for X and Y respectively.

Given yY, a linear mapping T:XY, and a subset KX such that T(K) is a weakly-closed convex cone, the following are equivalent:

  1. (a)

    The linear equation Tx=y has a solution xK.

  2. (b)

    If ψY satisfies ψ(Tx)0 for all xK, then ψ(y)0.

  3. (c)

    If ψY satisfies T*ψK+ (anti-cone of K with respect to X), then ψ(y)0.

Here T*:YX denotes the pullback, restricted to Y and X, defined by T*ψ=ψT.

Proof.

Make the substitutions XY, XY, xy and KT(K) in Theorem 1. Condition (c) is a rephrasal of condition (b). ∎

References

  • 1 B. D. Craven and J. J. Kohila. “GeneralizationsPlanetmathPlanetmath of Farkas’ Theorem.” SIAM Journal on Mathematical Analysis. Vol. 8, No. 6, November 1977.
  • 2 David Kincaid and Ward Cheney. Numerical Analysis: Mathematics of Scientific Computing, third edition. Brooks/Cole, 2002.
Title generalized Farkas lemma
Canonical name GeneralizedFarkasLemma
Date of creation 2013-03-22 17:20:53
Last modified on 2013-03-22 17:20:53
Owner stevecheng (10074)
Last modified by stevecheng (10074)
Numerical id 7
Author stevecheng (10074)
Entry type Theorem
Classification msc 46A03
Classification msc 46A20
Classification msc 15A39
Classification msc 49J35
Synonym Farkas lemma for topological vector spaces
Synonym generalized Farkas theorem
Related topic AntiCone
Related topic Cone5