Duality-based regularization in a linear convex mathematical programming problem

M. I. Sumin

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 47 (2007) no. 4, pp. 602-625

Résumé

For a linear convex mathematical programming (MP) problem with equality and inequality constraints in a Hilbert space, a dual-type algorithm is constructed that is stable with respect to input data errors. In the algorithm, the dual of the original optimization problem is solved directly on the basis of Tikhonov regularization. It is shown that the necessary optimality conditions in the original MP problem are derived in a natural manner by using dual regularization in conjunction with the constructive generation of a minimizing sequence. An iterative regularization of the dual algorithm is considered. A stopping rule for the iteration process is presented in the case of a finite fixed error in the input data.

Bibliographie

[1] Vasilev F. P., Metody optimizatsii, Faktorial Press, M., 2002

[2] Ishmukhametov A. Z., “Dvoistvennyi regulyarizovannyi metod resheniya odnogo klassa vypuklykh zadach minimizatsii”, Zh. vychisl. matem. i matem. fiz., 40:7 (2000), 1045–1060 | MR | Zbl

[3] Sumin M. I., “Optimalnoe upravlenie parabolicheskimi uravneniyami: dvoistvennye chislennye metody, regulyarizatsiya”, Raspredelennye sistemy: optimizatsiya i prilozheniya v ekonomike i naukakh ob okruzhayuschei srede, Mezhdunar. konf. Ekaterinburg (30 maya–2 iyunya 2000 g.), In-t matem. i mekhan. UrO RAN, Ekaterinburg, 2000, 66–69

[4] Sumin M. I., “Regulyarizovannyi gradientnyi dvoistvennyi metod resheniya obratnoi zadachi finalnogo nablyudeniya dlya parabolicheskogo uravneniya”, Zh. vychisl. matem. i matem. fiz., 44:11 (2004), 2001–2019 | MR | Zbl

[5] Sumin M. I., “Iterativnaya regulyarizatsiya gradientnogo dvoistvennogo metoda dlya resheniya integralnogo uravneniya Fredgolma pervogo roda”, Vestn. Nizhegorodskogo un-ta. Ser. Matem., 2004, no. 1(2), 192–208

[6] Sumin M. I., “Regulyarizovannyi dvoistvennyi algoritm v zadachakh optimalnogo upravleniya dlya raspredelennykh sistem”, Vestn. Nizhegorodskogo un-ta. Ser. Matem. modelirovanie i optimalnoe upravlenie, 2006, no. 2(31), 82–102

[7] Minu M., Matematicheskoe programmirovanie. Teoriya i algoritm, Nauka, M., 1990 | MR

[8] Uzawa H., “Iterative methods for concave programming”, Studies in Linear and Nonlinear Programming, Chap. 10, Univ. Press, Stanford, 1958 | Zbl

[9] Errou K. Dzh., Gurvits L., Udzava X., Issledovaniya po lineinomu i nelineinomu programmirovaniyu, Izd-vo inostr. lit., M., 1962

[10] Ekland I., Temam R., Vypuklyi analiz i variatsionnye problemy, Mir, M., 1979 | MR

[11] Tlovinski R.,Lions Zh.-D., Tremoler R., Chislennoe issledovanie variatsionnykh neravenstv, Mir, M., 1979 | MR

[12] Temam R., Uravneniya Nave–Stoksa. Teoriya i chislennyi analiz, Mir, M., 1981 | MR | Zbl

[13] Plotnikov V. I., “O skhodimosti konechnomernykh priblizhenii (v zadache ob optimalnom nagreve neodnorodnogo tela proizvolnoi formy)”, Zh. vychisl. matem. i matem. fiz., 8:1 (1968), 136–157 | MR | Zbl

[14] Plotnikov V. I., “Energeticheskoe neravenstvo i svoistvo pereopredelennosti sistemy sobstvennykh funktsii”, Izv. AN SSSR. Ser. matem., 32:4 (1968), 743–755 | MR | Zbl

[15] Osipov Yu. S., Vasilev F. P., Potapov M. M., Osnovy metoda dinamicheskoi regulyarizatsii, Izd-vo MGU, M., 1999

[16] Sumin M. I., “Regulyarizatsiya v zadachakh optimalnogo upravleniya i obratnykh zadachakh na osnove teorii dvoistvennosti”, Mezhdunar. konf. “Tikhonov i sovrem. matem.” (M., MGU, 19–25 iyunya 2006 g.), MGU, M., 2006, 184–185

[17] Varga Dzh., Optimalnoe upravlenie differentsialnymi i funktsionalnymi uravneniyami, Nauka, M., 1977 | MR

[18] Borwein J. M., Strojwas H. M., “Proximal analysis and boundaries of closed sets in Banach space. Part I: Theory”, Canadian J. Math., 38:2 (1986), 431–452 ; “Part II: Applications”, 39:2 (1987), 428–472 | MR | Zbl | MR | Zbl

[19] Klark F., Optimizatsiya i negladkii analiz, Nauka, M., 1988 | MR | Zbl

[20] Loewen P. D., Optimal control via nonsmooth analysis, CRM Proc. Lect. Notes, 2, Amer. Math. Soc., Providence, RI, 1993 | MR | Zbl

[21] Sumin M. I., “Suboptimal control of systems with distributed parameters: Minimizing sequences, value function, regularity, normality”, Control and Cybernetics, 25:3 (1996), 529–552 | MR | Zbl

[22] Oben Zh.-P., Nelineinyi analiz i ego ekonomicheskie prilozheniya, Mir, M., 1988 | MR

[23] Ekeland I., “On the Variational Principle”, J. Math. Analys and Appl., 47:2 (1974), 324–353 | DOI | MR | Zbl

[24] Kolmogorov A. H., Fomin C. B., Elementy teorii funktsii i funktsionalnogo analiza, Nauka, M., 1981 | MR

[25] Oben Zh.-P., Ekland I., Prikladnoi nelineinyi analiz, Mir, M., 1988 | MR

[26] Tikhonov A. N., Arsenin V. Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1986 | MR | Zbl

[27] Bakushinskii A. B., Goncharskii A. B., Nekorrektnye zadachi. Chislennye metody i prilozheniya, MGU, M., 1989