Email this article A new approach to the Farkas theorem of the alternative
- Authors: Evtushenko Y.G.1,2, Tret’yakov A.A.1,3,4, Tyrtyshnikov E.E.2,4,5
-
Affiliations:
- Dorodnicyn Computing Centre, Federal Research Center "Informatics and Management" of the Russian Academy of Sciences
- Lomonosov Moscow State University
- System Research Institute of the Polish Academy of Sciences
- Siedlce University of Natural Sciences and Humanities
- Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences
- Issue: Vol 485, No 6 (2019)
- Pages: 655-658
- Section: Mathematics
- URL: https://journals.eco-vector.com/0869-5652/article/view/14393
- DOI: https://doi.org/10.31857/S0869-56524856655-658
- ID: 14393
Cite item
Full Text
Abstract
The classical Farkas theorem of the alternative is considered, which is widely used in various areas of mathematics and has numerous proofs and formulations. An entirely new elementary proof of this theorem is proposed. It is based on the consideration of a functional that, under Farkas’ condition, is bounded below on the whole space and attains a minimum. The assertion of Farkas’ theorem that a vector belongs to a cone is equivalent to the fact that the gradient of this functional is zero at the minimizer.
About the authors
Yu. G. Evtushenko
Dorodnicyn Computing Centre, Federal Research Center "Informatics and Management" of the Russian Academy of Sciences; Lomonosov Moscow State University
Author for correspondence.
Email: evt@ccas.ru
Academician of the Russian Academy of Sciences
Russian Federation, 40, Vavilova street, Moscow, 119333; 1, Leninskie gory, Moscow, 119991A. A. Tret’yakov
Dorodnicyn Computing Centre, Federal Research Center "Informatics and Management" of the Russian Academy of Sciences; System Research Institute of the Polish Academy of Sciences; Siedlce University of Natural Sciences and Humanities
Email: tret@ap.siedlce.pl
Russian Federation, 40, Vavilova street, Moscow, 119333; 6, Newelska, Warsaw, Poland, 01-447; 2, Konarskiego, Siedlce, Poland, 08-110
E. E. Tyrtyshnikov
Lomonosov Moscow State University; Siedlce University of Natural Sciences and Humanities; Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences
Email: eugene.tyrtyshnikov@gmail.com
Academician of the Russian Academy of Sciences
Russian Federation, 1, Leninskie gory, Moscow, 119991; 2, Konarskiego, Siedlce, Poland, 08-110; 8, Gubkina street, Moscow, 119991References
- Артамонов В. А., Латышев В. Н. Линейная алгебра и выпуклая геометрия. М.: Факториал Пресс, 2004.
- Карманов В. Г. Математическое программирование. М.: Наука, 1986.
- Тыртышников Е. Е. Основы алгебры. М.: Физматлит, 2017.
- Bartl D. A Short Algebraic Proof of the Farkas Lemma // SIAM J. Optim. 2008. V. 19. № 1. P. 234-239.
- Broyden C. G. A Simple Algebraic Proof of Farkas’s Lemma and Related Theorems // Optim. Methods and Software. 1998. V. 8. № 3/4. P. 185-199.
- Chandru V., Lassez J. L. Qualitative Theorem Proving in Linear Constraints. In: Verification: Theory and Practice. B., Heidelberg: Springer, 2003. P. 395-406.
- Dax A. Classroom Note: An Elementary Proof of Farkas’ Lemma // SIAM Rev. 1997. V. 39. № 3. P. 503-507.
- Голиков А. И., Евтушенко Ю. Г. Теоремы об альтернативах и их применение в численных методах //ЖВМиМФ. 2003. Т. 43. № 3. С. 354-375.
- Jaćimoviс́ M. Farkas’ Lemma of Alternative // The Teaching Math. 2011. V. 25. № 27. P. 77-86.
- Marjanović M. M. An Iterative Method for Solving Polynomial Equations. In: Topology and Its Appl. Budva, 1972. P. 170-172.
- Roos C., Terlaky T. S. Note on a Paper of Broyden //Operations Res. Lett. 1999. V. 25. № 4. P. 183-186.
- Ziegler G. M. Lectures on Polytopes. B.: Springer-Verlag, 1995.
Supplementary files
