Quadratic approximation of penalty functions for solving large-scale linear programs / Popov L.D. // Computational Mathematics and Mathematical Physics. - 2007. - V. 47, l. 2. - P. 200-214.

ISSN:

09655425

Type:

Article

Abstract:

Using the least squares, modified Lagrangian function, and some other methods as examples, the capabilities of the new optimization technique based on the quadratic approximation of penalty functions that has been recently proposed by O. Mangasarian for a special class of linear programming problems are demonstrated. The application of this technique makes it possible to use unified matrix operations and standard linear algebra packages (including parallel ones) for solving large-scale problems with sparse strongly structured constraint matrices. With this technique, the computational schemes of some well-known algorithms can take an unexpected form. © 2007 Pleiades Publishing, Ltd.

Author keywords:

Generalized Newton method; Lagrangian function; Large-scale linear program; Least squares method; Optimization by least squares

Index keywords:

нет данных

DOI:

10.1134/S0965542507020054

Смотреть в Scopus:

https://www.scopus.com/inward/record.uri?eid=2-s2.0-33947130625&doi=10.1134%2fS0965542507020054&partnerID=40&md5=9b32b036cf4053dd010c80c5f0f264ab

Соавторы в МНС:

—

Другие поля

Поле	Значение
Link	https://www.scopus.com/inward/record.uri?eid=2-s2.0-33947130625&doi=10.1134%2fS0965542507020054&partnerID=40&md5=9b32b036cf4053dd010c80c5f0f264ab
Affiliations	Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation
Author Keywords	Generalized Newton method; Lagrangian function; Large-scale linear program; Least squares method; Optimization by least squares
References	Eremin, I.I., (2002) Theory of Linear Optimization. Inverse and Ill-Posed Problems Series, , VSP, Boston; Eremin, I.I., Mazurov, V.D., (1979) Nonstationary Processes in Mathematical Programming, , Nauka, Moscow, in Russian; Evtushenko, Y.G., (1982) Methods for Solving Extremal Problems and Their Application in Optimization Systems, , Nauka, Moscow, in Russian; Vasil'ev, F.P., (1988) Numerical Methods for Solving Extremum Value Problems, , Nauka, Moscow, in Russian; Vasil'ev, F.P., Ivanitskii, A.Y., (2003) Linear Programming, , Faktorial, Moscow, in Russian; Antipin, A.S., Nonlinear Programming Methods Based on a Primal and Dual Modification of the Lagrangian Function (1979) Preprint, VNIISI RAN SSSR, , All-Union Institute for System Studies, Academy of Sciences of the USSSR, Moscow; Lebedev, V.Y., An Approximate Algorithm for Solving Linear Programming Problems (1974) Zh. Vychisl. Mat. Mat. Fiz, 14, pp. 1052-1058; Razumikhin, B.S., The Method of Tangents for Stochastic and Dynamic Optimization Problems (1977) Avtom. Telemekh, (1), pp. 5-15; Polyak, B.T., Tret'yakov, N.V., On an Iterative Linear Programming Method and Its Economic Interpretation (1972) Ekon. Mat. Metody, 8, pp. 740-751; Mangasarian, O.L., A Finite Newton Method for Classification (2002) Optimizat. Meth. Software, 17, pp. 913-930; Kanzow, C., Qi, H., Qi, L., On the Minimum Norm Solution of Linear Program (2003) J. Optimizat. Theory Appl, 116, pp. 333-345; Golikov, A.I., Evtushenko, Y.G., Mollaverdi, N., Application of Newton's Method for Solving Large Linear Programming Problems (2004) Zh. Vychisl. Mat. Mat. Fiz, 44, pp. 1564-1573; Math, (2004) Math. Phys, 44, pp. 1484-1493. , Comput; Golub, G.H., van Loan, C.F., (1989) Matrix Computations, , John Hopkins Univ. Press, Mir, Moscow; Ortega, J.M., (1988) Introduction to Parallel and Vector Solution of Linear Systems, , Plenum, New York, Mir, Moscow; Gondzio, J., Sarkissian, R., Parallel Interior-Point Solver for Structured Linear Programs (2003) Ser. A, 96, pp. 561-584. , Math. Progr
Correspondence Address	Popov, L.D.; Institute of Mathematics and Mechanics, Ural Division, Russian Academy of Sciences, ul. S. Kovalevskoi 16, Yekaterinburg, 620219, Russian Federation; email: popld@imm.uran.ru
Language of Original Document	English
Abbreviated Source Title	Comput. Math. Math. Phys.
Source	Scopus