Finite iteration method for evaluation of interior point of algebraic polyhedron and bound for step number
We are interested in a system of strict inequalities \[ Ax<b. \tag{1} \] System (1) is consistent if and only if the following homogeneous system \[ Ax<bt, \quad -t<0, \tag{2} \] is consistent, which, in turn, is equivalent to consistency of the system \[ Ax\leq bt-\gamma, \quad -t\leq- \gamma \tag{3} \] with arbitrary \(\gamma>0\). Easy reduction of the problem of solution's evaluation of the strict system (1) to solving system (3) for any \(\gamma>0\) enables us to apply the Fejér process for construction of finite-step methods for solving system (1) and estimation of the step number. The general idea of the methods under consideration is as follows. If we apply the method of Fejér approximations to system (3), then its iteration sequence \(\{[x_k,t_k]\}\), converges to a certain solution \([\widetilde x,\widetilde t]\) of system (3). Consequently, beginning from some \(k=N\), the vector \([x_k,t_k]\) satisfies system (2), and \(x_k/t_k\) system (1), i.e., for system (1) this process is finite. This scheme contains also some methods of linear correction.
- scientific article; zbMATH DE number 3908176
- Solution of systems of equalities and inequalities by the method of interior points
- Methods for solving systems of linear and convex inequalities based on the Fejér principle
- scientific article; zbMATH DE number 3844949
- A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
This page was built for publication: Finite iteration method for evaluation of interior point of algebraic polyhedron and bound for step number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1380190)
