УДК 519.658.4
MSC: 90C05, 90C46
DOI: 10.21538/0134-4889-2017-23-3-214-223
Полная версия статьи
Работа поддержана Российским фондом фундаментальных исследований (грант № 16-07-00266).
Рассматриваются задачи выпуклого программирования, про ограничения которых априори не известно, совместны они или нет. Для численного анализа и поиска обобщенных решений таких задач предлагается использовать симметричную регуляризацию классической функции Лагранжа одновременно как по прямым, так и по двойственным переменным. За счет такой регуляризации минимаксные задачи, порождаемые расширенным Лагранжианом исходной задачи, оказываются всегда разрешимыми и при стремлении параметра регуляризации к нулю дают автоматически либо обычное решение исходной задачи (в случае ее собственности, т. е. разрешимости), либо ее обобщенное решение (в несобственном случае); последнее минимизирует изменения, которые необходимо внести в ограничения исходной задачи для обеспечения их совместности, и в то же время оптимизируют значение ее целевой функции в релаксированной допустимой области. Такие минимаксные задачи могут быть положены в основу формирования новых схем двойственности, по крайней мере для несобственных постановок. Приведены схемы регуляризации, доказаны теоремы сходимости и численной устойчивости метода, дана содержательная интерпретация получаемого обобщенного решения. Работа развивает ранее опубликованные результаты авторов, полученные ими для задач линейного программирования.
Ключевые слова: выпуклое программирование, двойственность, обобщенные решения, метод регуляризации, метод штрафных функций, лексикографический оптимум.
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И. И., Мазуров Вл. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
2. Ватолин А. А. Множества разрешимости и коррекция седловых функций и систем неравенств: препринт / Ин-т математики и механики УрО АН СССР. Свердловск, 1989. 90 с.
3. Попов Л. Д. Линейная коррекция несобственных минимаксных выпукло-вогнутых задач по максиминному критерию // Журн. вычисл. математики и мат. физики. 1986. Т. 26, № 9. C. 1100–1110.
4. Скарин В. Д. Об одном подходе к анализу несобственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 1986. Т. 26, № 3. С. 439–448.
5. McCormick S. T. How to compute least infeasible flows // Math. Programming. 1997. Vol. 78, no. 2. P. 179–194.
6. Vada J., Slupphaug O., Johansen T. A. Optimal prioritized infeasibility handling in model predictive control: parametric preemptive multiobjective linear programming approach // J. Optim. Theory Appl. 2001. Vol. 109, no. 2. P. 385–413.
7. Leon T., Liern V., Vercher E. Viability of infeasible portfolio selection problems: a fuzzy approach // European J. Oper. Res. 2002. Vol. 139, no. 1. P. 178–189.
8. Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1979. 285 с.
9. Васильев Ф. П. Методы решения экстремальных задач. М.: Наука, 1981. 400 с.
10. Еремин И. И. О задачах последовательного программирования // Сиб. мат. журн. 1973. Т. 14, № 1. С. 124–129.
11. Федоров В. В. Численные методы максимина. М.: Наука, 1979. 280 с.
12. Гольштейн Е. Г. Теория двойственности в математическом программировании и ее приложения. М.: Наука, 1971. 352 с.
13. Popov L.D., Skarin V.D. On alternative duality and lexicographic correction of right-hand-side vector in improper linear programs of the 1st kind // Proc. V Internat. Conf. on Optimization Methods and Applications (OPTIMA-2014; Petrovac, Montenegro, September 28 – October 4, 2014). Moscow, 2014. P. 152–153.
Поступила 25.03.2017
Попов Леонид Денисович
д-р физ.-мат. наук, ведущий науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: popld@imm.uran.ru
Скарин Владимир Дмитриевич
д-р физ.-мат. наук, зав. сектором
Институт математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: skavd@imm.uran.ru
English
L. D. Popov, V. D. Skarin. Regularization methods and issues of lexicographic correction for convex programming problems with inconsistent constraints.
We consider convex programming problems for which it is unknown in advance whether their constraints are consistent. For the numerical analysis of these problems, we propose to apply a multistep symmetric regularization of the classical Lagrange function with respect to both primal and dual variables and then to solve the arising minimax problems with a small parameter. The latter problems are always solvable and give either normal decisions of the original problems in the case of their propriety or, in the improper case, generalized solutions that minimize the discrepancies of the constraints and optimize the value of the objective function asymptotically with respect to the parameter. Minimax problems can also form a basis for the construction of new duality diagrams in convex programming, at least for improper settings. Regularization diagrams are provided, a primal minimax setting is written, theorems on the convergence and numerical stability of the method are proved, and an informal interpretation of the generalized solutions is given. The study develops the authors’ earlier results obtained for linear programming problems.
Keywords: convex programming, duality, generalized solutions, regularization method, penalty function method.
The paper was received by the Editorial Office on March 25, 2017.
Leonid Denisovich Popov, 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: popld@imm.uran.ru
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
