В.Д. Скарин. О выборе параметров в методе квазирешений для коррекции несобственных задач выпуклого программирования ... С. 187-197

УДК 519.853

MSC: 47N05, 37N25, 37N40

DOI: 10.21538/0134-4889-2020-26-3-187-197

Полный текст статьи (Full text)

Работа выполнена в рамках исследований, проводимых в Уральском математическом центре, и поддержана РФФИ, проект 19-07-01243.

Работа посвящена нахождению аппроксимационных решений несобственных задач выпуклого программирования (НЗ ВП). Для таких задач рассматривается корректирующая модель как задача минимизации целевой функции исходной проблемы на множестве экстремальных точек штрафной функции, которая агрегирует несовместные ограничения. В качестве штрафной функции выбрана точная штрафная функция Еремина — Зангвилла. В условиях приближенного задания исходной информации обобщенное решение НЗ ВП получается в результате применения известного из теории некорректных задач метода квазирешений. Приводятся оценки, характеризующие качество коррекции. Предлагаются итерационные схемы, реализующие данный подход.

Ключевые слова: выпуклое программирование, несобственная задача, оптимальная коррекция, метод точной штрафной функции, метод квазирешений

СПИСОК ЛИТЕРАТУРЫ

1.   Еремин И. И., Мазуров В. Д., Астафьев Н. Н. Несобственные задачи линейного и выпуклого программирования. М.: Наука, 1983. 336 с.

2.   Попов Л. Д., Скарин В. Д. Лексикографическая регуляризация и двойственность для несобственных задач линейного программирования // Тр. Ин-та математики и механики УрО РАН. 2015. Т. 21, № 3. С. 279–291.

3.   Skarin V. D. On the application of the residual method for the correction of inconsistent problems of convex programming // Proc. Steklov Institute Math. 2015. Vol. 289, Suppl. 1. P. S182–S191. doi: 10.1134/S0081543815050168 

4.   Волков В. В., Ерохин В. И., Красников А. С., Разумов А. В., Хватов М. Н. Минимальная по евклидовой норме матричная коррекция пары двойственных задач линейного программирования // Журн. вычисл. математики и мат. физики. 2017. Т. 57, № 11. C. 1788–1803.

5.   Муравьева О. В. Определение радиусов совместности и несовместности систем линейных уравнений и неравенств по матричной норме l1 // Журн. вычисл. математики и мат. физики. 2018. Т. 58, № 6. C. 873–882.

6.   Васильев Ф. П., Потапов М. М., Артемьева Л. А. Экстраградиентный метод коррекции противоречивых задач линейного программирования // Журн. вычисл. математики и мат. физики. 2018. Т. 58, № 12. C. 1992–1998.

7.   Тихонов А. Н., Арсенин В. Я. Методы решения некорректных задач. М.: Наука, 1979. 288 с.

8.   Васильев Ф. П. Методы оптимизации: Кн. 1, 2. М.: МЦНМО, 2011. 1056 c.

9.   Golub G. N., Hansen P. C., O’Leary D. P. Tikhonov regularization and total least squares // SIAM J. Matrix Anal. Appl. 1999. Vol. 21, № 1. P. 185–194. doi: 10.1137/S0895479897326432 

10.   Renaut R. A., Guo N. Efficient algorithms for solution of regularized total least squares // SIAM J. Matrix Anal. Appl. 2005. Vol. 26, № 2. P. 457–476. doi: 10.1137/S0895479802419889 

11.   Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. М.: Наука, 1976. 192 с.

12.   Burke J. V. An exact penalization viewpoint of constrained optimization // SIAM J. Contr. Optim. 1991. Vol. 29, № 4. P. 968–998. doi: 10.1137/0329054 

13.   Демьянов В. Ф., Васильев Л. В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.

Поступила 3.03.2020

После доработки 6.04.2020

Принята к публикации 20.04.2020

Скарин Владимир Дмитриевич
д-р физ.-мат. наук, зав. сектором
Инcтитут математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: skavd@imm.uran.ru

Ссылка на статью: В.Д. Скарин. О выборе параметров в методе квазирешений для коррекции несобственных задач выпуклого программирования // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 3. С. 187-197

English

V.D. Skarin. On the choice of parameters in the quasisolution method for the correction of improper convex programs

The paper is devoted to finding approximation solutions of improper convex programs. For such programs, a correction model is considered in the form of the problem of minimizing the objective function of the original problem on the set of extremal points of a penalty function, which aggregates the inconsistent constraints. For the penalty function, the Eremin–Zangwill exact penalty function is chosen. Under an approximately given input, a generalized solution of the improper convex program is obtained by applying the quasisolution method known in the theory of ill-posed problems. Estimates characterizing the quality of the correction are given. Iterative schemes implementing this approach are proposed.

Keywords: convex programming, improper problem, optimal correction, exact penalty function method, quasisolution method

Received March 3, 2020

Revised April 6, 2020

Accepted April 10, 2020

Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and 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. On the choice of parameters in the quasisolution method for the correction of improper convex programs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 187–197.

[References -> on the "English" button bottom right]