In this paper the author continues his research on the application of penalty functions of composite type for solving linear programming problems. The term “composite” is explained by the fact that the graphs of such functions are obtained by the operation of smooth gluing of different-type graphs of a number of usual functions of internal and external penalties. Such an operation allows one to preserve the positive qualities of the glued components and eliminate their specific shortcomings. In particular, these constructions preserve the smoothness properties, allowing the use of second-order methods for their minimization, and at the same time are applicable not only to problems whose admissible regions have a non-empty interior, but also to ill-posed (improper, contradictory, poorly posed) problems that do not have admissible plans at all; for the latter, composite functions are capable of finding their so-called approximation solutions. The author proposes a rigorous axiomatization of such functions, thus extending their list, and also proves convergence theorems corresponding to the new axiomatization of the method.
Keywords: linear programming, combinations of the methods, interior penalties, exterior penalties, improper programs, generalizes solutions.
Received April 23, 2025
Revised June 16, 2025
Accepted June 23, 2025
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-2025-1549).
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: e-mail: popld@imm.uran.ru
REFERENCES
1. Eremin I.I. The “penalty” method in convex programming. Sov. Math., Dokl., 1967, vol. 8, pp. 459–462.
2. Zangwill W. Nonlinear programming: a unified approach, Englewood Cliffs, Prentice-Hall, 1969, 356 p. ISBN: 978-0136235798 . Translated to Russian under the title Nelineinoe programmirovanie: edinyi podkhod, Moscow, Soviet Radio Publ., 1973, 312 p.
3. Osborne M.R., Ryan D.M. On penalty function methods for nonlinear programming problems. J. Math. Anal. Appl., 1970, vol. 31, no. 3, pp. 559–579. https://doi.org/10.1016/0022-247X(70)90009-0
4. Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Classics in applied mathematics, vol. 4. Philadelphia, SIAM, 1987, 226 p. https://doi.org/10.1137/1.9781611971316 . Translated to Russian under the title Nelineinoe programmirovanie. Metody posledovatel’noi bezuslovnoi minimizatsii. Moscow, Mir Publ., 1972, 240 p.
5. Polak E. Computational methods in optimization: a unified approach. Mathematics in Science and Engineering Ser., vol. 77. NY, London, Acad. Press, 1971, 329 p. ISBN-10: 0125593503 . Translated to Russian under the title Chislennyye metody optimizatsii: yedinyy podkhod. Moscow, Mir Publ., 1974, 376 p.
6. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow, Nauka Publ., 1976, 196 p.
7. Moiseev N.N., Ivanilov Yu.P., Stolarova E.M. Metody optimizacii [Optimization methods]. Moscow, Nauka Publ., 1978, 351 p.
8. Vasil’ev F.P. Metody resheniya ekstremal’nykh zadach [Methods for solving extremal problems]. Moscow, Nauka Publ., 1980, 520 p.
9. Evtushenko Yu.G. Numerical optimization techniques, NY, Springer-Verlag, 1985, 562 p. ISBN: 978-1-4612-9530-3 . Original Russian text published in Evtushenko Yu. G. Metody resheniya ekstremal nykh zadach i ikh primenenie v sistemakh optimizatsii, Moscow, Nauka Publ., 1982, 432 p.
10. Polyak B.T. Introduction to optimization. New York, Division Publ., 1987, 438 p. ISBN-10: 0911575146 . Original Russian text published in Polyak B. T. Vvedeniye v optimizatsiyu, Moscow, Nauka Publ., 1983, 384 p.
11. 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.
12. Eremin I.I. Protivorechivye modeli optimal’nogo planirovaniya [Contradictory models of optimal planning], Moscow, Nauka Publ., 1988, 160 p. ISBN: 5-02-013773-1 .
13. Golshtein E.G., Tret’yakov N.V. Modifitsirovannyye funktsii Lagranzha. Teoriya i metody optimizatsii [Modified Lagrange functions. Theory and methods of optimization]. Moscow, Nauka Publ., 1989, 400 p. ISBN: 5-02-013965-3 .
14. Skarin V.D. Penalty function method and regularization in the analysis of improper convex programs. Proc. Steklov Inst. Math., 2019, vol. 305, suppl. 1, pp. S166–S177. https://doi.org/10.1134/S0081543819040175
15. Birjukov A.G., Chernov A.V., Chernova Yu.G., Sharovatova Yu.I. Penalty, barrier, quasi-barrier functions and functions inverse to them. Intellektual’nyye sistemy. Teoriya i prilozheniya, 2018, vol. 22, no. 4, pp. 31–50 (in Rusian).
16. Renegar J. A polynomial-time algorithm, based on Newton’s method, for linear programming. Math. Programm., 1988, vol. 40, pp. 59–93. https://doi.org/10.1007/BF01580724
17. Gonzaga C.C. Interior point algorithms for linear programming problems with inequality constraints. Math. Programm., 1991, vol. 52, pp. 209–225. https://doi.org/10.1007/BF01582888
18. Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization: an interior point approach. Chichester, NY, Wiley, 1997, 482 p.
19. Popov L.D. Barriers and symmetric regularization of the lagrange function in the analysis of improper linear programming problems. Trudy Inst. Mat. Mekh. UrO RAN, 2023, vol. 29, no. 3, pp. 138–155 (in Russian). https://doi.org/10.21538/0134-4889-2023-29-3-138-155
20. Popov L.D. On the application of composite penalty functions obtained by “gluing” of external penalties with barrier ones in linear programming. In: Proc. 15th Inter. Conf. “Optimization and applications” (OPTIMA 2024), Ser. Lecture Notes in Comp. Sci., vol. 15218, Cham, Springer, 2025, pp. 43–57.
https://doi.org/10.1007/978-3-031-79119-2_4
21. Gill P., Murray W., Wright M. Practical optimization. London, NY, Toronto, Sydney, San Francisco, Academic Press, 1981, 401 p. Translated to Russian under the title Prakticheskaya optimizatsiya, Moscow, Mir Publ., 1985, 509 p.
22. Kanzow C., Qi H., Qi L. On the minimum norm solution of linear program. J. Optim. Theory Appl., 2003, vol. 116, pp. 333–345. https://doi.org/10.1023/A:1022457904979
23. Mangasarian O.L. A Newton method for linear programming. J. Optim. Theory Appl., 2004, vol. 121,
pp. 1–18. https://doi.org/10.1023/B:JOTA.0000026128.34294.77
Cite this article as: L.D. Popov. Principles of construction and properties of penalty functions of composite type (on the example of linear programming problems). Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 3, pp. 215–232.
