Farkas' lemma (original) (raw)
Farkasova věta, někdy též Farkasovo lemma, vypovídá o řešitelnosti konečné soustavy lineárních rovnic, případně nerovnic, existuje několik modifikací. Věta je jedním z důsledků silné věty o dualitě v lineárním programování. Jako první tuto větu dokázal maďarský matematik Gyula Farkas v roce 1902.
| Property | Value |
|---|---|
| dbo:abstract | Farkasova věta, někdy též Farkasovo lemma, vypovídá o řešitelnosti konečné soustavy lineárních rovnic, případně nerovnic, existuje několik modifikací. Věta je jedním z důsledků silné věty o dualitě v lineárním programování. Jako první tuto větu dokázal maďarský matematik Gyula Farkas v roce 1902. (cs) Das Lemma von Farkas ist ein mathematischer Hilfssatz (Lemma). Er wurde 1902 von Julius Farkas aus Klausenburg (damals Österreich-Ungarn, heute Rumänien) als „Grundsatz der einfachen Ungleichungen“ veröffentlicht. Als eine der ersten Aussagen über Dualität erlangte dieses Lemma große Bedeutung für die Entwicklung der linearen Optimierung und die Spieltheorie. Das Lemma von Farkas kann verwendet werden, um den starken Dualitätssatz der linearen Optimierung und den Satz von Kuhn-Tucker zu beweisen. Es dient weiter dazu, finanztheoretische Arbitrageprobleme zu behandeln. (de) Farkas' lemma is a solvability theorem for a finite system of linear inequalities in mathematics. It was originally proven by the Hungarian mathematician Gyula Farkas.Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization (alternatively, mathematical programming). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming.Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements. Generalizations of the Farkas' lemma are about the solvability theorem for convex inequalities, i.e., infinite system of linear inequalities. Farkas' lemma belongs to a class of statements called "theorems of the alternative": a theorem stating that exactly one of two systems has a solution. (en) Le lemme de Farkas est un résultat d'analyse convexe (une branche des mathématiques) qui s'exprime et s'interprète de multiples manières. Sous une forme assez générale, il donne une expression duale de l'adhérence de l'image d'un cône convexe par une application linéaire : où est l'adjointe de et désigne le cône dual d'une partie .Lorsque est fermé, on obtient ainsi des conditions nécessaires et suffisantes pour qu'un système d'équations linéaires (ou affines) ait une solution dans . Sous la forme ci-dessus, le lemme de Farkas généralise la relation bien connue d'algèbre linéaire reliant l'image d'une application linéaire entre deux espaces euclidiens et le noyau de , à savoir Certaines versions du lemme sont connues sous le nom de « théorèmes de l'alternative » et s'obtiennent en prenant pour cône l'orthant positif de . Ceux-ci expriment l'équivalence (ou l'incompatibilité) entre la satisfaction de différents systèmes d'inéquations linéaires (ou affines). Du fait de sa généralité, le lemme de Farkas intervient dans de nombreux domaines, lorsque des questions de dualité sont en jeu. Citons l'optimisation non linéaire dans laquelle il permet d'obtenir une expression analytique de l'optimalité (les conditions de Karush, Kuhn et Tucker) à partir d'une expression géométrique de celle-ci, et la théorie des jeux. (fr) 수학적 최적화에서 퍼르커시 보조정리(영어: Farkas’s lemma)는 어떤 볼록뿔과 이에 속하지 않는 벡터 사이를 초평면으로 분리할 수 있다는 정리다. (ko) Lemat Farkasa, alternatywa Farkasa – twierdzenie z algebry liniowej, według którego w przestrzeni albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną. (pl) Лемма Фаркаша — утверждение о свойствах линейных неравенств.Была сформулирована и доказана в 1902 году.Применяется в геометрическом программировании. (ru) Лема Фаркаша — твердження опуклої геометрії, що широко використовується в теорії оптимізації, зокрема при розгляді двоїстих задач лінійного програмування і доведення теореми Каруша — Куна — Такера в нелінійному програмуванні. Лема Фаркаша є однією з так званих теорем альтернативності, що стверджують про існування розв'язку однієї і тільки однієї з деяких двох систем лінійних рівнянь і нерівностей (uk) |
| dbo:wikiPageExternalLink | https://books.google.com/books%3Fid=zfaUBDY33XkC&pg=PA19 https://link.springer.com/article/10.1007/s11202-010-0010-y |
| dbo:wikiPageID | 2480226 (xsd:integer) |
| dbo:wikiPageLength | 16880 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1117677929 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Minimax_theorem dbr:Bell's_theorem dbr:Cone_(linear_algebra) dbr:Convex_optimization dbr:Mathematical_optimization dbr:Convex_cone dbr:Local_hidden-variable_theory dbr:Closed_set dbr:Completeness_(logic) dbr:Dual_linear_program dbr:Karush–Kuhn–Tucker_conditions dbr:Linear_programming dbr:Fourier–Motzkin_elimination dbr:Lemma_(mathematics) dbr:Mathematical_programming dbr:Gyula_Farkas_(natural_scientist) dbr:Hyperplane dbr:Hyperplane_separation_theorem dbc:Convex_analysis dbc:Linear_programming dbr:Fredholm_alternative dbc:Lemmas_in_linear_algebra dbr:Semen_Samsonovich_Kutateladze dbr:Slater's_condition dbr:Nonlinear_programming dbr:Dual_cone dbr:Linear_inequalities dbr:Karush–Kuhn–Tucker dbr:Gordan's_theorem |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Reflist dbt:Rp dbt:Math_theorem |
| dcterms:subject | dbc:Convex_analysis dbc:Linear_programming dbc:Lemmas_in_linear_algebra |
| gold:hypernym | dbr:Result |
| rdf:type | yago:WikicatLemmas yago:WikicatMathematicalTheorems yago:Abstraction100002137 yago:Communication100033020 yago:Lemma106751833 yago:Message106598915 yago:Proposition106750804 yago:Statement106722453 yago:Theorem106752293 |
| rdfs:comment | Farkasova věta, někdy též Farkasovo lemma, vypovídá o řešitelnosti konečné soustavy lineárních rovnic, případně nerovnic, existuje několik modifikací. Věta je jedním z důsledků silné věty o dualitě v lineárním programování. Jako první tuto větu dokázal maďarský matematik Gyula Farkas v roce 1902. (cs) Das Lemma von Farkas ist ein mathematischer Hilfssatz (Lemma). Er wurde 1902 von Julius Farkas aus Klausenburg (damals Österreich-Ungarn, heute Rumänien) als „Grundsatz der einfachen Ungleichungen“ veröffentlicht. Als eine der ersten Aussagen über Dualität erlangte dieses Lemma große Bedeutung für die Entwicklung der linearen Optimierung und die Spieltheorie. Das Lemma von Farkas kann verwendet werden, um den starken Dualitätssatz der linearen Optimierung und den Satz von Kuhn-Tucker zu beweisen. Es dient weiter dazu, finanztheoretische Arbitrageprobleme zu behandeln. (de) 수학적 최적화에서 퍼르커시 보조정리(영어: Farkas’s lemma)는 어떤 볼록뿔과 이에 속하지 않는 벡터 사이를 초평면으로 분리할 수 있다는 정리다. (ko) Lemat Farkasa, alternatywa Farkasa – twierdzenie z algebry liniowej, według którego w przestrzeni albo punkt należy do stożka, albo można go oddzielić od stożka płaszczyzną. (pl) Лемма Фаркаша — утверждение о свойствах линейных неравенств.Была сформулирована и доказана в 1902 году.Применяется в геометрическом программировании. (ru) Лема Фаркаша — твердження опуклої геометрії, що широко використовується в теорії оптимізації, зокрема при розгляді двоїстих задач лінійного програмування і доведення теореми Каруша — Куна — Такера в нелінійному програмуванні. Лема Фаркаша є однією з так званих теорем альтернативності, що стверджують про існування розв'язку однієї і тільки однієї з деяких двох систем лінійних рівнянь і нерівностей (uk) Farkas' lemma is a solvability theorem for a finite system of linear inequalities in mathematics. It was originally proven by the Hungarian mathematician Gyula Farkas.Farkas' lemma is the key result underpinning the linear programming duality and has played a central role in the development of mathematical optimization (alternatively, mathematical programming). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming.Remarkably, in the area of the foundations of quantum theory, the lemma also underlies the complete set of Bell inequalities in the form of necessary and sufficient conditions for the existence of a local hidden-variable theory, given data from any specific set of measurements. (en) Le lemme de Farkas est un résultat d'analyse convexe (une branche des mathématiques) qui s'exprime et s'interprète de multiples manières. Sous une forme assez générale, il donne une expression duale de l'adhérence de l'image d'un cône convexe par une application linéaire : Certaines versions du lemme sont connues sous le nom de « théorèmes de l'alternative » et s'obtiennent en prenant pour cône l'orthant positif de . Ceux-ci expriment l'équivalence (ou l'incompatibilité) entre la satisfaction de différents systèmes d'inéquations linéaires (ou affines). (fr) |
| rdfs:label | Farkasova věta (cs) Lemma von Farkas (de) Farkas' lemma (en) Lemme de Farkas (fr) 퍼르커시 보조정리 (ko) Lemat Farkasa (pl) Лемма Фаркаша (ru) Лема Фаркаша (uk) |
| owl:sameAs | freebase:Farkas' lemma yago-res:Farkas' lemma wikidata:Farkas' lemma dbpedia-cs:Farkas' lemma dbpedia-de:Farkas' lemma dbpedia-fr:Farkas' lemma dbpedia-hu:Farkas' lemma dbpedia-ko:Farkas' lemma dbpedia-pl:Farkas' lemma dbpedia-ru:Farkas' lemma dbpedia-uk:Farkas' lemma dbpedia-vi:Farkas' lemma https://global.dbpedia.org/id/4ni6P |
| prov:wasDerivedFrom | wikipedia-en:Farkas'_lemma?oldid=1117677929&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Farkas'_lemma |
| is dbo:knownFor of | dbr:Gyula_Farkas_(natural_scientist) |
| is dbo:wikiPageRedirects of | dbr:Farkas'_Lemma dbr:Farkas_lemma dbr:Generalized_Farkas'_lemma dbr:Farkas's_Lemma dbr:Farkas's_lemma dbr:Farkas_Lemma dbr:Farkas’_Lemma dbr:Lemma_(Farkas) dbr:Theorem_of_alternatives |
| is dbo:wikiPageWikiLink of | dbr:List_of_numerical_analysis_topics dbr:Convex_optimization dbr:Convex_cone dbr:1902_in_science dbr:Farkas'_Lemma dbr:Farkas_lemma dbr:Karush–Kuhn–Tucker_conditions dbr:Fourier–Motzkin_elimination dbr:Lemma_(mathematics) dbr:Gyula_Farkas_(natural_scientist) dbr:Sárosd dbr:Real_algebraic_geometry dbr:Fredholm_alternative dbr:R._Tyrrell_Rockafellar dbr:Generalized_Farkas'_lemma dbr:Farkas's_Lemma dbr:Farkas's_lemma dbr:Farkas_Lemma dbr:Farkas’_Lemma dbr:Lemma_(Farkas) dbr:Theorem_of_alternatives |
| is dbp:knownFor of | dbr:Gyula_Farkas_(natural_scientist) |
| is foaf:primaryTopic of | wikipedia-en:Farkas'_lemma |