The Method of Quasi-Solutions Based on Barrier Functions in the Analysis of Improper Convex Programs

V. D. Skarin

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 4, pp. 201-215

Résumé

The paper is devoted to the construction of possible approximations for improper convex programs based on the application of a classical approach to the regularization of ill-posed extremal problems, namely V. K. Ivanov's method of quasi-solutions. While usually the constraints of the original problem in the method of quasi-solutions are aggregated with the help of exterior penalty functions, here we use for this purpose a generalized inverse barrier function, which is a modification of interior penalty. Due to the specifics of the problem, we introduce a number of new control parameters into the minimized barrier function. Along with the penalty coefficients and the regularization parameter, we consider parameters that ensure the correctness of the application of the barrier method, first of all, the existence of interior points in the domain of the method. We also discuss the existence of solutions to the resulting correction problems and analyze the influence of the parameters of the barrier function on the convergence of the proposed modification of the method of quasi-solutions for improper problems.

Détail

Keywords: convex programming, improper problem, method of quasi-solutions, barrier 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] Tikhonov A.N., Arsenin V.Ya., Metody resheniya nekorrektnykh zadach, Nauka, M., 1979, 288 pp.

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

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

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

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

[7] Elster K.-Kh., Reingart R., Shoible M., Donat G., Vvedenie v nelineinoe programmirovanie, Nauka, M., 1985, 264 pp. | MR

[8] Gill P.E., Murray W., Sunders M.S., Tomlin J.A., Wright M.H., “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projected methods”, Math. Prog., 36:2 (1986), 183–209 | DOI | MR

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

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

[11] Skarin V.D., “O nekotorykh universalnykh metodakh korrektsii nesobstvennykh zadach vypuklogo programmirovaniya”, Avtomatika i telemekhanika, 2 (2012), 99–110

[12] Popov L.D., Skarin V.D., “Leksikograficheskaya regulyarizatsiya i dvoistvennost dlya nesobstvennykh zadach lineinogo programmirovaniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 21:3 (2015), 279–291

[13] Skarin V., “On parameter control of the residual method for the correction of improper problems”, Discrete Optimization and Operations Research (DOOR 2016), Lecture Notes in Computer Science, 9869, eds. Kochetov, Yu. et all, 441–451 | DOI | MR

[14] 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 | DOI

[15] 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 | DOI | MR

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

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

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