generalized Farkas lemma

Farkas’ Lemma of convex optimizationand linear programming can be formulatedfor topological vector spaces.

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

The key insightis that the notion of linear inequalities ina finite number of real variablescan be generalized to abstract linear spacesby 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 linearfunctionals 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 propertyof the anti-cone, while condition (b) is merelya rephrasal of condition (c).∎

Theorem 2 is a version of Theorem 1 wherethe 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 definedby linear mappings; such linear mappings are the analogues to the matricesinvolved 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$, anda 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).∎