УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2024-30-4-234-250
В работе рассматривается проблема построения аппроксимаций для широкого класса несобственных задач выпуклого программирования (НЗ ВП). Исходная задача с противоречивой системой ограничений погружается в параметрическое семейство разрешимых моделей ВП, где параметром служит норма невязки функций ограничений. Минимальное значение параметра, при котором допустимое множество задачи становится непустым, определяет оптимальную коррекцию НЗ ВП. Для решения задачи коррекции применяется один из классических методов регуляризации некорректных экстремальных задач — метод стабилизирующих функций (метод Тихонова). При этом исходная задача с ограничениями вначале сводится к проблеме безусловной минимизации некоторой штрафной функции. Вместо обычных функций внешнего штрафа в работе используется метод внутренних (барьерных) функций. Конструктивные особенности барьерных функций могут дать определенные преимущества при численной реализации метода коррекции. В статье формулируются условия разрешимости задач, возникающих на различных этапах предлагаемого метода коррекции, исследуются вопросы согласования параметров процесса, обеспечивающих требуемую сходимость. Подробно изучаются возможности метода при работе с возмущенными данными.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод регуляризации Тихонова, методы барьерных функций
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // Докл. АН СССР. 1981. T. 256, № 2. C. 272–276.
2. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
3. Еремин И.И. Противоречивые модели оптимального планирования. М.: Наука, 1988. 160 с.
4. Кочиков И.В., Матвиенко А.Н., Ягола А.Г. Обобщенный принцип невязки для решения несовместных уравнений // Журн. вычисл. математики и мат. физики. 1984. Т. 24, № 7. С. 1087–1090.
5. Параметрическая оптимизация и методы аппроксимации несобственных задач математического программирования. Сб. науч. статей. Свердловск: Изд-во УНЦ АН СССР, 1985. 136 с.
6. Скарин В.Д. Об одном подходе к анализу несобственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 1986. Т. 26, № 3. C. 439–448.
7. Попов Л.Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. № 3. C. 3–11.
8. Волков В.В., Ерохин В.И., Красников А.С., Разумов А.В., Хвостов М.Н. Минимальная по евклидовой норме матричная коррекция пары двойственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 2017. T. 57, № 11. C. 1788–1803.
9. Васильев Ф.П., Потапов М.М., Артемьева Л.А. Экстраградиентный метод коррекции противоречивых задач линейного программирования // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 12. C. 1992–1998.
10. Dax A. The smallest correction of an inconsistent system of linear inequalities // Optimization and Engineering. 2001. Vol. 2. P. 349–359.
11. Renaut R.A., Guo N. Efficient algorithms for solution of regularized total least squares // SIAM J. Matrix Anal. Appl. 2005. Vol. 26, № 2. P. 457–476.
12. Мазуров Вл.Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. 248 с.
13. Хачай М.Ю. Об оценке числа членов минимального комитета системы линейных неравенств. Журн. вычислительной математики и мат. физики. 1997. T. 37, № 11. C. 1399–1404.
14. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. M.: Наука, 1979. 288 с.
15. Васильев Ф. П. Методы оптимизации: Кн. 1, 2. Изд-во МЦНМО, 2011. 1056 с.
16. Golub G.N., Hansen P.C., O’Leary D.P. Tikhonov regularization and total least squares // SIAM J. Matrix Anal. Appl. 1999. Vol. 21, no. 1. P. 185–194.
17. Скарин В.Д. О некоторых универсальных методах коррекции несобственных задач выпуклого программирования // Автоматика и телемеханика. 2012. № 2. C. 99–110.
18. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.
19. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. M.: Наука, 1976. 196 с.
20. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.
21. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2008. T. 14, № 2. C. 115–128.
22. Попов Л.Д. Поиск обобщенных решений несобственных задач линейного и выпуклого программирования с помощью барьерных функций // Изв. Иркутского гос. ун-та. Сер. Математика. 2011. Т. 4, № 2. C. 134–146.
23. Эльстер К.-Х., Рейнгарт Р., Шойбле М., Донат Г. Введение в нелинейное программирование. М.: Наука, 1985. 264 с.
Поступила 8.07.2024
После доработки 5.08.2024
Принята к публикации 12.08.2024
Скарин Владимир Дмитриевич
д-р физ.-мат. наук, зав. сектором
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: skavd@imm.uran.ru
Ссылка на статью: В.Д. Скарин. О регуляризованном методе барьерных функций в анализе несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2024. Т. 30, № 4. С. 234-250
English
V.D. Skarin. On the regularized method of barrier functions in the analysis of improper convex programs
The paper considers the problem of constructing approximations for a wide class of improper convex programs (ICPs). The original problem with an inconsistent system of constraints is immersed in a parametric family of feasible convex programming models, where the norm of the discrepancy of the constraint functions serves as a parameter. The minimum value of the parameter at which the feasible set of the problem becomes nonempty determines an optimal correction of the ICP. To solve the correction problem, one of the classical methods of regularization of ill-posed extremal problems is used — the method of stabilizing functions (Tikhonov’s method). In this case, the original problem with constraints is initially reduced to the problem of unconstrained minimization of a certain penalty function. Instead of conventional external penalty functions, the paper uses the method of internal (barrier) functions. The design features of barrier functions can provide certain advantages in the numerical implementation of the correction method. Conditions for the solvability of problems arising at various stages of the proposed correction method are formulated, and the issues of matching the process parameters that ensure the required convergence are studied. The capabilities of the method when working with perturbed data are analyzed.
Keywords: convex programming, improper problem, optimal correction, Tikhonov regularization method, barrier function methods
Received July 8, 2024
Revised August 5, 2024
Accepted August 12, 2024
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: skavd@imm.uran.ru
Cite this article as: V.D. Skarin. The method of quasi-solutions based on barrier functions in the analysis of improper convex programming problems. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2024, vol. 30, no. 4, pp. 234–250.
[References -> on the "English" button bottom right]
