On the optimal correction of improper convex programming problems based on the method of quasi-solutions

V. D. Skarin

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

Résumé

The work continues the author's research on the construction of possible approximations for improper problems of convex programming. The problem of minimizing the objective function of the original problem on the set of minimum points of the Chebyshev norm of the constraint discrepancy is defined as a basic model for correcting an improper problem. For this setting, one of the classical methods of regularization of ill-posed extremal problems is used, namely, the method of quasi-solutions. This method is based on the transition to a problem of unconstrained minimization by aggregation of the constraint function of the original problem. For this purpose, a modification of the penalty function method is used, namely, the generalized inverse barrier function method. This approach seems to be promising from the point of view of the numerical implementation of the quasi-solution method. Convergence conditions are formulated for the proposed method, including the case where the input data are given inaccurately. Special attention is paid to finding the value of optimal correction of the constraints in the improper problem of convex programming under study and to calculating the optimal value of the regularization parameter in the method of quasi-solutions.

Détail

Keywords: convex programming, improper problem, method of quasi-solutions, barrier function methods.
Mots-clés : optimal correction

Bibliographie

[1] Eremin I.I., “Dvoistvennost dlya nesobstvennykh zadach lineinogo i vypuklogo programmirovaniya”, Dokl. AN SSSR, 256:2 (1981), 272–276 | MR | Zbl

[2] Eremin I.I., Mazurov Vl.D., Astafev N.N., Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya, Nauka, M., 1983, 336 pp.

[3] Tikhonov A.N., Arsenin V.Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1979, 288 pp.

[4] Vasilev F.P., Metody optimizatsii, kn. 1,2, MTsNMO, 2011, 1056 pp.

[5] Golub G.N., Hansen P.C., O'Leary D.P., “Tikhonov regularization and total least squares”, SIAM J. Matrix Anal. Appl., 2:1 (1999), 185–194 | DOI | MR

[6] Renaut R., Guo N., “Efficient algorithms for solution of regularized total least squares”, SIAM J. Matrix Anal. Appl., 26:2 (2005), 457–476 | DOI | MR | Zbl

[7] Vasilev F.P., Potapov M.M., Artemeva L.A., “Ekstragradientnyi metod korrektsii protivorechivykh zadach lineinogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 58:12 (2018), 1992–1998 | DOI | Zbl

[8] Fiakko A., Mak-Kormik G., Nelineinoe programmirovanie. Metody posledovatelnoi bezuslovnoi minimizatsii, Mir, M., 1972, 240 pp. | MR

[9] Eremin I.I., Astafev N.N., Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya, Nauka, M., 1976, 196 pp.

[10] Evtushenko Yu.G., Metody resheniya ekstremalnykh zadach i ikh primenenie v sistemakh optimizatsii, Nauka, M., 1982, 432 pp. | MR

[11] Minu M., Matematicheskoe programmirovanie. Teoriya i algoritmy, Nauka, M., 1990, 488 pp.

[12] Skarin V.D., “O metode barernykh funktsii i algoritmakh korrektsii nesobstvennykh zadach vypuklogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 14:2 (2008), 115–128 | MR | Zbl

[13] Popov L.D., “Primenenie barernykh funktsii dlya optimalnoi korrektsii nesobstvennykh zadach lineinogo programmirovaniya 1-go roda”, Avtomatika i telemekhanika, 3 (2012), 3–11 | Zbl

[14] Skarin V.D., “Metod kvazireshenii na osnove barernykh funktsii v analize nesobstvennykh zadach vypuklogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 28:4 (2022), 201–215