Том 25, номер 1, 2019
УДК 519.658.4
MSC: 90C05, 90C46
DOI: 10.21538/0134-4889-2019-25-1-196-206
Полный текст статьи (Full text)
Исследования поддержаны Российским научным фондом, грант № 14-11-00109.
Продолжено исследование альтернативных схем формирования двойственности в линейном программировании, в основе которых лежит симметричная регуляризация функции Лагранжа одновременно по прямым и двойственным переменным. Особенностью данной работы является использование неевклидовых норм-стабилизаторов. Для новых схем получены симметричные оценки точности получаемого решения. Также проведено исследование свойств метода для случая, когда система ограничений у исходной задачи противоречива. Для таких задач (несобственных 1-го рода) метод дает их обобщенное решение, имеющее хорошую содержательную интерпретацию. Для несобственного случая также получены аналогичные оценки уклонения регуляризированного решения от обобщенного.
Ключевые слова: линейное программирование, двойственность, методы регуляризации, точность решения
СПИСОК ЛИТЕРАТУРЫ
1. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1979. 285 с.
2. Васильев Ф. П. Методы оптимизации: в 2 кн. Москва: МЦНМО, 2011. Кн. 1: 620 с.; кн. 2: 433 с.
3. Rockafellar R. T. Augmented lagrange multiplier functions and duality in nonconvex programming // SIAM J. Contr. 1974. Vol. 12, no. 2. P. 268–285. doi: 10.1137/0312021
4. Evtushenko Ju. Numerical optimization technique. Optimization Software. N Y: Inc. Publ. Division, 1985. 562 p.
5. Гольштейн Е.Г., Третьяков Н.В. Модифицированные функции Лагранжа. Теория и методы оптимизации. Москва: Наука. Главная редакция физ.-мат. литературы, 1989. 400 с.
6. Roos C., Terlaky T. Theory and algorithms for linear optimization: An interior point approach. N Y: Wiley, 1997. 454 p.
7. Еремин И. И. Двойственность в линейной оптимизации. Екатеринбург: Изд-во УрО РАН, 2001. 180 с.
8. Еремин И. И., Мазуров Вл. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
9. Eremin I. I. Theory of linear optimization. Inverse and ill-posed problems series. Utrecht; Boston; Koln; Tokyo: VSP, 2002. 248 p.
10. Скарин В. Д. Об оптимальной коррекции противоречивых задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2013. Т. 19, № 2. C. 267–274.
11. Skarin V. D. Regularization of the min-max problems occurring in convex programming // Comput. Math. Math. Physics. 1977. Vol. 17, no. 6. P. 65–78. doi: 10.1016/0041-5553(77)90173-2
12. Скарин В. Д. О методе регуляризации для противоречивых задач выпуклого программирования // Изв. вузов. Математика. 1995. № 12. P. 81–88.
13. Popov L. D. On Accuracy estimates for one regularization method in linear programming // Optimization Problems and Their Applications (OPTA 2018) / eds. A. Eremeev, M. Khachay, Y. Kochetov, P. Pardalos. Cham: Springer, 2018. P. 170–182. (Communications Comp. Inform. Sci.; vol. 871). doi: 10.1007/978-3-319-93800-4_14
14. Guddat J. Stability in convex quadratic programming // Mathematische Operationsforschung und Statistik. 1976. Vol. 8, no. 2. P. 223–245. doi: 10.1080/02331887608801291
15. Dorn W. S. Duality in quadratic programming // Quart. Appl. Math. 1960. Vol. 18, no. 2. P. 407–413. doi: 10.1090/qam/112751
16. Hoffman A. J. On approximate solutions of systems of linear inequalities // J. Res. Nat. Bur. Standards. 1952. Vol. 49, no. 4. P. 263–265. doi: 10.1142/9789812796936_0018
Поступила 19.09.2018
После доработки 21.12.2018
Принята к публикации 24.12.2018
Попов Леонид Денисович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
профессор кафедры ВКТ
Уральский федеральный университет
г. Екатеринбург
e-mail: popld@imm.uran.ru
Ссылка на статью: Попов Л.Д. Об одном методе регуляризации для несобственных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 1. С. 196-206.
Cite this article as: L.D. Popov. On a regularization method for improper linear programs, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2019, vol. 25, no. 1, pp. 196-206.
English
L.D. Popov. On a regularization method for improper linear programs
We continue the study of alternative duality formation schemes in linear programming based on the symmetric regularization of the Lagrange function simultaneously in the primal and dual variables. A feature of this work is the use of non-Euclidean stabilizing norms. Symmetric bounds for the error of the resulting solution are obtained for the new schemes. The properties of the method are investigated in the case where the constraint system of the original problem is inconsistent. For such problems (improper problems of the first kind), the method gives their generalized solution with an appropriate interpretation. For the improper case, we derive similar estimates for the deviation of the regularized solution from the generalized solution.
Keywords: linear programming, duality, regularization methods, accuracy of the solution
Received September 19, 2018
Revised December 21, 2018
Accepted December 24, 2018
Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).
Leonid Denisovich Popov, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: popld@imm.uran.ru
[References -> on the "English" button bottom right]
