УДК 519.853
MSC: 47N05, 37N25, 37N40
DOI: 10.21538/0134-4889-2017-23-3-234-243
Полная версия статьи
Исследования поддержаны Российским научным фондом, грант № 14-11-00109.
В работе рассматриваются задачи выпуклого программирования с возможно противоречивой системой ограничений. Такие задачи составляют важный класс несобственных моделей выпуклойоптимизации и часто возникают при математическом моделировании практических постановок из области исследования операций. Частота появления несобственных задач делает актуальнойнеобходимость разработки теории и методов их численной аппроксимации (коррекции), т. е. объективных процедур “развязки” противоречивых ограничений, превращения несобственной модели в совокупность разрешимых задач и выбора среди них оптимальной коррекции. В работе аппроксимирующая задача строится путем вариации правых частей ограничений относительно минимума той или иной векторной нормы. Тип выбранной нормы определяет вид штрафной функции, минимизация которой вместе со стабилизирующей добавкой лежит в основе конкретного метода оптимальной коррекции несобственной задачи. Евклидова норма влечет применение квадратичного штрафа, кусочно-линейная норма (чебышевская, октаэдрическая) предполагает использование точной штрафной функции. Предлагаемые алгоритмы могут быть проинтерпретированы и как методы регуляризации (по Тихонову) задач выпуклого программирования с неточно заданной исходной информацией. Формулируются условия и устанавливаются оценки сходимости рассматриваемых методов.
Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод регуляризации Тихонова, методы штрафных функций.
СПИСОК ЛИТЕРАТУРЫ
1. Еремин И. И., Мазуров В. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.
2. Васильев Ф. П. Методы оптимизации. М.: Факториал, 2002. 824 c.
3. Скарин B. Д. О применении одного метода регуляризации для коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2012. Т. 18, № 3. С. 230–241.
4. Антипин А. С. Метод регуляризации в задачах выпуклого программирования // Экономика и мат. методы. 1975. Т. 11, № 2. С. 336–342.
5. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.
6. Скарин B. Д. О методе регуляризации для противоречивых задач выпуклого программирования // Изв. вузов. Математика. 1995. № 12. С. 81–88.
7. Еремин И. И. К методу штрафов в математическом программировании // Докл. РАН. 1996. Т. 346, № 4. С. 459–461.
8. Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. М.: Наука, 1967. 460 с.
9. Скарин B. Д. О методе барьерных функций и алгоритмах коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2008. Т. 14, № 2. С. 115–128.
Поступила 1.06.2017
Скарин Владимир Дмитриевич
доктор физ.-мат. наук, зав. сектором
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: skavd@imm.uran.ru
English
V. D. Skarin. On the construction of regularizing algorithms for the correction of improper convex programming problems.
We consider convex programming methods with a possibly inconsistent constraint system. Such problems constitute an important class of improper models of convex optimization and often arise in the mathematical modeling of real-life operations research statements. Since improper problems arise rather frequently, the theory and methods of their numerical approximation (correction) should be developed, which would allow to design objective procedures that resolve inconsistent constraints, turn an improper model into a family of feasible problems, and choose an optimal correction among them. In the present paper, an approximating problem is constructed by the variation of the right-hand sides of the constraints with respect to some vector norm. The type of the norm defines the form of a penalty function, and the minimization of the penalty function together with a stabilizing term is the core of each specific method of optimal correction of improper problems. The Euclidean norm implies the application of a quadratic penalty, whereas a piecewise linear (Chebyshev of octahedral) norm is concerned with the use of an exact penalty function. The proposed algorithms may also be interpreted as (Tikhonov) regularization methods for convex programming problems with inaccurate input information. Convergence conditions are formulated for the methods under consideration and convergence bounds are established.
Keywords: convex programming, improper problem, optimal correction, Tikhonov regularization method, penalty function methods.
