В.В. Васин. Итерационные процессы фейеровского типа в задаче условной квадратичной минимизации ... С. 26-41

УДК 517.988

MSC: 65J20, 65K05

DOI: 10.21538/0134-4889-2023-29-3-26-41

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

Статья переведена: ISSN 0081-5438 

Proceedings of the Steklov Institute of Mathematics, 2023, Vol. 323, Suppl. 1, pp. S305–S320. (Abstract)

В работе представлен обзор методов решения некорректно поставленной задачи условной выпуклой квадратичной минимизации на основе итерационных методов фейеровского типа, в которых широко используются идеи и подходы, развитые в работах И. И. Еремина — основателя Уральской научной школы по математическому программированию. Наряду с постановкой общего вида рассматриваются варианты исходной задачи с ограничениями в форме систем равенств и неравенств, которые имеют многочисленные приложения. Кроме того, исследуются частные постановки задачи, среди которых: нахождение метрической проекции, решение задачи линейного программирования, которые имеют самостоятельный интерес. Отличительной чертой этих методов является то, что для них устанавливается не только сходимость, но и устойчивость к погрешностям входных данных, т. е. методы порождают регуляризующие алгоритмы в отличие от прямых методов, которые этим свойством не обладают.

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

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

1.   Васин В. В. Основы теории некорректных задач. Новосибирск: Изд-во СО РАН, 2020. 312 с.

2.   Vasin V. V., Ageev A. L. Ill-posed problems with a priori information. Utrecht, The Netherlands: VSP, 1995. 255 p.

3.   Lawson C. T., Hansen R. J. Solving least squares problem. Philadelphia: SIAM, 1995. 337 p.

4.   Fejér L. Über die Lage der Nullstellen fon Polinomen,die aus Minimumforderung gewisser Art entspringen // Math. Ann. 1922. Bd 85, № 1. S. 41–48. doi: 10.1007/BF01449600

5.   Motzkin T. S., Schoenberg J. J. The relaxation method for linear inequalities // Canad. J. Math. 1954. Vol. 6, no. 3. P. 393–404. doi: 10.4153/CJM-1954-038-x

6.   Agmon S. The relaxation method for linear inequality // Canad. J. Math. 1954. Vol. 6, no. 3. P. 382–392. doi: 10.4153/CJM-1954-037-2

7.   Еремин И.И. Обобщение релаксационного метода Моцкина — Агмона // Успехи мат. наук. 1965. Т. 20, вып. 2. С. 183–187.

8.   Еремин И.И. Методы фейеровских приближений в выпуклом программировании // Мат. заметки. 1968. Т. 3, вып. 2. С. 217–234.

9.   Еремин И. И. Теория линейной оптимизации. Екатеринбург: Изд-во УрО РАН, 1998. 247 с.

10.   Еремин И. И. Системы линейных неравенств и линейная оптимизация. Науч. издание. Екатеринбург: Изд-во РАН, 2007. 238 с.

11.   Vasin V. V., Eremin I. I. Operators and iterative processes of Fejér type. Theory and applications. Berlin; NY: Walter de Gruyter, 2009. 155 p.

12.   Васин В. В. Итерационные методы решения некорректных задач с априорной информацией в гильбертовых пространствах // Журн. вычисл. математики и мат. физики. 1988. Т. 22, № 7. С. 971–980.

13.   Eicke B. Konvex-restringierte schlechtgestellte Probleme und ihre Regularizierung durch Iterationverfahren. Berlin: Dr. Diss., 1991.

14.   Martinet B. Determination approachee d’un point fixe d’une applications pseudo-contractante // Paris: C. R. Acad. Sci. 1972. Vol. 274. P. 163–175.

15.   Opial Z. Weak convergence of the sequence of successive approximations for nonexpansive mappings // Bull. Amer. Math. Soc. 1967. Vol. 73, no. 4. P. 591–597. doi: 10.1090/S0002-9904-1967-11761-0

16.   Halperin B. Fixed points of nonexpansive maps // Bull. Amer. Math. Soc. 1967. Vol. 73, no. 6. P. 957–961. doi: 10.1090/S0002-9904-1967-11864-0

17.   Вайникко Г. М. Оценки погрешности метода последовательных приближений для некорректных задач // Автоматика и телемеханика. 1980. № 3. С. 84–92.

18.   Карманов В. Г. Математическое программирование. М.: Физматлит, 2008. 260 с.

19.   Бакушинский А. Б., Гончарский А. В. Итеративные методы решения некорректных задач. М.: Наука, 1989. 127 c.

Поступила 19.02.2023

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

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

Васин Владимир Васильевич
д-р физ.-мат. наук, профессор
главный научн. сотрудник
Институт математики и механики им. Н.H. Красовского УрО РАН
г. Екатеринбург
e-mail: vasin@imm.uran.ru

Ссылка на статью: В.В. Васин. Итерационные процессы фейеровского типа в задаче условной квадратичной минимизации // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 26-41

English

V.V. Vasin. Fejér-type iterative processes in the constrained quadratic minimization problem

The paper presents an overview of methods for solving an ill-posed problem of constrained convex quadratic minimization based on the Fejér-type iterative methods, which widely use the ideas and approaches developed in the works of I. I. Eremin, the founder of the Ural research school of mathematical programming. Along with a problem statement of general form, we consider variants of the original problem with constraints in the form of systems of equalities and inequalities, which have numerous applications. In addition, particular formulations of the problem are investigated, including the problem of finding a metric projection and a linear programming problem, which are of independent interest. A distinctive feature of these methods is that not only convergence but also stability with respect to errors in the input data are established for them; i. e., the methods generate regularizing algorithms in contrast to the direct methods, which do not have this property.

Keywords: quadratic minimization, ill-posed problem, linear constraints, Fejér process, regularizing algorithm

Received February19, 2023

Revised March 1, 2023

Accepted March 6, 2023

Vladimir Vasilievich Vasin, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: vasin@imm.uran.ru

Cite this article as: V.V. Vasin. Fejér-type iterative processes in the constrained quadratic minimization problem. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 26–41; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S305–S320.

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