Farkas' lemma - Revision history

Ranjelin: /* Extended Farkas' lemma */

2026-05-14T00:13:06Z

Extended Farkas' lemma

←Older revision		Revision as of 00:13, 14 May 2026
Line 43:		Line 43:

	= Extended Farkas' lemma =		= Extended Farkas' lemma =
-	For any closed convex cone <math>\mathcal{J}</math> in the Hilbert space <math>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> (in particular we can have <math>\mathbb{H}=\mathbb{R}^n)</math>, denote by <math>\mathcal{J}^\circ</math> the polar cone of <math>\mathcal{J}.</math>	+	For any closed convex cone <math>\mathcal{J}</math> in the Hilbert space <math>(\mathbb{H},\,\langle\cdot,\cdot\rangle)\,</math> (in particular we can have <math>\mathbb{H}=\mathbb{R}^n)</math>, denote by <math>\mathcal{J}^\circ</math> the polar cone of <math>\mathcal{J}.</math>

	Let <math>\mathcal{K}</math> be an arbitrary closed convex cone in <math>\mathbb{H}.</math>		Let <math>\mathcal{K}</math> be an arbitrary closed convex cone in <math>\mathbb{H}.</math>

Ranjelin: /* Geometrical Interpretation */

2026-05-14T00:06:39Z

Geometrical Interpretation

←Older revision		Revision as of 00:06, 14 May 2026
Line 35:		Line 35:
	Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not.		Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not.

-	When <math>b\notin\mathcal{K}^*</math>, then there is a vector <math>\,y\!\in\mathcal{K}</math>	+	When <math>b\notin\mathcal{K}^*,\,</math> then there is a vector <math>\,y\!\in\mathcal{K}</math>
	normal to a hyperplane separating point <math>\,b</math> from cone <math>\mathcal{K}^*</math>.		normal to a hyperplane separating point <math>\,b</math> from cone <math>\mathcal{K}^*</math>.

Ranjelin: /* Proof */

2026-05-14T00:02:47Z

Proof

←Older revision		Revision as of 00:02, 14 May 2026
Line 19:		Line 19:

	From the definition of dual cone		From the definition of dual cone
-	<math>\,\mathcal{K}^*\!=\{b\;\|\;b^{\rm T}y\!\geq0\;\;\~~forall~~\;y\!\in\mathcal{K}\}</math> we get	+	<math>\,\mathcal{K}^*\!=\{b\;\|\;b^{\rm T}y\!\geq0\;\;{\rm for\;all}\;y\!\in\mathcal{K}\}</math> we get

-	<math>y\in\mathcal{K}\;\Leftrightarrow\;b^Ty\geq0\;\;\~~forall~~\;b\in\mathcal{K}^*</math>	+	<math>y\in\mathcal{K}\;\Leftrightarrow\;b^Ty\geq0\;\;{\rm for\;all}\;b\in\mathcal{K}^*</math>

	rather,		rather,

-	<math>A^Ty\succeq0\;\Leftrightarrow\;b^Ty\geq0\;\;\~~forall~~\;b\in\{A_{}x\;\|\;x\succeq0\}</math>	+	<math>A^Ty\succeq0\;\Leftrightarrow\;b^Ty\geq0\;\;{\rm for\;all}\;b\in\{A_{}x\;\|\;x\succeq0\}</math>

