L.D. Popov. Barriers and symmetric regularization of the Lagrange function in the analysis of improper linear programming problems ... P. 138-155

In this paper, the author continues his research on the modification and adaptation of classical methods of the central path in order to apply them to the analysis of improper problems of linear programming. In the new constructions presented in the paper, in contrast to those developed earlier, it becomes possible to apply second-order optimization methods. Moreover, there is no need to specify in advance the type of impropriety of the problem being solved. Convergence theorems for the constructed methods are given, a meaningful interpretation of the obtained generalized solution is provided, and the results of numerical experiments are presented.

Keywords: linear programming, improper problems, generalized solutions, barrier function method, regularization

Received January 26, 2023

Revised June 9, 2023

Accepted June 13, 2023

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

REFERENCES

1.   Eremin I.I. Duality for improper problems of linear and convex programming. Sov. Math. Dokl. 1981, vol. 23, pp. 62–66.

2.   Eremin I.I., Mazurov Vl.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow: Nauka Publ., 1983, 336 p.

3.   Eremin I.I. Protivorechivye modely optimal’nogo planirovaniya [Inconsistent models of optimal planning] Moscow: Nauka Publ., 1988, 160 p.

4.   Morozov V.A. Pseudo-solutions. USSR Comput. Math. Math. Physics, 1969, vol. 9, no. 6, pp. 196–203. doi: 10.1016/0041-5553(69)90136-0

5.   Kochikov I.V., Matvienko A.N., Yagola A.G. The generalized residual principle for the solution of inconsistent equations. Comput. Math. Math. Phys., 1984, vol. 24, no. 4, pp. 78–80. doi: 10.1016/0041-5553(84)90233-7

6.   Reseaches on improper optimization problems: sbornik nauchnykh statei. Yekaterinburg, Ural Branch of the Academy of Sciences USSR Publ., 1988, 78 p. (in Russian)

7.   Parametric optimizarion and approximating methods for improper mathematical programming problems: sbornik nauchnykh statei. Yekaterinburg, Ural Branch of the Academy of Sciences USSR Publ., 1985, 136 p. (in Russian)

8.   Skarin V.D. An approach to the analysis of improper problems of linear programming. USSR Comput. Math. Math. Phys., 1986, vol. 26, no. 2, pp. 73–79. doi: 10.1016/0041-5553(86)90011-X

9.   Nonregular duality in matematical programming: sbornik nauchnykh statei. Yekaterinburg, Ural Branch of the Academy of Sciences USSR Publ., 1990, 78 p. (in Russian)

10.   Skarin V.D. Barrier function method and correction algorithms for improper convex programming problems. Proc. Steklov Instit. Math. (Suppl.), 2008, vol. 263, no. 2, pp. S120–S134. doi: 10.1134/S0081543808060126

11.   Popov L.D. Search of generalized solutions to improper linear and convex programming problems using barrier functions. Izv. Irkut. Gos. Univ. Ser. Matematika, 2011, vol. 4, no. 2, pp. 134–146 (in Russian).

12.   Eremin I.I., Popov L.D. Interior penalty functions and duality in linear programming. Proc. Steklov Instit. Math. (Suppl.), 2013, vol. 283, no. 1, pp. 56–63 doi: 10.1134/S0081543813090058

13.   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

14.   Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Ser. Classics in Appl. Math., vol. 4, Philadelphia: SIAM, 1987, 226 p. ISBN: 0898712548 . Translated to Russian under the title Nelineinoe programmirovanie. Metody posledovatel’noi bezuslovnoi minimizatsii, Moscow: Mir Publ., 1972, 240 p.

15.   Eremin I.I., Astaf’ev N.N. Vvedenie v teoryu lineinogo i vypuklogo programmirovaniya [Introduction to linear and convex programming]. Moscow: Nauka Publ., 1976, 192 p.

16.   Rockafellar R.T. Convex analysis. Prinseton: Prinseton Univ. Press, 1970, 451 p. Translated to Russian under the title Vypukly Analiz, Moscow: Mir Publ., 1973, 472 p.

17.   Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. Chichester: John Wiley & Sons Ltd, 1997, 484 p.

Cite this article as: L.D. Popov. Barriers and symmetric regularization of the Lagrange function in the analysis of improper linear programming problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 138–155.