A locally polynomial method for solving a system of linear inequalities

• Autorzy: Evtushenko Yuri , Szkatuła Krzysztof , Tretyakov Alexey
• Języki publikacji: EN

Abstrakty

EN

The paper proposes a method for solving systems of linear inequalities. This method determines in a finite number of iterations whether the given system of linear ineqalities has a solution. If it does, the solution for the given system of linear inequalities is provided. The computational complexity of the proposed method is locally polynomial.

Słowa kluczowe

EN

linear programming; system of linear inequalities; computational complexity; locally-polynomial algorithm; convergence rate

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2021
• Tom: Vol. 50, No. 2
• Strony: 301--314
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Evtushenko Yuri

• Dorodnicyn Computing Centre of FRC CSC, Russian Academy of Sciences, Vavilov st. 40, 119333 Moscow, Russia

autor

Szkatuła Krzysztof

• Siedlce University of Natural Sciences and Humanities, Faculty of Science, ul. Konarskiego 2, 08-110 Siedlce, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warszawa, Poland

autor

Tretyakov Alexey

• Siedlce University of Natural Sciences and Humanities, Faculty of Science, ul. Konarskiego 2, 08-110 Siedlce, Poland
• Systems Research Institute, Polish Academy of Sciences ul. Newelska 6, 01-447 Warszawa, Poland
• Dorodnicyn Computing Centre of FRC CSC, Russian Academy of Sciences, Vavilov st. 40, 119333 Moscow, Russia

Bibliografia

• Evtushenko, Y. G. and Golikov, A. (2003) New perspective on the theorems of alternative. In: High Performance Algorithms and Software for Nonlinear Optimization, Springer, 227–241.
• Facchinei, F., Fischer, A. and Kanzow, C. (1998) On the accurate identification of active constraints. SIAM Journal on Optimization, 9(1):14–32.
• Goffin, J.-L. (1982) On the non-polynomiality of the relaxation method for systems of linear inequalities. Mathematical Programming, 22(1):93–103.
• Golikov, A. and Evtushenko, Y. G. (2003) Theorems of the alternative and their applications in numerical methods. Computational Mathematics and Mathematical Physics, 43(3):338–358.
• Han, S.-P. (1980) Least-squares solution of linear inequalities. Technical report, University of Wisconsin – Madison, Mathematical Research Center. November 1980.
• Karmanov, V. G. (1989) Mathematical Programming. Mir Publishers, Moscow.
• Mangasarian, O. (2001) A finite Newton method for classification problems. Technical Report 01-11, Data Mining Institute, Computer Sciences Department, University of Wisconsin, Madison, Wisconsin.
• Nesterov, Y. (1984) One class of methods of unconditional minimization of a convex function, having a high rate of convergence. USSR Computational Mathematics and Mathematical Physics, 24(4):80–82.
• Poliak, B. (1987) Introduction to Optimization. Optimization Software, Inc., New York.
• Smale, S. (1998) Mathematical problems for the next century. The Mathematical Intelligencer, 20(2):7–15.
• Tretyakov, A. (2010) A finite-termination gradient projection method for solving systems of linear inequalities. Russian Journal of Numerical Analysis and Mathematical Modelling, 25(3):279–288.
• Tretyakov, A. and Tyrtyshnikov, E. (2013) A finite gradient-projective solver for a quadratic programming problem. Russian Journal of Numerical Analysis and Mathematical Modelling, 28(3):289–300.
• Tretyakov, A. and Tyrtyshnikov, E. (2015) Exact differentiable penalty for a problem of quadratic programming with the use of a gradient-projective method. Russian Journal of Numerical Analysis and Mathematical Modelling, 30(2):121–128.
• Wright, S. J. (2005) An algorithm for degenerate nonlinear programming with rapid local convergence. SIAM Journal on Optimization, 15(3):673–696.