The search for admissible solutions by the interior point algorithms
Valerii Ivanovich Zorkal'tsev
L. A. Melentiev Energy Systems Institute, Siberian Branch of the Russian Academy of Sciences, Lermontova st., 130, Irkutsk, 664033, Russia
Keywords: метод внутренних точек, линейное программирование, ввод в область допустимых решений, interior point algorithm, linear programming, techniques of arriving at the feasible solutions region
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.
|
