L.D. Popov. On parameter control in iterative linear programming methods based on a new class of smooth exterior penalty functions ... P. 191-200

New results are presented on the construction of exterior penalty functions of increased smoothness in linear programming and on the construction of iterative methods on their basis with automatic matching of their parameters. New constructions, similarly to interior penalty functions, make it possible to use second-order optimization methods and at the same time do not require knowledge of at least one interior admissible point of the original problem for the start of the operation. Moreover, the new penalty functions can also be applied to improper linear programming problems (problems with inconsistent constraint systems), for which they can produce generalized (compromise) solutions. Convergence theorems are proved and data of numerical experiments are presented.

Keywords: linear programming, improper (ill-posed) problems, generalized solutions, penalty functions method, Newton method

Received July 19, 2022

Revised September 21, 2022

Accepted September 26, 2022

Funding Agency: The work was performed as part of research conducted in the Ural Mathematical Center with the financial support of the Ministry of Science and Higher Education of the Russian Federation (Agreement number 075-02-2022-874).

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


1.   Dantzig George B. Linear programming and extensions. Ser. Princeton Landmarks in Mathematics and Physics, Princeton: Princeton University Press, 1963, 656 p. Translated to Russian under the title Lineinoe programmirovanie, ego obobshcheniya i primeneniya, Moscow: Progress Publ., 1966, 600 p.

2.   Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Classics in applied mathematics, 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.

3.   Zangwill W.I. Nonlinear programming: a unified approach. Englewood Cliffs: Prentice-Hall, 1969, 356 p. ISBN: 0136235794 . Translated to Russian under the title Nelineinoe programmirovanie. Edinyi podkhod, Moscow: Sov. Radio Publ., 1973, 312 p.

4.   Polak E. Computational methods in optimization. NY: Acad. Press, 1971, 329 p. ISBN: 9780080960913 . Translated to Russian under the title Chislenye metody optimizatsii, Moscow: Mir Publ., 1974, 376 p.

5.   Eremin I.I. The “penalty” method in convex programming. Sov. Math., Dokl., 1967, vol. 8, pp. 459–462.

6.   Moiseev N.N., Ivanilov Yu.P., Stolyarova E.M. Metody optimizatsii [Optimization methods]. Moscow: Nauka Publ., 1978, 351 p.

7.   Evtushenko Yu.G. Metody resheniya ekstremal’nykh zadach i ikh primenenie v sistemakh optimizatsii [Methods for solving extremal problems and their application in optimization systems]. Moscow: Nauka Publ., 1982, 432 p.

8.   Gill P.E., Murray W., Wright M.H. Practical optimization. Philadelphia: SIAM, 2019, 401 p. doi: 10.1137/1.9781611975604 . Translated to Russian under the title Prakticheskaya optimizatsiya. Moscow: Mir Publ., 1985, 509 p.

9.   Vasilyev F.P. Chislennye metody resheniya ekstremal’nykh zadach [Numerical methods for solving extremal problems]. Moscow: Nauka Publ., 1988, 552 p. ISBN: 5-02-013796-0 .

10.   Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. NY: Wiley, 1997, 454 p. ISBN: 047195676 .

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

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

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

14.   Popov L.D. Search of generalized solutions to improper linear and convex programming problems using barrier functions. Bull. Irkutsk State Univ. Ser. Math., 2011, vol. 4, no. 2, pp. 134–146 (in Russian).

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

16.   Popov L.D. On one method of increasing the smoothness of external penalty functions in linear and convex programming. Trudy Inst. Mat. i Mekh. UrO RAN, 2021, vol. 27, no. 4, pp. 88–101 (in Russian). doi: 10.21538/0134-4889-2021-27-4-88-101 

Cite this article as: L.D. Popov. On parameter control in iterative linear programming methods based on a new class of smooth exterior penalty functions. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 4, pp. 191–200