The paper is devoted to finding approximation solutions of improper convex programs. For such programs, a correction model is considered in the form of the problem of minimizing the objective function of the original problem on the set of extremal points of a penalty function, which aggregates the inconsistent constraints. For the penalty function, the Eremin–Zangwill exact penalty function is chosen. Under an approximately given input, a generalized solution of the improper convex program is obtained by applying the quasisolution method known in the theory of ill-posed problems. Estimates characterizing the quality of the correction are given. Iterative schemes implementing this approach are proposed.
Keywords: convex programming, improper problem, optimal correction, exact penalty function method, quasisolution method
Received March 3, 2020
Revised April 6, 2020
Accepted April 10, 2020
Funding Agency: This study is a part of the research carried out at the Ural Mathematical Center and 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., and 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., Skarin V.D. Lexicographic regularization and duality for improper linear programming problems. Proc. Steklov Inst. Math., 2016, vol. 295, suppl. 1, pp. 131–144. doi: 10.1134/S0081543816090145
3. Skarin V.D. On the application of the residual method for the correction of inconsistent problems of convex programming. Proc. Steklov Inst. Math., 2015, vol. 289, suppl. 1, pp. 182–191. doi: 10.1134/S0081543815050168
4. 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
5. Murav’eva O.V. Determination of consistency and inconsistency radii for systems of linear equations and inequalities using the matrix l1 norm. Comput. Math. Math. Phys., 2018, vol. 58, no. 6, pp. 840–849. doi: 10.1134/S0965542518060106
6. 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
7. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for the solution of ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
8. 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 .
9. Golub G.N., 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
10. 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
11. Eremin I.I., Astaf’ev N.N. Vvedenie v teoriyu linejnogo 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 Journal on Control and Optimization, 1991, vol. 29, no. 4, pp. 968–998. doi: 10.1137/0329054
13. Dem’yanov V.F., Vasil’ev L.V. Nondifferentiable Optimization. N Y: Springer-Verlag, 1985, 452 p. ISBN: 978-0-387-90951-6 . Original Russian text published in Dem’yanov V.F. Vasil’ev L.V., Nedifferentsiruemaya optimizatsiya, Moscow: Nauka Publ., 1981, 384 p.
Cite this article as: V.D. Skarin. On the choice of parameters in the quasisolution method for the correction of improper convex programs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 187–197.
