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

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

REFERENCES

1.   Vasin V.V. Osnovy teorii nekorrektnykh zadach [Fundamentals of the theory of ill-posed problems]. Novosibirsk, Publ. of Syberian Branch of Russian Acad. Sci., 2020, 312 p. ISBN 978-5-7692-1673-2 .

2.   Vasin V.V., Ageev A. L. Ill-posed problems with a priori information. Utrecht, VSP Publ., 1995, 255 с. ISBN: 906764191X. Original Russian text was published in Vasin V.V., Ageev A.L., Nekorrektnye zadachi s apriornoi informatsiei, Yekaterinburg, Ural Publishing House “Nauka”, 1993, 264 p. ISBN: 5-7691-0390-6 

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

4.   Fejér L. Über die Lage der Nullstellen fon Polinomen, die aus Minimumforderung gewisser Arten entspringen. Math. Ann., 1922, vol. 85, no. 1, pp. 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, pp. 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. pp. 382–392. doi: 10.4153/CJM-1954-037-2

7.   Eremin I.I. Generalization of the relaxation method of Motzkin — Agmon. Uspekhi Matem. Nauk, 1965, vol. 20, no. 2, pp. 183–187 (in Russian).

8.   Eremin I.I. Methods of fejer’s approximations in convex programming. Math. Notes, 1968, vol. 3, no. 2, pp. 139–149. doi: 10.1007/BF01094336

9.   Eremin I.I. Theory of linear optimization, Berlin, Walter de Gruyter, 2002, 248 p. ISBN: 906764353X. Original Russian text was published in Eremin I.I., Teoriya lineinoi optimizatsii, Yekaterinburg, Izd-vo UrO RAN, 1998, 247 p.

10.   Eremin I.I. Sistemy lineinyh neravenstv i lineinaya optimizaziya [Systems of linear inequalities and linear optimization], Yekaterinburg, Izd-vo RAN, 2007, 238 p. ISBN: 5-7691-1822-9.

11.   Vasin V.V., Eremin I.I. Operators and iterative processes of Fejér type. Theory and Applications, Berlin, New York, Walter de Gruyter, 2009, 155 p. ISBN: 3110218186. Original Russian text was published in Vasin V.V., Eremin I.I., Operatory i iteratsionnye protsessy feierovskogo tipa, Izhevsk, Regular and Chaotic Dynamics, 2005, 200 p. ISBN: 5-93972-427-2.

12.   Vasin V.V. Iterative methods for solving ill-posed problems with a priori information in Hilbert spaces. USSR Comput. Math and Math. Phys., 1988, vol. 28, no. 4, pp. 6–13. doi: 10.1016/0041-5553(88)90104-8

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

14.   Martinet B. Determination approachee d’un point fixe d’une applications pseudo-contractante. C. R. Acad. Sci. Paris, 1972, vol. 274, pp. 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, pp. 591–597. doi: 10.1090/S0002-9904-1967-11761-0

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

17.   Vainikko G.M. Error estimates for the method of successive approximation for ill-posed problems. Autom. Remote Control, 1980, vol. 41, no. 3, pp. 356–363.

18.   Karmanov V.G. Matematicheskoe programmirovanie [Mathematical programming], Moscow, Fizmatlit, 2008, 260 p. ISBN: 978-5-9221-0983-3.

19.   Bakushinsky A.B., Goncharsky A.V. Iterativnye metody resheniya nekorrektnykh zadach [Iterative methods for solving ill-posed problems]. Moscow, Nauka publ., 1989, 127 p. ISBN: 5-02-013960-2.

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.