The work continues the author’s research on the construction of possible approximations for improper problems of convex programming. The problem of minimizing the objective function of the original problem on the set of minimum points of the Chebyshev norm of the constraint discrepancy is defined as a basic model for correcting an improper problem. For this setting, one of the classical methods of regularization of ill-posed extremal problems is used, namely, the method of quasi-solutions. This method is based on the transition to a problem of unconstrained minimization by aggregation of the constraint function of the original problem. For this purpose, a modification of the penalty function method is used, namely, the generalized inverse barrier function method. This approach seems to be promising from the point of view of the numerical implementation of the quasi-solution method. Convergence conditions are formulated for the proposed method, including the case where the input data are given inaccurately. Special attention is paid to finding the value of optimal correction of the constraints in the improper problem of convex programming under study and to calculating the optimal value of the regularization parameter in the method of quasi-solutions.
Keywords: convex programming, improper problem, optimal correction, method of quasi-solutions, barrier function methods
Received March 27, 2023
Revised July 14, 2023
Accepted July 21, 2023
Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-02-2023-913).
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. Duality for improper problems of linear and convex programming. Soviet Math. Dokl., 1981, vol. 23, pp. 62–66.
2. 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.
3. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for solving ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
4. Vasil’ev F.P. Metody optimizatsii. T. 1,2. [Optimization methods. Vol. 1, 2]. Moscow, Moskovskii Tsentr Nepr. Mat. Obr. Publ., 2011, 1056 p. ISBN: 978-5-94057-707-2, 978-5-94057-708-9.
5. 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
6. 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
7. 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
8. Fiacco A.V., McCormick G.P. Nonlinear programming: sequential unconstrained minimization techniques. Classics in applied mathematics, vol. 4. Philadelphia: SIAM, 1987, 226 p. doi: 10.1137/1.9781611971316 Translated to Russian under the title Nelineinoe programmirovanie. Metody posledovatel’noi bezuslovnoi minimizatsii, Moscow: Mir Publ., 1972, 240 p.
9. 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.
10. 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.
11. Minoux M. Programmation mathematique: theorie et algorithmes. Dunod, 1987. Translated to Russian under the title Matematicheskoe programmirovanie: teoriya i algoritmy, Moscow, Nauka Publ., 1990, 488 p. ISBN: 5-02-013980-7.
12. 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
13. 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
14. Skarin V.D. The method of quasi-solutions based on barrier functions in the analysis of improper convex programming problems. Proc. Steklov. Inst. Math.(Suppl.), vol. 319, suppl. 1, pp. S242–S256. doi: 10.1134/S0081543822060219
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, 2023, vol. 29, no. 3, pp. 168–184 .
