Fejér-Type Iterative Processes in the Constrained Quadratic Minimization Problem

V. V. Vasin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 26-41

Résumé

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 solving a linear program, 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.

Détail

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

Bibliographie

[1] Vasin V. V., Osnovy teorii nekorrektnykh zadach, Izd-vo SO RAN, Novosibirsk, 2020, 312 pp.

[2] Vasin V. V., Ageev A. L., Ill-posed problems with a priori information, VSP, Utrecht, The Netherlands, 1995, 255 pp. | MR | Zbl

[3] Lawson C. T., Hansen R. J., Solving least squares problem, SIAM, Philadelphia, 1995, 337 pp. | MR

[4] Fejér L., “Über die Lage der Nullstellen fon Polinomen,die aus Minimumforderung gewisser Art entspringen”, Math. Ann., 85:1 (1922), 41–48 | DOI | MR

[5] Motzkin T. S., Schoenberg J. J., “The relaxation method for linear inequalities”, Canad. J. Math., 6:3 (1954), 393–404 | DOI | MR | Zbl

[6] Agmon S., “The relaxation method for linear inequality”, Canad. J. Math., 6:3 (1954), 382–392 | DOI | MR | Zbl

[7] Eremin I.I., “Obobschenie relaksatsionnogo metoda Motskina — Agmona”, Uspekhi mat. nauk, 20:2 (1965), 183–187 | MR | Zbl

[8] Eremin I.I., “Metody feierovskikh priblizhenii v vypuklom programmirovanii”, Mat. zametki, 3:2 (1968), 217–234

[9] Eremin I. I., Teoriya lineinoi optimizatsii, Izd-vo UrO RAN, Ekaterinburg, 1998, 247 pp.

[10] Eremin I. I., Sistemy lineinykh neravenstv i lineinaya optimizatsiya, Nauch. izdanie, Izd-vo RAN, Ekaterinburg, 2007, 238 pp.

[11] Vasin V. V., Eremin I. I., Operators and iterative processes of Fejér type. Theory and applications, Walter de Gruyter, Berlin; NY, 2009, 155 pp. | MR

[12] Vasin V. V., “Iteratsionnye metody resheniya nekorrektnykh zadach s apriornoi informatsiei v gilbertovykh prostranstvakh”, Zhurn. vychisl. matematiki i mat. fiziki, 22:7 (1988), 971–980

[13] Eicke B., Konvex-restringierte schlechtgestellte Probleme und ihre Regularizierung durch Iterationverfahren, Dr. Diss., Berlin, 1991 | Zbl

[14] Martinet B., “Determination approachee d'un point fixe d'une applications pseudo-contractante”, C. R. Acad. Sci., 274 (1972), 163–175, Paris | MR

[15] Opial Z., “Weak convergence of the sequence of successive approximations for nonexpansive mappings”, Bull. Amer. Math. Soc., 73:4 (1967), 591–597 | DOI | MR | Zbl

[16] Halperin B., “Fixed points of nonexpansive maps”, Bull. Amer. Math. Soc., 73:6 (1967), 957–961 | DOI | MR

[17] Vainikko G. M., “Otsenki pogreshnosti metoda posledovatelnykh priblizhenii dlya nekorrektnykh zadach”, Avtomatika i telemekhanika, 1980, no. 3, 84–92 | Zbl

[18] Karmanov V. G., Matematicheskoe programmirovanie, Fizmatlit, M., 2008, 260 pp.

[19] Bakushinskii A. B., Goncharskii A. V., Iterativnye metody resheniya nekorrektnykh zadach, Nauka, M., 1989, 127 pp.