We consider the questions of correction of improper convex programming problems, first of all, problems with inconsistent systems of constraints. Such problems often arise in the practice of mathematical simulation of specific applied settings in operations research. Since improper problems are rather frequent, it is important to develop methods of their correction, i.e., methods of construction of solvable models that are close to the original problems in a certain sense. Solutions of these models are taken as generalized (approximation) solutions of the original problems. We construct the correcting problems using a variation of the right-hand sides of the constraints with respect to the minimum of a certain penalty function, which, in particular, can be taken as some norm of the vector of constraints. As a result, we obtain optimal correction methods that are modifications of the (Tikhonov) regularized method of penalty functions. Special attention is paid to the application of the exact penalty method. Convergence conditions are formulated for the proposed methods and convergence rates are established.
Keywords: convex programming, improper problem, optimal correction, penalty function methods, Tikhonov regularization method
The paper was received by the Editorial Office on May 17, 2018.
Funding Agency: This work was supported by the Russian Science Foundation (project no. 14-11-00109).
Vladimir Dmitrievich Skarin, Dr. Phys.-Math. Sci, Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 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. Mazurov V.D. Metod komitetov v zadachakh optimizatsii i klassifikatsii [Committee method in problems of optimization and classification]. Moscow: Nauka Publ., 1990, 246 p. ISBN: 5-02-013976-9 .
3. Khachay M.Yu. On approximate algorithm of a minimal committee of a linear inequalities system. Pattern Recogn. and Image Anal., 2003, vol. 13, no. 3, pp. 459–464.
4. 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 .
5. Erokhin V.I., Krasnikov A.S., Khvostov M.N. Matrix corrections minimal with respect to the Euclidean norm for linear programming problems. Autom. Remote Control, 2012, vol. 73, no. 2, pp. 219–231. doi: 10.1134/S0005117912020026 .
6. Skarin V.D. On the application of a regularization method for the correction of improper problems of convex programming. Proc. Steklov Inst. Math., 2013, vol. 283, suppl. 1, pp. 126–138. doi: 10.1134/S0081543813090137 .
7. 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 .
8. Amaral P., Barahona P. Connections between the total least squares and the correction of an infeasible system of linear inequalities. Linear Algebra and Its Appl., 2005, vol. 395, pp. 191–210. doi: 10.1016/j.laa.2004.08.022 .
9. Tikhonov A.N., Arsenin V.Ya. Metody resheniya nekorrektnykh zadach [Methods for the solution of ill-posed problems]. Moscow: Nauka Publ., 1979, 288 p.
10. Ivanov V.K., Vasin V.V., Tanana V.P. Theory of linear ill-posed problems and its applications. Utrecht: VSP, 2002, Inverse and Ill-Posed Problems Series, 281 p. ISBN: 90-6764-367-X/hbk . Original Russian text published in Ivanov V.K., Vasin V.V., Tanana V.P. Teoriya lineinykh nekorrektnykh zadach i ee prilozheniya. Moscow, Nauka Publ., 1978, 208 p.
11. 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 .
12. 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 .
13. 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 .
14. Skarin V.D. On the parameter control of the residual method for the correction of improper problems of convex programming. In: Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos (eds.), Discrete Optimization and Operations Research. DOOR 2016., 2016, Ser. Lecture Notes in Computer Science, vol. 9869, pp. 441–451. doi: 10.1007/978-3-319-44914-2_35 .
15. 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, 191 p.
