# generalized Farkas lemma

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

###### Theorem 1.

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.

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.

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

 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