УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2018-24-3-187-199
Полный текст статьи
Исследования поддержаны Российским научным фондом, грант № 14-11-00109.
В статье рассматриваются вопросы коррекции несобственных задач выпуклого программирования, прежде всего задач с противоречивой системой ограничений. Такие задачи часто возникают в практике математического моделирования конкретных прикладных постановок из области исследования операций. Вследствие частоты появления несобственных задач актуальной является разработка методов коррекции таких задач, т. е. построения близких в определенном смысле разрешимых моделей, решение которых принимается за обобщенное (аппроксимационное) решение исходной постановки. В работе корректирующие задачи строятся путем вариации правых частей ограничений относительно минимума некоторой функции штрафа, частным случаем которой могут служить различные нормы векторов ограничений. В результате возникают методы оптимальной коррекции несобственной задачи, представляющие собой модификации регуляризированного (по Тихонову) метода штрафных функций. Особое внимание при этом уделяется применению метода точного штрафа. Формулируются условия и устанавливаются оценки сходимости предлагаемых методов.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, методы штрафных функций, метод регуляризации Тихонова
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И. И., Мазуров В. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
2. Мазуров Вл. Д. Метод комитетов в задачах оптимизации и классификации. М.: Наука, 1990. 246 с.
3. Khachay M. Yu. On approximate algorithm of a minimal committee of a linear inequalities system // Pattern Recogn. and Image Anal. 2003. Vol. 13, no. 3. P. 459–464.
4. Попов Л. Д. Применение барьерных функций для оптимальной коррекции несобственных задач линейного программирования 1-го рода // Автоматика и телемеханика. 2012. № 3. С. 3–11.
5. Ерохин В. И., Красников А. С., Хвостов М. Н. Матричные коррекции задач линейного программирования по минимуму евклидовой нормы // Автоматика и телемеханика. 2012. № 3. С. 219–231.
6. Скарин B. Д. О применении одного метода регуляризации для коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2012. Т. 18, № 3. С. 230–241.
7. Dax A. The smallest correction of an inconsistent system of linear inequalities // Optimization and Engineering. 2001. Vol. 2, no. 3. P. 349–359. doi: 10.1023/A:1015370617219 .
8. Amaral P., Barahona P. Connections between the total least squares and the correction of an infeasible system of linear inequalities // Linear Algebra and Its Appl. 2005. Vol. 395. P. 191–210. doi: 10.1016/j.laa.2004.08.022 .
9. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1979. 288 с.
10. Иванов В. К., Васин В. В., Танана В. П. Теория линейных некорректных задач и ее приложения. М.: Наука, 1978. 208 с.
11. Васильев Ф. П. Методы оптимизации: Кн. 1, 2. М.: МЦНМО, 2011. Т. 1: 620 p. ISBN: 978-5-94057-707-2 ; Т. 2: 433 p. ISBN: 978-5-94057-708-9 .
12. 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. doi: 10.1137/S0895479897326432 .
13. 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. doi: 10.1137/S0895479802419889 .
14. Skarin V. D. On the parameter control of the residual method for the correction of improper problems of convex programming // Proc. DOOR 2016. Cham: Springer International Publishing, 2016. P. 441–451. (Lecture Notes Comp. Sci.; vol. 9869). doi: 10.1007/978-3-319-44914-2_35 .
15. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.
Поступила 17.05.2018
Скарин Владимир Дмитриевич
д-р физ.-мат. наук, зав. сектором
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет им. Б.Н. Ельцина,
г. Екатеринбург
e-mail: skavd@imm.uran.ru
English
V.D. Skarin. The method of penalty functions and regularization in the analysis of improper convex programming problems.
We consider the questions of correction of improper convex programming problems, first of all, problems with inconsistent systems of constraints. Such problems often arise in the practice of mathematical simulation of specific applied settings in operations research. Since improper problems are rather frequent, it is important to develop methods of their correction, i.e., methods of construction of solvable models that are close to the original problems in a certain sense. Solutions of these models are taken as generalized (approximation) solutions of the original problems. We construct the correcting problems using a variation of the right-hand sides of the constraints with respect to the minimum of a certain penalty function, which, in particular, can be taken as some norm of the vector of constraints. As a result, we obtain optimal correction methods that are modifications of the (Tikhonov) regularized method of penalty functions. Special attention is paid to the application of the exact penalty method. Convergence conditions are formulated for the proposed methods and convergence rates are established.
Keywords: convex programming, improper problem, optimal correction, penalty function methods, Tikhonov regularization method
The paper was received by the Editorial Office on May 17, 2018.
Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci, Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: skavd@imm.uran.ru
[References -> on the "English" button bottom right]
