The quasisolution method in the analysis of convex programs with singularities

V. D. Skarin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 27 (2021) no. 4, pp. 125-141

Résumé

The paper is devoted to the analysis of some convex programs that are “degenerate” (improper, having no solutions in the usual sense). We propose an approach to the correction of such problems based on the ideas of the quasisolution method, which is standard in the theory of ill-posed extremal problems. The constraints of the original problem are aggregated with the use of a certain penalty function, which is explicitly included in the scheme of the quasisolution method. Two most popular variants are used: an exact penalty function and a quadratic penalty function. For each of these variants, the questions of solvability of the arising problems are studied and estimates for the convergence rate of the proposed procedures are established in the case where the input information about the problem to be analyzed is given approximately.

Détail

Keywords: convex programming, improper problem, quasisolution method, penalty function methods.
Mots-clés : optimal correction

Bibliographie

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

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

[3] Volkov V. V., Erokhin V. I., Krasnikov A. S., Razumov A. V., Khvostov M. N., “Minimalnaya po evklidovoi norme matrichnaya korrektsiya pary dvoistvennykh zadach lineinogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 57:11 (2017), 1788–1803 | Zbl

[4] Muraveva O. V., “Opredelenie radiusov sovmestnosti i nesovmestnosti sistem lineinykh uravnenii i neravenstv po matrichnoi norme”, Zhurn. vychisl. matematiki i mat. fiziki, 58:6 (2018), 873–882

[5] 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 | Zbl

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

[7] Vasilev F. P., Metody optimizatsii, Kn. 1, 2, Izd-vo MTsNMO, 2011, 1056 pp.

[8] Dax A., “The smallest correction of an inconsistent system of linear inequalities”, Optimization and Engineering, 2 (2001), 349–359 | DOI | Zbl

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

[10] Skarin V. D., “On parameter control of the residual method for the correction of improper problems”, Discrete Optimization and Operations Research - 9th International Conf. (DOOR 2016), Proc., Lecture Notes in Computer Science, 9869, eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, 441–451 | DOI | Zbl

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

[12] Burke J., “An exact penalization viewpoint of constrained optimization”, SIAM J. Contr. Optim., 29:4 (1991), 968–998 | DOI | Zbl

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

[14] Skarin V. D., “O nekotorykh universalnykh metodakh korrektsii nesobstvennykh zadach vypuklogo programmirovaniya”, Avtomatika i telemekhanika, 2012, no. 2, 99–110 | Zbl