-	Given some <math>~~{\displaystyle~~ b}</math> vector and <math>y\!\in\mathcal{K}\;</math>, then <math>~~{\displaystyle~~ b^Ty\!<0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.	+	Given some <math>b</math> vector and <math>y\in\mathcal{K}\;,\;</math> then <math>b^Ty<0</math> can only mean <math>b\notin\mathcal{K}^*</math>.

	An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>		An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>

Ranjelin at 23:32, 6 May 2026

2026-05-06T23:32:24Z

←Older revision		Revision as of 23:32, 6 May 2026
Line 2:		Line 2:

	It states that if <math>\,A\,</math> is a matrix and <math>\,b</math> a vector, then exactly one of the following two systems has a solution:		It states that if <math>\,A\,</math> is a matrix and <math>\,b</math> a vector, then exactly one of the following two systems has a solution:
-	* <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0~~</math>	+	* <math>A^Ty\succeq0</math> for some <math>y\,</math> such that <math>b^Ty<0\;\;</math>
	or in the alternative		or in the alternative
	* <math>Ax=b\,</math> for some <math>x\succeq0</math>		* <math>Ax=b\,</math> for some <math>x\succeq0</math>
Line 14:		Line 14:

	'''('''[http://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' Define a convex cone		'''('''[http://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' Define a convex cone
-	* <math>\mathcal{K}=\{y~\|~A^Ty\succeq0\}\quad</math>	+	* <math>\mathcal{K}=\{y\;\|\;A^Ty\succeq0\}\quad</math>
	whose dual cone is		whose dual cone is
-	* <math>\quad\mathcal{K}^*=\{A_{}x~\|~x\succeq0\}</math>	+	* <math>\quad\mathcal{K}^*=\{A_{}x\;\|\;x\succeq0\}</math>

	From the definition of dual cone		From the definition of dual cone
-	<math>\,\mathcal{K}^*\!=\{b~\|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\}</math> we get	+	<math>\,\mathcal{K}^*\!=\{b\;\|\;b^{\rm T}y\!\geq0\;\;\forall\;y\!\in\mathcal{K}\}</math> we get

-	<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>	+	<math>y\in\mathcal{K}\;\Leftrightarrow\;b^Ty\geq0\;\;\forall\;b\in\mathcal{K}^*</math>

	rather,		rather,

-	<math>A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~\|~x\succeq0\}</math>	+	<math>A^Ty\succeq0\;\Leftrightarrow\;b^Ty\geq0\;\;\forall\;b\in\{A_{}x\;\|\;x\succeq0\}</math>

-	Given some <math>{\displaystyle b}</math> vector and <math>y\!\in\mathcal{K}~</math>, then <math>{\displaystyle b^Ty\!<0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.	+	Given some <math>{\displaystyle b}</math> vector and <math>y\!\in\mathcal{K}\;</math>, then <math>{\displaystyle b^Ty\!<0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.

	An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>		An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>

Ranjelin: /* References */

2016-09-28T21:50:59Z

References

←Older revision		Revision as of 21:50, 28 September 2016
Line 40:		Line 40:
	== References ==		== References ==
	* Gyula Farkas, Über die Theorie der Einfachen Ungleichungen, Journal für die Reine und Angewandte Mathematik, volume 124, pages 1–27, 1902.		* 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~~/no_cache~~/dms/load/img/?~~IDDOC~~=~~261361~~ http://gdz.sub.uni-goettingen.de~~/no_cache~~/dms/load/img/?~~IDDOC~~=~~261361~~]	+	[http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006 http://gdz.sub.uni-goettingen.de/dms/load/img/?PID=GDZPPN002165023&physid=PHYS_0006]
-		+

	= Extended Farkas' lemma =		= Extended Farkas' lemma =

Ranjelin: /* Geometrical Interpretation */

2011-12-05T05:20:10Z

Geometrical Interpretation

←Older revision		Revision as of 05:20, 5 December 2011
Line 35:		Line 35:
	Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not.		Farkas' lemma simply states that either vector <math>\,b</math> belongs to convex cone <math>\mathcal{K}^*</math> or it does not.

-	When <math>b\notin\mathcal{K}^*</math>, then there is a vector <math>\,y\!\in\!\mathcal{K}</math>	+	When <math>b\notin\mathcal{K}^*</math>, then there is a vector <math>\,y\!\in\mathcal{K}</math>
	normal to a hyperplane separating point <math>\,b</math> from cone <math>\mathcal{K}^*</math>.		normal to a hyperplane separating point <math>\,b</math> from cone <math>\mathcal{K}^*</math>.

Ranjelin: /* Proof */

2011-12-05T05:19:42Z

Proof

←Older revision		Revision as of 05:19, 5 December 2011
Line 19:		Line 19:

	From the definition of dual cone		From the definition of dual cone
-	<math>\,\mathcal{K}^*\!=\{b~\|~b^{\rm T}y\!\~~geq\!0~~~~\forall~y\!\~~in_{}\!~~\mathcal{K}\}</math> we get	+	<math>\,\mathcal{K}^*\!=\{b~\|~b^{\rm T}y\!\geq0~~\forall~y\!\in\mathcal{K}\}</math> we get

	<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>		<math>y\in\mathcal{K}~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\mathcal{K}^*</math>
Line 27:		Line 27:
	<math>A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~\|~x\succeq0\}</math>		<math>A^Ty\succeq0~\Leftrightarrow~b^Ty\geq0~~\forall~b\in\{A_{}x~\|~x\succeq0\}</math>

-	Given some <math>{\displaystyle b}</math> vector and <math>y\!\in\!\mathcal{K}~</math>, then <math>{\displaystyle b^Ty\!<\!0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.	+	Given some <math>{\displaystyle b}</math> vector and <math>y\!\in\mathcal{K}~</math>, then <math>{\displaystyle b^Ty\!<0}</math> can only mean <math>b\notin\mathcal{K}^*</math>.

	An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>		An alternative system is therefore simply <math>b\in\mathcal{K}^*</math>

Nemeth: /* Extended Farkas' lemma */

2011-11-19T09:04:00Z

Extended Farkas' lemma

←Older revision		Revision as of 09:04, 19 November 2011
Line 44:		Line 44:

	= Extended Farkas' lemma =		= Extended Farkas' lemma =
-	For any closed convex cone <math>\mathcal J</math> in the Hilbert space <math>(\mathbb H,\langle\cdot,\cdot\rangle)</math> ~~<math>~~(~~\,</math>~~in particular we can have <math>\mathbb H=\mathbb R^n)</math>, denote by <math>\mathcal J^\circ</math> the polar cone of <math>\mathcal J.</math>	+	For any closed convex cone <math>\mathcal{J}</math> in the Hilbert space <math>(\mathbb{H},\langle\cdot,\cdot\rangle)</math> (in particular we can have <math>\mathbb{H}=\mathbb{R}^n)</math>, denote by <math>\mathcal{J}^\circ</math> the polar cone of <math>\mathcal{J}.</math>

-	Let <math>\mathcal K</math> be an arbitrary closed convex cone in <math>\mathbb H.</math>	+	Let <math>\mathcal{K}</math> be an arbitrary closed convex cone in <math>\mathbb{H}.</math>

-	Then, the extended Farkas' lemma asserts that <math>\mathcal K^{\circ\circ}=\mathcal K.</math>	+	Then, the extended Farkas' lemma asserts that <math>\mathcal{K}^{\circ\circ}=\mathcal{K}.</math>

-	Hence, denoting <math>\mathcal L=\mathcal K^\circ,</math> it follows that <math>\mathcal L^\circ=\mathcal K.</math>	+	Hence, denoting <math>\mathcal{L}=\mathcal{K}^\circ,</math> it follows that <math>\mathcal{L}^\circ=\mathcal{K}.</math>

-	Therefore, the cones <math>\mathcal K</math> and <math>\mathcal L</math> are called ''mutually polar pair of cones''.	+	Therefore, the cones <math>\mathcal{K}</math> and <math>\mathcal{L}</math> are called ''mutually polar pair of cones''.

	=== notes ===		=== notes ===

Cslaw at 01:01, 30 May 2010

2010-05-30T01:01:43Z

←Older revision		Revision as of 01:01, 30 May 2010
Line 13:		Line 13:
	== Proof ==		== Proof ==

-	'''('''[~~https~~://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' Define a convex cone	+	'''('''[http://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' Define a convex cone
	* <math>\mathcal{K}=\{y~\|~A^Ty\succeq0\}\quad</math>		* <math>\mathcal{K}=\{y~\|~A^Ty\succeq0\}\quad</math>
	whose dual cone is		whose dual cone is

Cslaw at 00:59, 30 May 2010

2010-05-30T00:59:55Z

←Older revision		Revision as of 00:59, 30 May 2010
Line 13:		Line 13:
	== Proof ==		== Proof ==

-	'''('''Dattorro''')''' Define a convex cone	+	'''('''[https://ccrma.stanford.edu/~dattorro/mybook.html Dattorro, ch.2.13]''')''' Define a convex cone
	* <math>\mathcal{K}=\{y~\|~A^Ty\succeq0\}\quad</math>		* <math>\mathcal{K}=\{y~\|~A^Ty\succeq0\}\quad</math>
	whose dual cone is		whose dual cone is