УДК 519.658.4
MSC: 90C05, 90C51, 90C53
DOI: 10.21538/0134-4889-2025-31-3-215-232
Работа выполнена в рамках исследований, проводимых в Уральском математическом центре при финансовой поддержке Министерства науки и высшего образования Российской Федерации (номер соглашения 075-02-2025-1549).
В данной статье продолжено исследование штрафных функций композитного типа в применении к задачам линейного программирования. Термин “композитные” объясняется тем, что графики таких функций получаются операцией гладкой склейки разнотипных графиков ряда привычных функций внутреннего и внешнего штрафов, что позволяет сохранять положительные качества склеиваемых компонент и устранять их специфические недостатки. В частности, эти конструкции сохраняют высокие свойства гладкости, позволяющие использовать для их минимизации методы второго порядка, и в то же время оказываются применимыми не только к задачам, допустимые области которых имеют непустую внутренность, но и к некорректным (несобственным, противоречивым, плохо поставленным) задачам, вовсе не имеющим допустимых планов; для последних композитные функции способны находить их так называемые аппроксимационные решения. Автор предлагает строгую аксиоматику таких функций, расширяя тем самым их перечень, а также доказывает отвечающие новой аксиоматике теоремы сходимости метода.
Ключевые слова: линейное программирование, комбинированные методы, методы внешней точки, методы внутренней точки, несобственные задачи, обобщенные решения.
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И.И. Метод штрафов в выпуклом программировании // Докл. АН СССР. 1967. Т. 173, № 4. С. 748–751.
2. Зангвилл У.И. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973. 312 с.
3. Osborne M.R., Ryan D.M. On penalty function methods for nonlinear programming problems // J. Math. Anal, and Appl. 1970. T. 31, № 3. P. 559–579. https://doi.org/10.1016/0022-247X(70)90009-0
4. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.
5. Полак Э. Численые методы оптимизации. М.: Мир, 1974. 376 с.
6. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.
7. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука, 1978. 351 с.
8. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. 520 с.
9. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.
10. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. 384 с.
11. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
12. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.
13. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. М.: Наука, 1989. 400 с. (Серия "Экономико-математическая библиотека").
14. Скарин В.Д. Метод штрафных функций и регуляризация в анализе несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2018. Т. 24, № 3. С. 187–199. https://doi.org/10.21538/0134-4889-2018-24-3-187-199
15. Бирюков А.Г., Чернов А.В., Чернова Ю.Г., Шароватова Ю.И. Штрафные, барьерные, квазибарьерные функции и функции, обратные к ним // Интеллектуальные системы. Теория и приложения. 2018. Т. 22, № 4. С. 31–50.
16. Renegar J. A polynomial-time algorithm, based on Newton’s method, for linear programming // Mathematical Programming. 1988. Vol. 40. P. 59–93. https://doi.org/10.1007/BF01580724
17. Gonzaga C.C. Interior point algorithms for linear programming problems with inequality constraints // Mathematical Programming. 1991. Vol. 52. P. 209–225. https://doi.org/10.1007/BF01582888
18. Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. Chichester: John Wiley & Sons Ltd, 1997. 484 p.
19. Попов Л.Д. Барьеры и симметричная регуляризация функции Лагранжа при анализе несобственных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 138–155. 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 // Optimization and Applications: Proc. 15th Internat. Conf. (OPTIMA 2024) / eds. Nicholas Olenev, Yuri Evtushenko, Milojica Jaćimović, Michael Khachay, Vlasta Malkova. Cham: Springer, 2025. P. 43–57. (Ser. Lecture Notes in Computer Science; vol. 15218).
https://doi.org/10.1007/978-3-031-79119-2_4
21. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 509 с.
22. Kanzow C., Qi H., Qi L. On the minimum norm solution of linear program // J. Optimi. Theory Appl. 2003. Vol. 116. P. 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. P. 1–18. https://doi.org/10.1023/B:JOTA.0000026128.34294.77
Поступила 23.04.2025
После доработки 16.06.2025
Принята к публикации 23.06.2025
Попов Леонид Денисович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
профессор, Институт естественных наук и математики
Уральский федеральный университет им. Б.Н. Ельцина
г. Екатеринбург
e-mail: popld@imm.uran.ru
Ссылка на статью: Л.Д. Попов. О принципах построения и свойствах штрафных функций композитного типа (на примере задач линейного программирования) // Тр. Ин-та математики и механики УрО РАН. 2025. Т. 31, № 3. С. 215–232.
English
L.D. Popov. Principles of construction and properties of penalty functions of composite type (on the example of linear programming problems)
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
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.
[References -> on the "English" button bottom right]
