Abstract:
A family of interior point algorithms for the linear programming problems is considered. In these algorithms, the entering into the domain of admissible solution of the original problem is represented as optimization process of the extended problem. This extension is realized by adding just one new variable. The main objective of the paper is to give a theoretical justification of the proposed procedure of entering into the feasible domain of the original problem, under the assumption of non-degeneracy of the extended problem. Particularly, we prove that given the constraints of the original problem being consistent, the procedure leads to a relative interior point of the feasible solutions domain.
Key words:
interior point algorithm, linear programming, techniques of arriving at the feasible solutions region.
Citation:
V. I. Zorkaltsev, “The search for admissible solutions by the interior point algorithms”, Sib. Zh. Vychisl. Mat., 19:3 (2016), 249–265; Num. Anal. Appl., 9:3 (2016), 191–206