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

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

1. (a)

$x\in K$.

2. (b)

If $\phi\in X^{\prime}$$\phi(y)\geq 0$ for all $y\in K$, then $\phi(x)\geq 0$.

3. (c)

$\phi(x)\geq 0$ for all $\phi\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^{\prime}$ be a subspace of linear functionals on $X$ that separate points. Impose on $X^{\prime}$ the weak-* topology generated by $X$.

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

1. (a)

$f\in K$.

2. (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^{\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^{\prime}$ and $Y^{\prime}$ that separate points. Have $X^{\prime}$ and $Y^{\prime}$ generate the weak topology for $X$ and $Y$ respectively.

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

1. (a)

$Tx=y$ has a solution $x\in K$.

2. (b)

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

3. (c)

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

Here $T^{*}\colon Y^{\prime}\to X^{\prime}$ denotes the pullback, restricted to $Y^{\prime}$ and $X^{\prime}$, defined by $T^{*}\psi=\psi\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). ∎

## References

• 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.
 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