УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2021-27-4-125-141
Полный текст статьи (Full text)
Работа выполнена при поддержке РФФИ (проект 19-07-01243).
Работа посвящена анализу некоторых “вырожденных” задач выпуклого программирования (несобственных, не имеющих решений в обычном смысле). Предлагается подход к коррекции подобных задач, основанный на применении идеологии стандартного в теории некорректных экстремальных задач метода квазирешений. Ограничения начальной проблемы агрегируются с помощью некоторой штрафной функции, которая в явном виде включается в схему метода квазирешений. При этом используются два наиболее распространенных варианта: точная штрафная функция и функция квадратичного штрафа. Для каждого варианта в условиях приближенного задания исходной информации об анализируемой проблеме исследуются вопросы разрешимости возникающих задач, устанавливаются оценки сходимости предлагаемых процедур.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод квазирешений, методы штрафных функций
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И. И., Мазуров Вл. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
2. Попов Л. Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. № 3. C. 3–11.
3. Волков В. В., Ерохин В. И., Красников А. С., Разумов А. В., Хвостов М. Н. Минимальная по евклидовой норме матричная коррекция пары двойственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 2017. T. 57, № 11. C. 1788–1803.
4. Муравьева О. В. Определение радиусов совместности и несовместности систем линейных уравнений и неравенств по матричной норме // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 6. C. 873–882.
5. Васильев Ф. П., Потапов М. М., Артемьева Л. А. Экстраградиентный метод коррекции противоречивых задач линейного программирования // Журн. вычисл. математики и мат. физики. 2018. T. 58, № 12. C. 1992–1998.
6. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. M.: Наука, 1979. 288 с.
7. Васильев Ф. П. Методы оптимизации: Кн. 1, 2. Изд-во МЦНМО, 2011. 1056 с.
8. Dax A. The smallest correction of an inconsistent system of linear inequalities // Optimization and Engineering. 2001. Vol. 2. P. 349–359.
9. Renaut R. A., Guo N. Efficient algorithms for solution of regularized total least squares // SIAM J. Matrix Anal. Appl. 2005. Vol. 26, no. 2. P. 457–476.
10. Skarin V. D. On parameter control of the residual method for the correction of improper problems // Discrete Optimization and Operations Research — 9th International Conf. (DOOR 2016): Proc. / eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos. P. 441–451. (Lecture Notes in Computer Science; vol. 9869). doi: 10.1007/978-3-319-44914-2_35
11. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. M.: Наука, 1976. 196 с.
12. Burke J. An exact penalization viewpoint of constrained optimization // SIAM J. Contr. Optim. 1991. Vol. 29, no. 4. P. 968–998.
13. Евтушенко Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации. М.: Наука, 1982. 432 с.
14. Скарин В. Д. О некоторых универсальных методах коррекции несобственных задач выпуклого программирования // Автоматика и телемеханика. 2012. № 2. C. 99–110.
Поступила 12.05.2021
После доработки 10.06.2021
Принята к публикации 21.06.2021
Скарин Владимир Дмитриевич
д-р физ.-мат. наук
зав. сектором
Институт математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: skavd@imm.uran.ru
Ссылка на статью: В.Д. Скарин. Метод квазирешений в анализе задач выпуклого программирования с особенностями // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 4. С. 125-141
English
V.D. Skarin. The quasisolution method in the analysis of convex programs with singularities
The paper is devoted to the analysis of some convex programs that are “degenerate” (improper, having no solutions in the usual sense). We propose an approach to the correction of such problems based on the ideas of the quasisolution method, which is standard in the theory of ill-posed extremal problems. The constraints of the original problem are aggregated with the use of a certain penalty function, which is explicitly included in the scheme of the quasisolution method. Two most popular variants are used: an exact penalty function and a quadratic penalty function. For each of these variants, the questions of solvability of the arising problems are studied and estimates for the convergence rate of the proposed procedures are established in the case where the input information about the problem to be analyzed is given approximately.
Keywords: convex programming, improper problem, optimal correction, quasisolution method, penalty function methods
Received May 12, 2021
Revised June 10, 2021
Accepted June 21, 2021
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-07-01243).
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 quasisolution method in the analysis of convex programs with singularities, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 4, pp. 125–141.
[References -> on the "English" button bottom right]
