Farkas' lemma

From Wikimization

Farkas' lemma is a result used in the proof of the Karush-Kuhn-Tucker (KKT) theorem from nonlinear programming.

It states that if $LaTeX: \,A\,$ is a matrix and $LaTeX: \,b$ a vector, then exactly one of the following two systems has a solution:

$LaTeX: A^Ty\succeq0$ for some $LaTeX: y\,$ such that $LaTeX: b^Ty<0~~$

or in the alternative

$LaTeX: Ax=b\,$ for some $LaTeX: x\succeq0$

where the notation $LaTeX: x\succeq0$ means that all components of the vector $LaTeX: x$ are nonnegative.

The lemma was originally proved by Farkas in 1902. The above formulation is due to Albert W. Tucker in the 1950s.

It is an example of a theorem of the alternative; a theorem stating that of two systems, one or the other has a solution, but not both.

1 Proof
2 Geometrical Interpretation
3 References
4 Extended Farkas' lemma
- 4.1 notes
- 4.2 Proof of extended Farkas' lemma

Proof

(Dattorro, ch.2.13) Define a convex cone

$LaTeX: \mathcal{K}=\{y~|~A^Ty\succeq0\}\quad$

whose dual cone is

$LaTeX: \quad\mathcal{K}^*=\{A_{}x~|~x\succeq0\}$

From the definition of dual cone $LaTeX: \,\mathcal{K}^*\!=\{b~|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\}$ we get

$LaTeX: y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*$

rather,

$LaTeX: A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~|~x\succeq0\}$

Given some $LaTeX: {\displaystyle b}$ vector and $LaTeX: y\!\in\mathcal{K}~$ , then $LaTeX: {\displaystyle b^Ty\!<0}$ can only mean $LaTeX: b\notin\mathcal{K}^*$ .

An alternative system is therefore simply $LaTeX: b\in\mathcal{K}^*$ and so the stated result follows.

Geometrical Interpretation

Farkas' lemma simply states that either vector $LaTeX: \,b$ belongs to convex cone $LaTeX: \mathcal{K}^*$ or it does not.

When $LaTeX: b\notin\mathcal{K}^*$ , then there is a vector $LaTeX: \,y\!\in\mathcal{K}$ normal to a hyperplane separating point $LaTeX: \,b$ from cone $LaTeX: \mathcal{K}^*$ .

References

Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902.

http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006

Extended Farkas' lemma

For any closed convex cone $LaTeX: \mathcal{J}$ in the Hilbert space $LaTeX: (\mathbb{H},\langle\cdot,\cdot\rangle)$ (in particular we can have $LaTeX: \mathbb{H}=\mathbb{R}^n)$ , denote by $LaTeX: \mathcal{J}^\circ$ the polar cone of $LaTeX: \mathcal{J}.$

Let $LaTeX: \mathcal{K}$ be an arbitrary closed convex cone in $LaTeX: \mathbb{H}.$

Then, the extended Farkas' lemma asserts that $LaTeX: \mathcal{K}^{\circ\circ}=\mathcal{K}.$

Hence, denoting $LaTeX: \mathcal{L}=\mathcal{K}^\circ,$ it follows that $LaTeX: \mathcal{L}^\circ=\mathcal{K}.$

Therefore, the cones $LaTeX: \mathcal{K}$ and $LaTeX: \mathcal{L}$ are called mutually polar pair of cones.

notes

For definition of convex cone see in finite dimension see Convex cones, Wikimization.

For definition of polar cone see Moreau's theorem.

Proof of extended Farkas' lemma

(Sándor Zoltán Németh) Let $LaTeX: z\in\mathbb H$ be arbitrary. Then, by Moreau's theorem we have

$LaTeX: z=P_{\mathcal K}z+P_{\mathcal K^\circ}z$

and

$LaTeX: z=P_{\mathcal K^\circ}z+P_{\mathcal K^{\circ\circ}}z.$

Therefore,

$LaTeX: P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z=z-P_{\mathcal K^\circ}z.$

In particular, for any $LaTeX: z\in K$ we have $LaTeX: z=P_{\mathcal K}z=P_{\mathcal K^{\circ\circ}}z\in\mathcal K^{\circ\circ}.$ Hence, $LaTeX: \mathcal K \subset \mathcal K^{\circ\circ}.$ Similarly, for any $LaTeX: z\in K^{\circ\circ}$ we have $LaTeX: z=P_{\mathcal K^{\circ\circ}}z= P_{\mathcal K}z\in\mathcal K.$ Hence, $LaTeX: \mathcal K^{\circ\circ}\subset\mathcal K.$ Therefore, $LaTeX: \mathcal K^{\circ\circ}=\mathcal K.$