We consider a class of improper convex programs with a possibly inconsistent system of constraints, which is important from the viewpoint of applications. Such problems are characterized as improper problems of convex optimization. Since improper problems are rather frequent, it is important to develop the theory and numerical methods of their correction (approximation). The correction is understood as the construction of solvable models that are close to the original problems in a certain sense. Solutions of these models are taken as generalized solutions of the original improper problems. In the present paper the correcting problems are constructed based on the minimization of a certain penalty function depending on the constraints. Since the information about the functions of the original model may be inexact, we apply for the corrected problem the quasisolution method, which is a standard regularization method for ill-posed optimization problems. Convergence conditions are formulated for the proposed methods and convergence rates are established.
Keywords: convex programming, improper problem, optimal correction, penalty function methods, quasisolution method
Received July 15, 2019
Revised October 3, 2019
Accepted October 7, 2019
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. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for the solution of ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
3. Vasil’ev F.P. Metody optimizatsii [Optimization methods]: vol. 1 2. Moscow: MTsNMO Publ., 2011, 1056 p. ISBN: 978-5-94057-706-5 .
4. Bakushinsky A., Goncharsky A. Ill-Posed Problems: Theory and Applications. Dordrecht: Springer, 1994. ISBN: 978-94-010-4447-9 . Original Russian text published in Bakushinskii A.B., Goncharskii A.V. Iterativnye metody resheniya nekorrektnykh zadach. Moscow: Nauka Publ., 1989, 128 p.
5. Kaltenbacher B., Neubauer A., Scherzer O. Iterative regularization methods in nonlinear ill-posed problems. Berlin; N Y: de Gruyter, 2008, 194 p. ISBN: 978-3-11-020827-6
6. 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
7. 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
8. 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), Lecture Notes in Computer Science, vol. 9869, 2016, pp. 441–451. doi: 10.1007/978-3-319-44914-2_35
9. Skarin V.D. Correction of improper convex programming problems using regularization methods. In: Book of abstr. 8th Intern. Conf. “Optimization and Applications”: OPTIMA-2017 (Petrovac, Montenegro, Oct. 2017), Moscow, 2017, p. 134.
Cite this article as: V.D.Skarin. On the application of the quasisolution method to the correction of improper convex programs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 189–200.
