The paper is devoted to the construction of possible approximations for improper problems of convex programming 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, in this paper 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 presence of interior points of the domain of the method. We also discuss the existence of solutions to emerging 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.
Keywords: convex programming, improper problem, optimal correction, method of quasi-solutions, barrier function methods
Received August 2, 2022
Revised August 25, 2022
Accepted August 29, 2022
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: skavd@imm.uran.ru
REFERENCES
1. Eremin I.I., Mazurov Vl.D., Astaf’ev N.N. Nesobstvennye zadachi lineinogo i vypuklogo programmirovaniya [Improper problems of linear and convex programming]. Moscow: Nauka Publ., 1983, 336 p.
2. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for solving ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
3. Vasil’ev F.P. Metody optimizatsii. T. 1,2. [Optimization methods. Vol. 1, 2]. Moscow: MTsNMO Publ., 2011, 1056 p. ISBN: 978-5-94057-707-2, 978-5-94057-708-9 .
4. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu lineinogo i vypuklogo programmirovaniya [Introduction to the theory of linear and convex programming]. Moscow: Nauka Publ., 1976, 196 p.
5. Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Classics in applied mathematics, vol. 4. Philadelphia: SIAM, 1987, 226 p. ISBN: 0898712548 . Translated to Russian under the title Nelineinoe programmirovanie. Metody posledovatel’noi bezuslovnoi minimizatsii. Moscow: Mir Publ., 1972, 240 p.
6. Evtushenko Yu.G. Metody resheniya ekstremal’nykh zadach i ikh primenenie v sistemakh optimizatsii [Methods of solving extremal problems and their application in optimization systems]. Moscow: Nauka Publ., 1982, 432 p.
7. Elster K.H., Reinhardt R., Schäuble M., Donath G. Einführung in die nichtlineare Optimierung. Leipzig: Teubner, 1977, 299 p. Translated to Russian under the title Vvedenie v nelineinoe programmirovanie. Moscow: Nauka Publ., 1985, 264 p. ISBN: 9782763785233 .
8. Gill P.E., Murray W., Saunders M.A., Tomlin J.A., Wright M.H. On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method. Math. Program., 1986, vol. 36, no. 2, pp. 183–209. doi: 10.1007/BF02592025
9. Skarin V.D. Barrier function method and correction algorithms for improper convex programming problems. Proc. Steklov Inst. Math. (Suppl.), 2008, vol. 263, suppl. 2, pp. S120–S134. doi: 10.1134/S0081543808060126
10. Popov L.D. Use of barrier functions for optimal correction of improper problems of linear programming of the 1st kind. Autom. Remote Control, 2012, vol. 73, no. 3, pp. 417–424. doi: 10.1134/S0005117912030010 .
11. Skarin V.D. On some universal methods of correction of the improper convex programming problems. Autom. Remote Control, 2012, vol. 73, no. 2, pp. 300–309. doi: 10.1134/S0005117912020087
12. Popov L.D., Skarin V.D. Lexicographic regularization and duality for improper linear programming problems. Proc. Steklov Inst. Math. (Suppl.), 2016, vol. 295, suppl. 1, pp. 131–144. doi: 10.1134/S0081543816090145
13. Skarin V.D. On the parameter control of the residual method for the correction of improper problems of convex programming. In: Kochetov Y., Khachay M., Beresnev V., Nurminski E., Pardalos P. (eds.), Discrete Optimization and Operations Research. DOOR 2016, Ser. Lecture Notes in Computer Science, vol. 9869, Springer, 2016, pp. 441–451. doi: 10.1007/978-3-319-44914-2_35
14. Volkov V.V., Erokhin V.I., Krasnikov A.S., Razumov A.V., Khvostov M.N. Minimum-Euclidean-norm matrix correction for a pair of dual linear programming problems. Comput. Math. Math. Phys., 2017, vol. 57, no. 11, pp. 1757–1770. doi: 10.1134/S0965542517110148
15. Murav’eva O.V. Determination of consistency and inconsistency radii for systems of linear equations and inequalities using the matrix $l_1$ norm. Comput. Math. Math. Phys., 2018, vol. 58, no. 6, pp. 840–849. doi: 10.1134/S0965542518060106
16. Vasil’ev F.P., Potapov M.M., Artem’eva L.A. Extragradient method for correction of inconsistent linear programming problems. Comput. Math. Math. Phys., 2018, vol. 58, no. 12, pp. 1919–1925. doi: 10.1134/S0965542518120163
17. Golub G.H., Hansen P.C., O’Leary D.P. Tikhonov regularization and total least squares. SIAM J. Matrix Anal. Appl., 1999, vol. 21, no. 1, pp. 185–194. doi: 10.1137/S0895479897326432
18. Renaut R.A., Guo N. Efficient algorithms for solution of regularized total least squares. SIAM J. Matrix Anal. Appl., 2005, vol. 26, no. 2, pp. 457–476. doi: 10.1137/S0895479802419889
Cite this article as: V.D. Skarin. The method of quasi-solutions based on barrier functions in the analysis of improper convex programming problems. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 4, pp. 201-215; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2022, Vol. 319, Suppl. 1, pp. S242–S256.
