A new approach to the Farkas theorem of the alternative

Cover Page

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

Russian Federation, 40, Vavilova street, Moscow, 119333; 1, Leninskie gory, Moscow, 119991

Academician of the Russian Academy of Sciences

A. 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

Russian Federation, 1, Leninskie gory, Moscow, 119991; 2, Konarskiego, Siedlce, Poland, 08-110; 8, Gubkina street, Moscow, 119991

Academician of the Russian Academy of Sciences

References

  1. Артамонов В. А., Латышев В. Н. Линейная алгебра и выпуклая геометрия. М.: Факториал Пресс, 2004.
  2. Карманов В. Г. Математическое программирование. М.: Наука, 1986.
  3. Тыртышников Е. Е. Основы алгебры. М.: Физматлит, 2017.
  4. Bartl D. A Short Algebraic Proof of the Farkas Lemma // SIAM J. Optim. 2008. V. 19. № 1. P. 234-239.
  5. 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.
  6. Chandru V., Lassez J. L. Qualitative Theorem Proving in Linear Constraints. In: Verification: Theory and Practice. B., Heidelberg: Springer, 2003. P. 395-406.
  7. Dax A. Classroom Note: An Elementary Proof of Farkas’ Lemma // SIAM Rev. 1997. V. 39. № 3. P. 503-507.
  8. Голиков А. И., Евтушенко Ю. Г. Теоремы об альтернативах и их применение в численных методах //ЖВМиМФ. 2003. Т. 43. № 3. С. 354-375.
  9. Jaćimoviс́ M. Farkas’ Lemma of Alternative // The Teaching Math. 2011. V. 25. № 27. P. 77-86.
  10. Marjanović M. M. An Iterative Method for Solving Polynomial Equations. In: Topology and Its Appl. Budva, 1972. P. 170-172.
  11. Roos C., Terlaky T. S. Note on a Paper of Broyden //Operations Res. Lett. 1999. V. 25. № 4. P. 183-186.
  12. Ziegler G. M. Lectures on Polytopes. B.: Springer-Verlag, 1995.

Statistics

Views

Abstract - 308

PDF (Russian) - 248

PlumX


Copyright (c) 2019 Russian academy of sciences

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies