A New Proof of the Kuhn–Tucker and Farkas Theorems

Affiliation:
Dorodnitsyn Computing Centre, Federal Research Center “Computer Science and Control”, Russian Academy of Sciences
System Research Institute, Polish Academy of Sciences
Siedlce University
Address: Russian Federation

Journal name

Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki

Edition

Volume 58 Issue 7

Pages

1084-1088

Abstract

For the minimization problem for a differentiable function on a set defined by inequality constraints, a simple proof of the Kuhn–Tucker theorem in the Fritz John form is presented. Only an elementary property of the projection of a point onto a convex closed set is used. The approach proposed by the authors is applied to prove Farkas’ theorem. All results are extended to the case of Banach spaces.

Keywords

projection, Kuhn–Tucker theorem, convex hull, optimality conditions, local minimum

Received

08.08.2018

Publication date

11.10.2018

Number of characters

412

Cite Download pdf To download PDF you should sign in

GOST	Evtushenko Y., Tret’yakov A. A New Proof of the Kuhn–Tucker and Farkas Theorems // Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki – 2018. – V. 58. – Issue 7 C. 1084-1088 [Electronic resource]. URL: http://ras.jes.su/zvmmf/s004446690000372-0-1-en (circulation date: 25.04.2024). DOI: 10.31857/S004446690000372-0
MLA	Evtushenko, Yu, Tret’yakov, A. "A New Proof of the Kuhn–Tucker and Farkas Theorems." Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58.7 (2018):1084-1088. DOI: 10.31857/S004446690000372-0
APA	Evtushenko Y., Tret’yakov A. (2018). A New Proof of the Kuhn–Tucker and Farkas Theorems. Zhurnal vychislitelnoi matematiki i matematicheskoi fiziki 58(7), pp.1084-1088 DOI: 10.31857/S004446690000372-0

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной

Readers community rating: votes 0

1. Ostrogradski M. Considérations générales sur les momen(t)s des forces. [Obschie soobpazheniya o momentakh sil] //Mém. de l’Acad. des sc. de St.-Pbg. VI sér., sc. math. et phys. V. 1. 1835–1838. P. 129–150.

2. Ostpogpadskij M.V. Izbpannye tpudy. M.: Izd-vo AN SSSR, 1958. C. 129–150.

3. Prekopa A. On the development of optimization theory // The American Mathem. Monthly. 1980. V. 87. № 7. P. 527–542.

4. Kuhn H.W., Tucker A.W. Nonlinear programming. Proc. of the Second Berkeley Symposium on Math. Statistics and Probability. University of California Press, Berkeley, Calif., 1951. R. 481–492.

5. Mangasarian O.L. Nonlinear programming. Society for Industrial and Applied Mathematics, 1994.

6. Karmanov V.G. Matematicheskoe programmirovanie. M.: Nauka, 2000.

7. Alekseev V.M., Tikhomirov V.M., Fomin S.V. Optimal'noe upravlenie. M.: Fizmat. lit., 1979.

8. Brezhneva O., Tret’yakov A.A. An elementary proof of the Karush–Kuhn–Tucker theorem in normed linear spaces for problems with a finite number of inequality constraints //Optimizat. 2011. V. 60. № 5. P. 613–618.

9. Evtushenko Yu.G. Optimizatsiya i bystroe avtomaticheskoe differentsirovanie. M.: Nauchnoe izdanie VTs RAN, 2013.

10. Evtushenko Yu.G., Tret'yakov A.A. Approksimatsiya p-go poryadka mnozhestva reshenij nelinejnykh uravnenij // Zh. vychisl. matem. i matem. fiz. 2013. T. 53. № 12. S. 1951–1969.

11. Farkas J. Über die Theorie der einfachen Ungleichungen // J. Reine Angew, Math. 1902. № 124. R. 1–24.

12. Dax A. The relationship between theorems of the alternative, least norm problems, steepest descent directions, and degeneracy: A review // Annals of Operations Research. 1993. T. 46. № 1. S. 9–60.

13. Dax A. Classroom note: An elementary proof of Farkas’ lemma // SIAM Review. 1997. T. 39. № 3. S. 503–507.

14. Golikov A.I., Evtushenko Yu.G. Teoremy ob al'ternativakh i ikh primenenie v chislennykh metodakh // Zh. vychisl. matem. i matem. fiz. 2003. T. 43. № 3. S. 354–375.

15. Golikov A.I., Evtushenko Yu.G. Novyj klass teorem ob al'ternativakh // Tr. Instituta matematiki i mekhaniki UrO RAN. 2016. T. 22. № 3. S. 44–49.