L.D. Popov. Interior point methods adapted to infeasible linear programs ... P. 208-216

For linear programs, we consider schemes for the formation of a generalized central path, which arise under the simultaneous use of interior and exterior penalty terms in the traditional Lagrange function and the minimax problems generated by it. The advantage of the new schemes is that they do not require the a priori knowledge of feasible interior points in the primal or dual problem. Moreover, when applied to problems with inconsistent constraints, the schemes automatically lead to some of their generalized solutions, which have important applied content. Descriptions of the algorithms, their justification, and results of numerical experiments are presented.

Keywords: linear programming, duality, penalty function methods, regularization methods, infeasible problems, central path

Received August 24, 2018

Revised November 08, 2018

Accepted November 12, 2018

Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 16-07-00266).

Leonid Denisovich Popov, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: popld@imm.uran.ru


1.   Roos C., Terlaky T., Vial J.-Ph. Theory and Algorithms for Linear Optimization: An Interior Point Approach. N Y: Wiley, 1997, 454 p. ISBN: 0471956767 .

2.   Eremin I.I. Theory of linear optimization. Inverse and Ill-posed problems series. Utrecht; Boston; Koln; Tokyo: VSP, 2002, 248 p. ISBN: 906764353X .

3.   Eremin I.I., Mazurov V.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper Problems of Linear and Convex Programming]. Moscow: Nauka Publ., 1983, 336 p.

4.   Tikhonov A.N., Arsenin V.Ya. Methods for Solutions of Ill-Posed Problems. N Y: Wiley, 1977, 258 p. ISBN: 0470991240 . Original Russian text published in Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach. Moscow: Nauka Publ., 1979, 285 p.

5.   Vasil’ev F.P. Metody resheniya ekstremal’nykh zadach [Methods for solving extremal problems]. Moscow: Nauka Publ., 1981, 400 p.

6.   Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu linejnogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow: Nauka Publ., 1976, 191 p.

7.   Popov L.D. Use of barrier functions for optimal correction of improper problems of linear programming of the 1st kind. Autom. Remote Control, 2012, vol. 73, no. 3, pp. 417–424. doi: 10.1134/S0005117912030010

8.   Popov L.D. Dual approach to the application of barrier functions for the optimal correction of improper linear programming problems of the first kind. Proc. Steklov Inst. Math., 2015, vol. 288, suppl. 1, pp. 173–179. doi: 10.1134/S0081543815020170