The method of penalty functions and regularization in the analysis of improper convex programming problems

V. D. Skarin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 24 (2018) no. 3, pp. 187-199

Résumé

We consider the questions of correction of improper convex programming problems, first of all, problems with inconsistent systems of constraints. Such problems often arise in the practice of mathematical simulation of specific applied settings in operations research. Since improper problems are rather frequent, it is important to develop methods of their correction, i.e., methods of construction of solvable models that are close to the original problems in a certain sense. Solutions of these models are taken as generalized (approximation) solutions of the original problems. We construct the correcting problems using a variation of the right-hand sides of the constraints with respect to the minimum of a certain penalty function, which, in particular, can be taken as some norm of the vector of constraints. As a result, we obtain optimal correction methods that are modifications of the (Tikhonov) regularized method of penalty functions. Special attention is paid to the application of the exact penalty method. Convergence conditions are formulated for the proposed methods and convergence rates are established.

Détail

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

Bibliographie

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

[2] Mazurov Vl. D., Metod komitetov v zadachakh optimizatsii i klassifikatsii, Nauka, M., 1990, 246 pp.

[3] Khachay M. Yu., “On approximate algorithm of a minimal committee of a linear inequalities system”, Pattern Recogn. and Image Anal., 13:3 (2003), 459–464

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

[5] Erokhin V. I., Krasnikov A. S., Khvostov M. N., “Matrichnye korrektsii zadach lineinogo programmirovaniya po minimumu evklidovoi normy”, Avtomatika i telemekhanika, 2012, no. 3, 219–231

[6] Skarin B. D., “O primenenii odnogo metoda regulyarizatsii dlya korrektsii nesobstvennykh zadach vypuklogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 18:3 (2012), 230–241

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

[8] Amaral P., Barahona P., “Connections between the total least squares and the correction of an infeasible system of linear inequalities”, Linear Algebra and Its Appl., 395 (2005), 191–210 | DOI

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

[10] Ivanov V. K., Vasin V. V., Tanana V. P., Teoriya lineinykh nekorrektnykh zadach i ee prilozheniya, Nauka, M., 1978, 208 pp.

[11] Vasilev F. P., Metody optimizatsii, Kn. 1, 2, v. 1, MTsNMO, M., 2011, 620 pp.; т. 2, 433 с.

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

[13] 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

[14] Skarin V. D., “On the parameter control of the residual method for the correction of improper problems of convex programming”, Proc. DOOR 2016, Lecture Notes Comp. Sci., 9869, Springer International Publishing, Cham, 2016, 441–451 | DOI

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