УДК 519.658.4
MSC: 90C05, 90C51, 90C53
DOI: 10.21538/0134-4889-2022-28-4-191-200
Полный текст статьи (Full text)
Работа выполнена в рамках исследований, проводимых в Уральском математическом центре при финансовой поддержке Министерства науки и высшего образования Российской Федерации (номер соглашения 075-02-2022-874).
Приведены новые результаты по конструированию внешних штрафных функций повышенной гладкости в линейном программировании и по построению на их основе итерационных методов с автоматическим согласованием их параметров. Новые конструкции, подобно внутренним штрафным функциям, позволяют применять методы оптимизации второго порядка и в то же время не требуют знания хотя бы одной внутренней допустимой точки исходной задачи для своего старта. Более того, новые штрафные функции могут быть применены и к несобственным задачам линейного программирования (задачам с противоречивыми системами ограничений), для которых они способны вырабатывать обобщенные (компромиссные) решения. Приведены теоремы сходимости и данные численных экспериментов.
Ключевые слова: линейное программирование, несобственные задачи, обобщенные решения, метод штрафных функций, метод Ньютона
СПИСОК ЛИТЕРАТУРЫ
1. Данциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966. 600 с.
2. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.
3. Зангвилл У. И. Нелинейное программирование. Единый подход. М.: Сов. радио, 1973. 312 с.
4. Полак Э. Численые методы оптимизации. М.: Мир, 1974. 376 с.
5. Еремин И. И. Метод штрафов в выпуклом программировании // Докл. АН СССР. 1967. Т. 173, № 4. С. 748–751.
6. Моисеев Н. Н., Иванилов Ю. П., Столярова Е. М. Методы оптимизации. М.: Наука, 1978. 351 с.
7. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.
8. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985. 509 с.
9. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988. 552 с.
10. Roos C., Terlaky T., Vial J.-Ph. Theory and algorithms for linear optimization. Chichester: John Wiley & Sons Ltd, 1997. 484 p.
11. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // Докл. АН СССР. 1981. Т. 256, № 2. С. 272–276.
12. Еремин И. И., Мазуров Вл. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
13. Кочиков И. В., Матвиенко А. Н., Ягола А. Г. Обобщенный принцип невязки для решения несовместных уравнений // Журн. вычисл. математики и мат. физики. 1984. Т. 24, № 7. С. 1087–1090.
14. Попов Л. Д. Поиск обобщенных решений несобственных задач линейного и выпуклого программирования с помощью барьерных функций // Изв. Иркутского гос. ун-та. Сер. Математика. 2011. Т. 4, № 2. C. 134–146.
15. Попов Л. Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. Вып. 3. С. 3–11.
16. Попов Л. Д. Об одном приеме повышения гладкости внешних штрафных функций в линейном и выпуклом программировании // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 4. С. 88–101.
Поступила 19.07.2022
После доработки 21.09.2022
Принята к публикации 26.09.2022
Попов Леонид Денисович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
профессор, Институт математики и компьютерных наук
Уральский федеральный университет им. Б.Н. Ельцина
г. Екатеринбург
e-mail: popld@imm.uran.ru
Ссылка на статью: Л.Д. Попов. Об управлении параметрами в итерационных методах линейного программирования, основанных на новом классе гладких внешних штрафных функций // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 4. С. 191-200
English
L.D. Popov. On parameter control in iterative linear programming methods based on a new class of smooth exterior penalty functions
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
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
[References -> on the "English" button bottom right]
