УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2023-29-3-168-184
Работа выполнена в рамках исследований, проводимых в Уральском математическом центре при финансовой поддержке Министерства науки и высшего образования Российской Федерации (номер соглашения 075-02-2023-913).
Полный текст статьи (Full text)
Работа продолжает исследования автора по построению возможных аппроксимаций для несобственных задач выпуклого программирования (НЗ ВП). В качестве базовой модели коррекции НЗ определена проблема минимизации целевой функции исходной задачи на множестве точек минимума чебышевской нормы невязки ограничений. Для этой постановки применяется один из классических методов регуляризации некорректных экстремальных задач — метод квазирешений. В основу данного метода положен переход к некоторой задаче безусловной минимизации путем агрегации функций ограничений исходной задачи. Для этой цели используется одна из модификаций метода штрафных функций, а именно метод обобщенной обратной барьерной функции. Такой подход представляется перспективным с точки зрения численной реализации метода квазирешений. В работе формулируются условия сходимости предлагаемого метода, в том числе в случае неточного задания исходных данных. При этом особое внимание уделяется определению величины оптимальной коррекции ограничений анализируемой НЗ ВП, а также нахождению оптимального значения параметра регуляризации в методе квазирешений.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод квазирешений, методы барьерных функций
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И.И. Двойственность для несобственных задач линейного и выпуклого программирования // Докл. АН СССР. 1981. T. 256, № 2. C. 272–276.
2. Еремин И.И., Мазуров Вл.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования. M.: Наука, 1983. 336 с.
3. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. M.: Наука, 1979. 288 с.
4. Васильев Ф.П. Методы оптимизации: кн. 1,2. МЦНМО, 2011. 1056 с.
5. 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
6. 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
7. Васильев Ф.П., Потапов М.М., Артемьева Л.А. Экстраградиентный метод коррекции противоречивых задач линейного программирования // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 12. C. 1992–1998. doi: 10.31857/S004446690003547-2
8. Фиакко А., Мак-Кормик Г. Нелинейное программирование. Методы последовательной безусловной минимизации. М.: Мир, 1972. 240 с.
9. Еремин И.И., Астафьев Н.Н. Введение в теорию линейного и выпуклого программирования. M.: Наука, 1976. 196 с.
10. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. M.: Наука, 1982. 432 с.
11. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990. 488 с.
12. Скарин В.Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2008. T. 14, № 2. C. 115–128.
13. Попов Л.Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. T. 3. C. 3–11.
14. Скарин В.Д. Метод квазирешений на основе барьерных функций в анализе несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2022. T. 28, № 4. C. 201–215.
Поступила 27.03.2023
После доработки 14.07.2023
Принята к публикации 21.07.2023
Скарин Владимир Дмитриевич
д-р физ.-мат. наук
зав. сектором
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
e-mail: skavd@imm.uran.ru
Ссылка на статью: В.Д. Скарин. Об оптимальной коррекции несобственных задач выпуклого программирования на основе метода квазирешений // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 168-184
English
V.D. Skarin. On the optimal correction of improper convex programming problems based on the method of quasi-solutions
The work continues the author’s research on the construction of possible approximations for improper problems of convex programming. The problem of minimizing the objective function of the original problem on the set of minimum points of the Chebyshev norm of the constraint discrepancy is defined as a basic model for correcting an improper problem. For this setting, one of the classical methods of regularization of ill-posed extremal problems is used, namely, the method of quasi-solutions. This method is based on the transition to a problem of unconstrained minimization by aggregation of the constraint function of the original problem. For this purpose, a modification of the penalty function method is used, namely, the generalized inverse barrier function method. This approach seems to be promising from the point of view of the numerical implementation of the quasi-solution method. Convergence conditions are formulated for the proposed method, including the case where the input data are given inaccurately. Special attention is paid to finding the value of optimal correction of the constraints in the improper problem of convex programming under study and to calculating the optimal value of the regularization parameter in the method of quasi-solutions.
Keywords: convex programming, improper problem, optimal correction, method of quasi-solutions, barrier function methods
Received March 27, 2023
Revised July 14, 2023
Accepted July 21, 2023
Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2023-913).
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, 2023, vol. 29, no. 3, pp. 168–184 .
[References -> on the "English" button bottom right]
