A locally polynomial method for solving a system of linear inequalities

Evtushenko, Yuri; Szkatuła, Krzysztof; Tretyakov, Alexey

doi:10.2478/candc-2021-0015

Abstract

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.

References

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.10.1007/978-1-4613-0241-4_10
Search in Google Scholar Back to article
Facchinei, F., Fischer, A. and Kanzow, C. (1998) On the accurate identification of active constraints. SIAM Journal on Optimization, 9(1):14–32.10.1137/S1052623496305882
Search in Google Scholar Back to article
Goffin, J-L. (1982) On the non-polynomiality of the relaxation method for systems of linear inequalities. Mathematical Programming, 22(1):93–103.10.1007/BF01581028
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
Han, S-P. (1980) Least-squares solution of linear inequalities. Technical report, University of Wisconsin – Madison, Mathematical Research Center. November 1980.
Search in Google Scholar Back to article
Karmanov, V. G. (1989) Mathematical Programming. Mir Publishers, Moscow.
Search in Google Scholar Back to article
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.
Search in Google Scholar Back to article
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.10.1016/0041-5553(84)90234-9
Search in Google Scholar Back to article
Poliak, B. (1987) Introduction to Optimization. Optimization Software, Inc., New York.
Search in Google Scholar Back to article
Smale, S. (1998) Mathematical problems for the next century. The Mathematical Intelligencer, 20(2):7–15.10.1007/BF03025291
Search in Google Scholar Back to article
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.10.1515/rjnamm.2010.018
Search in Google Scholar Back to article
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.10.1515/rnam-2013-0017
Search in Google Scholar Back to article
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.10.1515/rnam-2015-1013
Search in Google Scholar Back to article
Wright, S. J. (2005) An algorithm for degenerate nonlinear programming with rapid local convergence. SIAM Journal on Optimization, 15(3):673–696.10.1137/030601235
Search in Google Scholar Back to article

A locally polynomial method for solving a system of linear inequalities

Abstract

Paradigm

My account