УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2022-28-4-201-215
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2022, Vol. 319, Suppl. 1, pp. S242–S256. (Abstract)
Работа посвящена построению возможных аппроксимаций для несобственных задач выпуклого программирования на основе применения одного из классических подходов к регуляризации некорректных экстремальных задач — метода квазирешений В. К. Иванова. Если обычно ограничения исходной задачи в методе квазирешений агрегируются с помощью внешних штрафных функций, то в настоящей работе с этой целью используется одна из модификаций внутреннего штрафа, а именно, обобщенная обратная барьерная функция. Специфика задачи предопределяет введение в минимизируемую барьерную функцию ряда новых управляющих параметров. Наряду с коэффициентами штрафа и параметром регуляризации рассматриваются параметры, обеспечивающие корректность применения метода барьеров, прежде всего, наличие внутренних точек области определения метода. В работе обсуждаются вопросы существования решений возникающих задач коррекции, исследуется влияние параметров барьерной функции на сходимость предлагаемой модификации метода квазирешений для несобственных задач.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод квазирешений, методы барьерных функций
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. M.: Наука, 1983. 336 с.
2. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. M.: Наука, 1979. 288 с.
3. Васильев Ф.П. Методы оптимизации: кн. 1,2. МЦНМО, 2011. 1056 с.
4. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. M.: Наука, 1976. 196 с.
5. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.
6. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. M.: Наука, 1982. 432 с.
7. Эльстер К.-Х., Рейнгарт Р., Шойбле М., Донат Г. Введение в нелинейное программирование. М.: Наука, 1985. 264 с.
8. Gill P.E., Murray W., Sunders M.S., Tomlin J.A., Wright M.H. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projected methods // Math. Prog. 1986. Vol. 36, no. 2. P. 183–209. doi: 10.1007/BF02592025
9. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2008. T. 14, № 2. C. 115–128.
10. Попов Л.Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. T. 3. C. 3–11.
11. Скарин В.Д. О некоторых универсальных методах коррекции несобственных задач выпуклого программирования // Автоматика и телемеханика. 2012. T. 2. C. 99–110.
12. Попов Л.Д., Скарин В.Д. Лексикографическая регуляризация и двойственность для несобственных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 2015. T. 21, № 3. C. 279–291.
13. Skarin V. On parameter control of the residual method for the correction of improper problems // Discrete Optimization and Operations Research (DOOR 2016) / eds. Kochetov, Yu. et all. P. 441–451. (Lecture Notes in Computer Science; vol. 9869). doi: 10.1007/978-3-319-44914-2_35
14. Волков В.В., Ерохин В.И., Красников А.С., Разумов А.В., Хвостов М.Н. Минимальная по евклидовой норме матричная коррекция пары двойственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 2017. T. 57, № 11. C. 1788–1803.
doi: 10.7868/S0044466917110151
15. Муравьева О.В. Определение радиусов совместности и несовместности систем линейных уравнений и неравенств по матричной норме // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 6. C. 873–882. doi: 10.7868/S0044466918060029
16. Васильев Ф.П., Потапов М.М., Артемьева Л.А. Экстраградиентный метод коррекции противоречивых задач линейного программирования // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 12. C. 1992–1998. doi: 10.31857/S004446690003547-2
17. Golub G.N., Hansen P.C., O’Leary D.P. Tikhonov regularization and total least squares // SIAM J. Matrix Anal. Appl. 1999. Vol. 2, no. 1. P. 185–194. doi: 10.1137/S0895479897326432
18. Renaut R., Guo N. Efficient algorithms for solution of regularized total least squares // SIAM J. Matrix Anal. Appl. 2005. Vol. 26, no. 2. P. 457–476. doi: 10.1137/S0895479802419889
Поступила 2.08.2022
После доработки 25.08.2022
Принята к публикации 29.08.2022
Скарин Владимир Дмитриевич
д-р физ.-мат. наук
зав. сектором
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
e-mail: skavd@imm.uran.ru
Ссылка на статью: В.Д. Скарин. Метод квазирешений на основе барьерных функций в анализе несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 4. С. 201-215
English
V.D. Skarin. The method of quasi-solutions based on barrier functions in the analysis of improper convex programming problems
The paper is devoted to the construction of possible approximations for improper problems of convex programming based on the application of a classical approach to the regularization of ill-posed extremal problems, namely, V. K. Ivanov’s method of quasi-solutions. While usually the constraints of the original problem in the method of quasi-solutions are aggregated with the help of exterior penalty functions, in this paper we use for this purpose a generalized inverse barrier function, which is a modification of interior penalty. Due to the specifics of the problem, we introduce a number of new control parameters into the minimized barrier function. Along with the penalty coefficients and the regularization parameter, we consider parameters that ensure the correctness of the application of the barrier method, first of all, the presence of interior points of the domain of the method. We also discuss the existence of solutions to emerging correction problems and analyze the influence of the parameters of the barrier function on the convergence of the proposed modification of the method of quasi-solutions for improper problems.
Keywords: convex programming, improper problem, optimal correction, method of quasi-solutions, barrier function methods
Received August 2, 2022
Revised August 25, 2022
Accepted August 29, 2022
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, 2022, vol. 28, no. 4, pp. 201-215; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2022, Vol. 319, Suppl. 1, pp. S242–S256.
[References -> on the "English" button bottom right]
