The paper is devoted to the analysis of some convex programs that are “degenerate” (improper, having no solutions in the usual sense). We propose an approach to the correction of such problems based on the ideas of the quasisolution method, which is standard in the theory of ill-posed extremal problems. The constraints of the original problem are aggregated with the use of a certain penalty function, which is explicitly included in the scheme of the quasisolution method. Two most popular variants are used: an exact penalty function and a quadratic penalty function. For each of these variants, the questions of solvability of the arising problems are studied and estimates for the convergence rate of the proposed procedures are established in the case where the input information about the problem to be analyzed is given approximately.
Keywords: convex programming, improper problem, optimal correction, quasisolution method, penalty function methods
Received May 12, 2021
Revised June 10, 2021
Accepted June 21, 2021
Funding Agency: This work was supported by the Russian Foundation for Basic Research (project no. 19-07-01243).
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 V.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. 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
3. 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
4. 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
5. 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
6. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for the solution of ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
7. Vasil’ev F.P. Metody optimizatsii [Optimization methods]. Moscow: MTsNMO Publ., 2011. Vol. 1: 620 p., ISBN: 978-5-94057-707-2 ; Vol. 2: 433 p., ISBN: 978-5-94057-708-9 .
8. Dax A. The smallest correction of an inconsistent system of linear inequalities. Optimization and Engineering, 2001, vol. 2, no. 3, pp. 349–359. doi: 10.1023/A:1015370617219
9. 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
10. Skarin V.D. On the parameter control of the residual method for the correction of improper problems of convex programming. In: Discrete Optimization and Operations Research (DOOR 2016), Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalo (eds.), Ser. Lecture Notes in Computer Science, vol. 9869, 2016, pp. 441–451. doi: 10.1007/978-3-319-44914-2_35
11. 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, 192 p.
12. Burke J. An exact penalization viewpoint of constrained optimization. SIAM J. Contr. Optim., 1991, vol. 29, no. 4, pp. 968–998. doi: 10.1137/0329054
13. Evtushenko Yu.G. Numerical optimization techniques. NY: Springer-Verlag, 1985, 562 p. ISBN: 978-1-4612-9530-3 . Original Russian text published in Evtushenko Yu.G. Metody resheniya ekstremal’nykh zadach i ikh primenenie v sistemakh optimizatsii, Moscow: Nauka Publ., 1982, 432 p.
14. 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
Cite this article as: V.D. Skarin. The quasisolution method in the analysis of convex programs with singularities, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 4, pp. 125–141.
