Stable sequential Kuhn–Tucker theorem in iterative form or a regularized Uzawa algorithm in a regular nonlinear programming problem

M. I. Sumin

Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 55 (2015) no. 6, pp. 947-977

Résumé

A parametric nonlinear programming problem in a metric space with an operator equality constraint in a Hilbert space is studied assuming that its lower semicontinuous value function at a chosen individual parameter value has certain subdifferentiability properties in the sense of nonlinear (nonsmooth) analysis. Such subdifferentiability can be understood as the existence of a proximal subgradient or a Fréchet subdifferential. In other words, an individual problem has a corresponding generalized Kuhn–Tucker vector. Under this assumption, a stable sequential Kuhn–Tucker theorem in nondifferential iterative form is proved and discussed in terms of minimizing sequences on the basis of the dual regularization method. This theorem provides necessary and sufficient conditions for the stable construction of a minimizing approximate solution in the sense of Warga in the considered problem, whose initial data can be approximately specified. A substantial difference of the proved theorem from its classical same-named analogue is that the former takes into account the possible instability of the problem in the case of perturbed initial data and, as a consequence, allows for the inherited instability of classical optimality conditions. This theorem can be treated as a regularized generalization of the classical Uzawa algorithm to nonlinear programming problems. Finally, the theorem is applied to the “simplest” nonlinear optimal control problem, namely, to a time-optimal control problem.

Bibliographie

[1] Alekseev V. M., Tikhomirov V. M., Fomin S. V., Optimalnoe upravlenie, Nauka, M., 1979 | MR

[2] Vasilev F. P., Metody optimizatsii, V 2-kh kn., MTsNMO, M., 2011

[3] Sumin M. I., “Ustoichivoe sekventsialnoe vypukloe programmirovanie v gilbertovom prostranstve i ego prilozhenie k resheniyu neustoichivykh zadach”, Zh. vychisl. matem. i matem. fiz., 54:1 (2014), 25–49 | MR | Zbl

[4] Sumin M. I., “Regulyarizovannaya parametricheskaya teorema Kuna–Takkera v gilbertovom prostranstve”, Zh. vychisl. matem. i matem. fiz., 51:9 (2011), 1594–1615 | MR | Zbl

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

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

[7] Sumin M. I., “On the stable sequential Kuhn–Tucker theorem and its applications”, Appl. Math., 3:10A, Special issue “Optimization” (2012), 1334–1350

[8] Sumin M. I., “Ob ustoichivom sekventsialnom printsipe Lagranzha v vypuklom programmirovanii i ego primenenii pri reshenii neustoichivykh zadach”, Tr. In-ta matem. i mekhan. UrO RAN, 19, no. 4, 2013, 231–240

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

[10] Sumin M. I., “Regulyarizatsiya v lineino vypukloi zadache matematicheskogo programmirovaniya na osnove teorii dvoistvennosti”, Zh. vychisl. matem. i matem. fiz., 47:4 (2007), 602–625 | MR | Zbl

[11] Sumin M. I., Nekorrektnye zadachi i metody ikh resheniya. Materialy k lektsiyam dlya studentov starshikh kursov, Uch. posobie, Izd-vo Nizhegorodskogo gos. un-ta, N. Novgorod, 2009

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

[13] Minu M., Matematicheskoe programmirovanie. Teoriya i algoritmy, Nauka, M., 1990 | MR

[14] Sumin M. I., “Regulyarizovannyi dvoistvennyi metod resheniya nelineinoi zadachi matematicheskogo programmirovaniya”, Zh. vychisl. matem. i matem. fiz., 47:5 (2007), 796–816 | MR | Zbl

[15] Sumin M. I., “Parametric dual regularization in a nonlinear mathematical programming”, Ch. 5, Advances in Mathematics Research, 11, Nova Sci. Publ. Inc., New-York, 2010, 103–134

[16] Kanatov A. V., Sumin M. I., “Sekventsialnaya ustoichivaya teorema Kuna–Takkera v nelineinom programmirovanii”, Zh. vychisl. matem. i matem. fiz., 53:8 (2013), 1249–1271 | Zbl

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

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

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

[20] Clarke F. H., Ledyaev Yu. S., Stern R. J., Wolenski P. R., Nonsmooth analysis and control theory, Graduate Texts in Mathematics, 178, Springer-Verlag, New York, 1998 | MR | Zbl

[21] Mordukhovich B. S., Variational analysis and generalized differentiation, v. I, Basic Theory ; v. II, Applications, Springer, Berlin, 2006 | MR

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

[23] Hestenes M. R., “Multipliers and gradient methods”, J. Optimizat. Appl., 4 (1969), 303–320 | MR | Zbl

[24] Powell M. J. D., “A method for nonlinear constraints in minimization problems”, Optimizat., ed. R. Fletcher, Academic Press, New-York, 1969, 293–298 | MR

[25] Bertsekas D., Uslovnaya optimizatsiya i metody mnozhitelei Lagranzha, Radio i svyaz, M., 1987 | MR

[26] Sumin M. I., “Suboptimalnoe upravlenie sistemami s raspredelennymi parametrami: minimiziruyuschie posledovatelnosti, funktsiya znachenii”, Zh. vychisl. matem. i matem. fiz., 37:1 (1997), 23–41 | MR

[27] Golshtein E. G., Tretyakov N. V., Modifitsirovannye funktsii Lagranzha. Teoriya i metody optimizatsii, Nauka, M., 1989 | MR

[28] Arutyunov A. V., Usloviya ekstremuma. Normalnye i vyrozhdennye zadachi, Faktorial, M., 1997 | MR

[29] Milyutin A. A., Dmitruk A. V., Osmolovskii N. P., Printsip maksimuma v optimalnom upravlenii, Izd-vo Tsentra prikladnykh issledovanii pri mekhan.-matem. f-te MGU, M., 2004