Parallel Newton methods for numerical analysis of infeasible linear programming problems with block-angular structure of constraints / Popov L.D. // CEUR Workshop Proceedings. - 2016. - V. 1623, l. . - P. 253-260.

ISSN:
16130073
Type:
Conference Paper
Abstract:
For the linear programming (LP) problems, perhaps infeasible, with block-angular matrices of constraints, two parallel second order optimization methods are proposed. Being applied to initial LP problem they give its solution if this problem is solvable, and automatically deliver a solution of some relaxed LP problem, otherwise. The methods use penalty and barrier functions as well as Tikhonov regularization of Lagrangian of initial problem. The methods contain a parameter which tends to zero and minimize a residual of constraints. Parallel calculations of matrix operations follow MPI-type paradigm. Copyright © by the paper's authors.
Author keywords:
Generalized solution; Ill-posed problems; Infeasibility; Linear programming; Parallel calculations; Penalty function; Regularization
Index keywords:
Linear programming; Matrix algebra; Newton-Raphson method; Numerical analysis; Numerical methods; Operations research; Optimization; Generalized solution; Ill posed problem; Infeasibility; Parallel ca
DOI:
нет данных
Смотреть в Scopus:
https://www.scopus.com/inward/record.uri?eid=2-s2.0-85019621504&partnerID=40&md5=12f7e5f366f0868ac8a149e9f9674359
Соавторы в МНС:
Другие поля
Поле Значение
Link https://www.scopus.com/inward/record.uri?eid=2-s2.0-85019621504&partnerID=40&md5=12f7e5f366f0868ac8a149e9f9674359
Affiliations Krasovskii Institute of Mathematics and Mechanics UB RAS, Ekaterinburg, Russian Federation; Ural Federal University, Ekaterinburg, Russian Federation
Author Keywords Generalized solution; Ill-posed problems; Infeasibility; Linear programming; Parallel calculations; Penalty function; Regularization
Funding Details 16-07-00266, RFBR, Russian Foundation for Basic Research
Funding Text This work was supported by Russian Foundation for Basic Research (project no. 16-07-00266).
References Eremin, I.I., Mazurov, Vl.D., Astaf'ev, N.N., (1983) Improper Problems of Linear and Convex Programming, , Nauka, Moscow. In Russian; Eremin, I.I., (2002) Theory of Linear Optimization. Inverse and Ill-Posed Problems Series, , VSP. Utrecht, Boston, Koln, Tokyo; Chinneck, J.W., Feasibility and viability (1997) Advances in Sensitivy Analysis and Parametric Programming, , T. Gal, H.J. Greenberg (Eds.) Kluwer Academic Publishers, Boston; Ben-Tal, A., Nemirovski, A., Robust solutions of linear programming problems contaminated with uncertain data (2000) Math. Progr., 88 (3), pp. 411-424; Amaral, P., Barahona, P., Connections between the total least squares and the correction of an infeasible system of linear inequalities (2005) Linear Algebra and its Appl., 395, pp. 191-210; Leon, T., Liern, V., A fuzzy method to repair infeasibility in linear constrained problems (2001) Fuzzy Set and Systems, 122, pp. 237-243; Dax, A., The smallest correction of an inconsistent system of linear inequalities (2001) Optimization and Engineering, 2, pp. 349-359; Eremin, I.I., Popov, L.D., Numerical analysis of improper linear programs using the DELTA-PLAN-ES interactive system (1993) Optimization Methods and Software, 2, pp. 69-78; Skarin, V.D., Regularized lagrange function and correction methods for improper convex programming problems (2002) Proc. Steklov Inst. Math. Mathematical Programming. Regularization and Approximation, pp. S116-S144; Popov, L.D., Use of barrier functions for optimal correction of improper problems of linear programming of the 1st kind (2012) Automation and Remote Control, 73 (3), pp. 417-424; Popov, L.D., Dual approach to the application of barrier functions for the optimal correction of improper linear programming problems of the first kind (2015) Proceedings of the Steklov Institute of Mathematics, 288 (1), pp. 173-179; Fiacco, A.V., McCormick, G.P., (1968) Nonlinear Programming: Sequential Unconstrained Minimization Techniques, , John Wiley and Sons, Inc: New York-London-Sidney; Tikhonov, A.N., Vasil'ev, F.P., Methods for solving ill-posed extremal problems, in: Mathematics models and numerical methods (1978) Banach Center Publ., Warszava, 3, pp. 291-348; Rockafellar, R.T., (1970) Convex Analysis, , Princeton University Press: Princeton, N.J; Gill, P.E., (1981) Practical Optimization, , Philip E. Gill, Walter Murray, Margaret H. Wright. London; New York: Academic Press; Popov, L.D., Experience in organizing hybrid parallel calculations in the evtushenko-golikov method for problems with block-angular structure (2014) Automation and Remote Control, 75 (4), pp. 622-631
Correspondence Address Popov, L.D.; Krasovskii Institute of Mathematics and Mechanics UB RASRussian Federation; email: popld@imm.uran.ru
Sponsors Far Eastern Federal University, Vladivostok;Higher School of Economics, Nizhny Novgorod;Novosibirsk State University;Russian Foundation for Basic Research
Publisher CEUR-WS
Conference name 9th International Conference on Discrete Optimization and Operations Research, DOOR 2016
Conference date 19 September 2016 through 23 September 2016
Language of Original Document English
Abbreviated Source Title CEUR Workshop Proc.
Source Scopus