PlanetMath: generalized Farkas lemma

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (21)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

generalized Farkas lemma

(Theorem)

Farkas' Lemma of convex optimization and linear programming can be formulated for topological vector spaces.

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.

Formal statements

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

Theorem 1 Let be a real vector spaces, and be a subspace of linear functionals on that separate points. Impose on the weak topology generated by .

Given $x \in X$ , and a weakly-closed convex cone $K \subseteq X$ , the following are equivalent:

(a): $x \in K$ .
(b): If $\phi \in X'$ satisfies $\phi(y) \geq 0$ for all $y \in K$ , then $\phi(x) \geq 0$ .
(c): $\phi(x) \geq 0$ for all $\phi \in K^+$ (anti-cone of with respect to ).

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

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

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

Given a functional $f \in X'$ , and a weak-* closed convex cone $K \subseteq X'$ , the following are equivalent:

(a): $f \in K$ .
(b): $\{ x \in X\colon f(x) \geq 0\} \supseteq \bigcap_{\phi \in K} \{ x \in X \colon \phi(x) \geq 0 \}$ .

Proof. Make the substitutions $X \to X'$ , $X' \to X$ , $x \to f$ and $K \to K$ in Theorem 1. $\qedsymbol$

Theorem 3 incorporates inequalities 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 and be real vector spaces, with corresponding spaces of linear functionals and that separate points. Have and generate the weak topology for and respectively.

Given $y \in Y$ , a linear mapping $T\colon X \to Y$ , and a subset $K \subseteq X$ such that is a weakly-closed convex cone, the following are equivalent:

(a): The linear equation has a solution $x \in K$ .
(b): If $\psi \in Y'$ satisfies $\psi(Tx) \geq 0$ for all $x \in K$ , then $\psi(y) \geq 0$ .
(c): If $\psi \in Y'$ satisfies $T^* \psi \in K^+$ (anti-cone of with respect to ), then $\psi(y) \geq 0$ .

Here $T^* \colon Y' \to X'$ denotes the pullback, restricted to and , defined by $T^* \psi = \psi \circ T$ .

Proof. Make the substitutions $X \to Y$ , $X' \to Y'$ , $x \to y$ and $K \to T(K)$ in Theorem 1. Condition (c) is a rephrasal of condition (b). $\qedsymbol$

Bibliography

1: B. D. Craven and J. J. Kohila. ``Generalizations 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.

"generalized Farkas lemma" is owned by stevecheng.

(view preamble | get metadata)

See Also: anti-cone, cone

Other names:

Farkas lemma for topological vector spaces, generalized Farkas theorem

This object's parent.

Log in to rate this entry.
(view current ratings)

Cross-references: restricted, pullback, solution, linear equation, subset, generate, finite-dimensional, linear mappings, closed, functional, weak-* topology, dual space, property, equivalence, anti-cone, the following are equivalent, generated by, weak topology, points, linear functionals, subspace, applications, equivalent, cone, linear spaces, variables, real, number, finite, inequalities, infinite-dimensional, matrices, topological vector spaces, linear programming, convex, Farkas lemma

This is version 4 of generalized Farkas lemma, born on 2007-07-01, modified 2007-07-05.
Object id is 9705, canonical name is GeneralizedFarkasLemma.
Accessed 1457 times total.

Classification:

AMS MSC:	46A03 (Functional analysis :: Topological linear spaces and related structures :: General theory of locally convex spaces)
	46A20 (Functional analysis :: Topological linear spaces and related structures :: Duality theory)
	15A39 (Linear and multilinear algebra; matrix theory :: Linear inequalities)
	49J35 (Calculus of variations and optimal control; optimization :: Existence theories :: Minimax problems)

Pending Errata and Addenda

None.

Discussion

forum policy

No messages.

Interact