generalized Farkas lemma

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.

0.1 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 $X$ be a real vector spaces, and $X^{\mathrm{\prime }}$ be a subspace of linear functionals on $X$ that separate points. Impose on $X$ the weak topology generated by $X^{\mathrm{\prime }}$.

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

1. $x\in K$.

2. If $\varphi \in X^{\prime }$ satisfies $\varphi (y)\ge 0$ for all $y\in K$, then $\varphi (x)\ge 0$.

3. $\varphi (x)\ge 0$ for all $\varphi \in K^{+}$ (anti-cone of $K$ with respect to $X^{\prime }$).

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 space switch roles.

Theorem 2.

Let $X$ be a real vector space, and $X^{\mathrm{\prime }}$ be a subspace of linear functionals on $X$ that separate points. Impose on $X^{\mathrm{\prime }}$ the weak-* topology generated by $X$.

Given a functional $f\mathrm{\in }{X}^{\mathrm{\prime }}$, and a weak-* closed convex cone $K\mathrm{\subseteq }{X}^{\mathrm{\prime }}$, the following are equivalent:

1. $f\in K$.

2. $\{x\in X:f(x)\ge 0\}\supseteq {\bigcap }_{\varphi \in K}\{x\in X:\varphi (x)\ge 0\}$.

Proof.

Make the substitutions $X\to X^{\prime }$, $X^{\prime }\to X$, $x\to f$ and $K\to K$ in Theorem 1. ∎

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 $X$ and $Y$ be real vector spaces, with corresponding spaces of linear functionals $X^{\mathrm{\prime }}$ and $Y^{\mathrm{\prime }}$ that separate points. Have $X^{\mathrm{\prime }}$ and $Y^{\mathrm{\prime }}$ generate the weak topology for $X$ and $Y$ respectively.

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

1. The linear equation $Tx=y$ has a solution $x\in K$.

2. If $\psi \in Y^{\prime }$ satisfies $\psi (Tx)\ge 0$ for all $x\in K$, then $\psi (y)\ge 0$.

3. If $\psi \in Y^{\prime }$ satisfies $T^{*}\psi \in K^{+}$ (anti-cone of $K$ with respect to $X^{\prime }$), then $\psi (y)\ge 0$.

Here $T^{\mathrm{*}}\mathrm{:}{Y}^{\mathrm{\prime }}\mathrm{\to }{X}^{\mathrm{\prime }}$ denotes the pullback, restricted to $Y^{\mathrm{\prime }}$ and $X^{\mathrm{\prime }}$, defined by $T^{\mathrm{*}}\mathit{}\psi \mathrm{=}\psi \mathrm{\circ }T$.

Proof.

Make the substitutions $X\to Y$, $X^{\prime }\to Y^{\prime }$, $x\to y$ and $K\to T(K)$ in Theorem 1. Condition (c) is a rephrasal of condition (b). ∎

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