On the regularized method of 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 30 (2024) no. 4, pp. 234-250

Résumé

The paper considers the problem of constructing approximations for a wide class of improper convex programs (ICPs). The original problem with an inconsistent system of constraints is immersed in a parametric family of feasible convex programming models, where the norm of the discrepancy of the constraint functions serves as a parameter. The minimum value of the parameter at which the feasible set of the problem becomes nonempty determines an optimal correction of the ICP. To solve the correction problem, one of the classical methods of regularization of ill-posed extremal problems is used — the method of stabilizing functions (Tikhonov's method). In this case, the original problem with constraints is initially reduced to the problem of unconstrained minimization of a certain penalty function. Instead of conventional external penalty functions, the paper uses the method of internal (barrier) functions. The design features of barrier functions can provide certain advantages in the numerical implementation of the correction method. Conditions for the solvability of problems arising at various stages of the proposed correction method are formulated, and the issues of matching the process parameters that ensure the required convergence are studied. The capabilities of the method when working with perturbed data are analyzed.

Détail

Keywords: convex programming, improper problem, Tikhonov regularization method, 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] Eremin I.I., Protivorechivye modeli optimalnogo planirovaniya, Nauka, M., 1988, 160 pp. | MR

[4] Kochikov I.V., Matvienko A.N., Yagola A.G., “Obobschennyi printsip nevyazki dlya resheniya nesovmestnykh uravnenii”, Zhurn. vychisl. matematiki i mat. fiziki, 24:7 (1984), 1087–1090 | MR | Zbl

[5] Parametricheskaya optimizatsiya i metody approksimatsii nesobstvennykh zadach matematicheskogo programmirovaniya, Sb. nauch. statei, Izd-vo UNTs AN SSSR, Sverdlovsk, 1985, 136 pp.

[6] Skarin V.D., “Ob odnom podkhode k analizu nesobstvennykh zadach lineinogo programmirovaniya”, Zhurn. vychisl. matematiki i mat. fiziki, 26:3 (1986), 439–448 | MR | Zbl

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

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

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

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

[11] 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 | MR | Zbl

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

[13] Khachai M.Yu., “Ob otsenke chisla chlenov minimalnogo komiteta sistemy lineinykh neravenstv”, Zhurn. vychislitelnoi matematiki i mat. fiziki, 37:11 (1997), 1399–1404 | MR | Zbl

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

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

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

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

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

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

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

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

[22] Popov L.D., “Poisk obobschennykh reshenii nesobstvennykh zadach lineinogo i vypuklogo programmirovaniya s pomoschyu barernykh funktsii”, Izv. Irkutskogo gos. un-ta. Ser. Matematika, 4:2 (2011), 134–146 | Zbl

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